为什么这个主要的筛选实现更慢？

本文介绍了为什么这个主要的筛选实现更慢？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我只是尝试一下（对我来说）一种新的编程语言：clojure。我写了一个非常天真的筛选实现，然后我试图优化一点。I was just experimenting a bit with (for me) a new programming language: clojure. And I wrote a quite naive 'sieve' implementation, which I then tried to optimise a bit.奇怪的是，（至少对我来说），新的实现wasn'Strangely enough though (for me at least), the new implementation wasn't faster, but much slower...任何人都可以提供一些深入了解为什么这么慢？Can anybody provide some insight in why this is so much slower?我也对如何改进此算法的其他提示感兴趣...I'm also interested in other tips in how to improve this algorithm...最好的问候， Arnaud GouderArnaud Gouder; naive sieve.(defn sieve ([max] (sieve max (range 2 max) 2)) ([max candidates n] (if (> (* n n) max) candidates (recur max (filter #(or (= % n) (not (= (mod % n) 0))) candidates) (inc n))))); Instead of just passing the 'candidates' list, from which I sieve-out the non-primes,; I also pass a 'primes' list, with the already found primes; I hoped that this would increase the speed, because:; - Instead of sieving-out multiples of 'all' numbers, I now only sieve-out the multiples of primes.; - The filter predicate now becomes simpler.; However, this code seems to be approx 20x as slow.; Note: the primes in 'primes' end up reversed, but I don't care (much). Adding a 'reverse' call makes it even slower :-((defn sieve2 ([max] (sieve2 max () (range 2 max))) ([max primes candidates] (let [n (first candidates)] (if (> (* n n) max) (concat primes candidates) (recur max (conj primes n) (filter #(not (= (mod % n) 0)) (rest candidates))))))); Another attempt to speed things up. Instead of sieving-out multiples of all numbers in the range,; I want to sieve-out only multiples of primes.. I don't like the '(first (filter ' construct very much...; It doesn't seem to be faster than 'sieve'.(defn sieve3 ([max] (sieve max (range 2 max) 2)) ([max candidates n] (if (> (* n n) max) candidates (let [new_candidates (filter #(or (= % n) (not (= (mod % n) 0))) candidates)] (recur max new_candidates (first (filter #(> % n) new_candidates)))))))(time (sieve 10000000))(time (sieve 10000000))(time (sieve2 10000000))(time (sieve2 10000000))(time (sieve2 10000000))(time (sieve 10000000)) ; Strange, speeds are very different now... Must be some memory allocation thing caused by running sieve2(time (sieve 10000000))(time (sieve3 10000000))(time (sieve3 10000000))(time (sieve 10000000))推荐答案我有好消息和坏消息。好消息是你的直觉是正确的。I have good news and bad news. The good news is that your intuitions are correct.(time (sieve 10000)) ; "Elapsed time: 0.265311 msecs"(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)(time (sieve2 10000)) ; "Elapsed time: 1.028353 msecs"(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)The bad news is that both are much slower than you think(time (count (sieve 10000))) ; "Elapsed time: 231.183055 msecs"1229(time (count (sieve2 10000))) ; "Elapsed time: 87.822796 msecs"1229过滤不会完成，直到答案需要打印。所有第一个表达式是计数是在一个过滤器的加载中包装序列的时间。将计数置为意味着序列实际上必须在时序表达式内计算，然后您将看到它实际需要多长时间。What's happening is that because filter is lazy, the filtering isn't getting done until the answers need to be printed. All the first expression is counting is the time to wrap the sequence in a load of filters. Putting the count in means that the sequence actually has to be calculated within the timing expression, and then you see how long it really takes.我认为在没有当你计数时，sieve2的速度更快，因为它是更好的算法。When you put the count in, sieve2 is faster because it's the better algorithm. PS当我尝试（时间（筛10000000）），我的机器崩溃与堆栈溢出，大概是因为堆积了大量的嵌套过滤器调用堆积。怎么来为你跑？P.S. When I try (time (sieve 10000000)), my machine crashes with a stack overflow, presumably because of the vast stack of nested filter calls it's building up. How come it ran for you? 这篇关于为什么这个主要的筛选实现更慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！