我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.
当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了2分钟,对规则来说太长了,一般来说太长了.这是算法:
(defn next-prime-slow
"Find the next prime number, checking against our already existing list"
([sofar guess]
(if (not-any? #(zero? (mod guess %)) sofar)
guess ; Then we have a prime
(recur sofar (+ guess 2))))) ; Try again
(defn find-primes-slow
"Finds prime numbers, slowly"
([]
(find-primes-slow 10001 [2 3])) ; How many we need, initial prime seeds
([needed sofar]
(if (<= needed (count sofar))
sofar ; Found enough, we're done
(recur needed (concat sofar [(next-prime-slow …我喜欢Clojure.困扰我的一个问题是我不知道如何实现懒惰的序列,或者它们是如何工作的.
我知道懒惰序列只评估序列中要求的项目.它是如何做到的？
我有一个序列s和这个序列的索引列表indexes.如何仅保留通过索引提供的项目？
简单的例子:
(filter-by-index '(a b c d e f g) '(0 2 3 4)) ; => (a c d e)
我的用例:
(filter-by-index '(c c# d d# e f f# g g# a a# b) '(0 2 4 5 7 9 11)) ; => (c d e f g a b)
这是我在Clojure中实现的Erathosthene筛选(基于关于流的SICP课程):
(defn nats-from [n]
(iterate inc n))
(defn divide? [p q]
(zero? (rem q p)))
(defn sieve [stream]
(lazy-seq (cons (first stream)
(sieve (remove #(divide? (first stream) %)
(rest stream))))))
(def primes (sieve (nats-from 2)))
现在,当我拿到前100个素数时,一切都好了:
(take 100 primes)
但是,如果我尝试采用前1000个素数,因为堆栈溢出而导致程序中断.我想知道是否有可能改变某种功能筛选成尾递归,并且仍然保留算法的"流"？
任何帮助???
我在Clojure中实现了Eratosthenes的筛子:
(defn sieve [n]
(loop [last-tried 2 sift (range 2 (inc n))]
(if
(or (nil? last-tried) (> last-tried n))
sift
(let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
(let [next-to-try (first (filter #(> % last-tried) filtered))]
(recur next-to-try filtered))))))
对于较大的n(如20000),它以堆栈溢出结束.为什么尾部呼叫消除不在这里工作？怎么解决？
algorithm primes functional-programming clojure sieve-of-eratosthenes
我在clojure中有一个简单的素数计算器(一种效率低下的算法,但我现在只想了解recur的行为).代码是:
(defn divisible [x,y] (= 0 (mod x y)))
(defn naive-primes [primes candidates]
(if (seq candidates)
(recur (conj primes (first candidates))
(remove (fn [x] (divisible x (first candidates))) candidates))
primes)
)
只要我不想找到太多数字,这就有用.例如
(print (sort (naive-primes [] (range 2 2000))))
作品.对于任何需要更多递归的事情,我都会遇到溢出错误.
(print (sort (naive-primes [] (range 2 20000))))
不管用.一般来说,我是否在没有尝试TCO的情况下再次使用复发或再次调用naive-primes似乎没有任何区别.为什么我在使用recur时遇到大型递归错误？
我有一个关于Clojure的问题:我正在尝试通过项目Euler来学习语言,我不明白幕后发生了什么:以下代码旨在使用返回所有素数列表lim.我认为它应该是堆空间中的O(n)因为我列出了所有数字lim,然后逐个过滤它们,同时将第一个数字移动到新的列表.(我知道我实际上每个都会重新制作新的列表,但我认为它们不会占用更多的内存？)无论如何,我正在运行这个
(defn getAllPrimes [lim]
(defn getPrimes [primes numlist]
(if (not-empty numlist) ;base case;
(recur (cons (first numlist) primes) ;put the prime on to the prime list
(filter
(fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
(rest numlist)))
primes)); return the primes
(getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be …给定一个 map {:a 1 :b [2,3]}，是否有一个内置函数可以返回序列(:a 1 :b [2,3])。
用例是将选项映射应用于函数，该函数对参数列表的其余部分进行映射解构绑定。这是 core.cache 中的一个示例。这是一个人为的例子来说明：
(defn make-car [& {:as options}] (assoc options :car true))
(make-car :color "red" :speed "fast")
; => {:car true, :speed "fast", :color "red"}
现在如果我们想分别管理选项和apply它们到函数中，我们有一个问题：
(def options {:color "red" :speed "fast"})
(apply make-car options)
; => {:car true, [:speed "fast"] [:color "red"]}
...因为当然seq地图的 是其键值对的序列。这是我想出的最好的：
(apply make-car (interleave (keys options) (vals options)))
; => {:car true, :speed "fast", :color "red"}
这是非常可怕的。我知道我可以让我自己的函数来做到这一点，但我很惊讶我没有找到内置的东西。如果没有内置的东西，那么我可能想避免在库代码中像这样解构参数列表。
我试图生成一个相对较小的(1296个元素)向量列表,基本上枚举从[0 0 0 0]到[5 5 5 5]的4个基数6位数
[0 0 0 0], [1 0 0 0] ... [5 0 0 0], [0 1 0 0] ... [5 5 5 5]
目前我所拥有的是:
(letfn [(next-v [v]
(let [active-index (some (fn [[i e]] (when (> 5 e) i))
(map-indexed vector v))]
(map-indexed #(cond
(> active-index %1) 0
(= active-index %1) (inc %2)
:else %2)
v)))]
(last (take 1290 (iterate next-v [0 0 0 0]))))
这可行,但它最终会打击堆栈.
我在这做什么导致StackOverflowError？如何构建我的代码以使其"安全"？有没有更好的方法来做我想做的事情？