- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我最近开始学习 Clojure 并决定练习欧拉问题以掌握可用的数据结构并练习递归和循环。
我尝试了各种方法来 Problem 50 ,但无论我做什么,找到 1000000 的解决方案从未完成。在我查阅了其他人的做法后,我猜我所做的应该也不会花很长时间,所以我在 Python 中输入了等效的算法,看看问题是否出在我对某些 Clojure 的东西或 Java 设置缺乏理解。 Python 在 10 秒内完成。对于 100000 以下的素数,Python 版本在 0.5 秒内完成,Clojure 在 5 秒内完成。
我发布的是专门为匹配 Python 代码而创建的 Clojure 版本。你能帮我理解为什么会有这样的性能差异吗?我应该使用未经检查的添加、类型提示、基元(但在哪里?)还是什么?
这是 Clojure:
(defn prime? [n]
(let [r (int (Math/sqrt n))]
(loop [d 2]
(cond
(= n 1) false
(> d r) true
(zero? (rem n d)) false
:other (recur (inc d))))))
(defn primes []
(filter prime? (iterate inc 2)))
(defn cumulative-sum [s]
(reduce
(fn [v, x] (conj v (+ (last v) x)))
[(first s)]
(rest s)))
(defn longest-seq-under [n]
"Longest prime seq with sum under n"
(let [ps (vec (take-while #(< % n) (primes))) ; prime numbers up to n
prime-set (set ps) ; set for testing of inclusion
cs (cumulative-sum ps)
cnt (count ps)
max-len (count (take-while #(< % n) cs)) ; cannot have longer sequences
sub-sum (fn [i j] ; sum of primes between the i-th and j-th
(- (cs j) (get cs (dec i) 0)))
seq-with-len (fn [m] ; try m length prime sequences and return the first where the sum is prime
(loop [i 0] ; try with the lowest sum
(if (> i (- cnt m)) ; there are no more elements for and m length sequence
nil ; could not find any
(let [j (+ i (dec m)) ; fix length
s (sub-sum i j)]
(if (>= s n) ; overshoot
nil
(if (prime-set s) ; sum is prime
[i (inc j)] ; we just looked for the first
(recur (inc i))))))))] ; shift window
(loop [m max-len] ; try with the longest sequence
(if (not (zero? m))
(let [[i j] (seq-with-len m) ]
(if j
(subvec ps i j)
(recur (dec m))))))))
(assert (= [2 3 5 7 11 13] (longest-seq-under 100)))
(let [s1000 (longest-seq-under 1000)]
(assert (= 21 (count s1000)))
(assert (= 953 (reduce + s1000))))
; (time (reduce + (longest-seq-under 100000))) ; "Elapsed time: 5707.784369 msecs"
在 Python 中也是如此:
from math import sqrt
from itertools import takewhile
def is_prime(n) :
for i in xrange(2, int(sqrt(n))+1) :
if n % i == 0 :
return False
return True
def next_prime(n):
while not is_prime(n) :
n += 1
return n
def primes() :
i = 1
while True :
i = next_prime(i+1)
yield i
def cumulative_sum(s):
cs = []
css = 0
for si in s :
css += si
cs.append( css )
return cs
def longest_seq_under(n) :
ps = list(takewhile( lambda p : p < n, primes()))
pss = set(ps)
cs = cumulative_sum(ps)
cnt = len(ps)
max_len = len(list(takewhile(lambda s : s < n, cs)))
def subsum(i, j):
return cs[j] - (cs[i-1] if i > 0 else 0)
def interval_with_length(m) :
for i in xrange(0, cnt-m+1) :
j = i + m - 1
sij = subsum(i,j)
if sij >= n :
return None, None
if sij in pss : # prime
return i, j+1
return None, None
for m in xrange(max_len, 0, -1) :
f, t = interval_with_length(m)
if t :
return ps[f:t]
assert longest_seq_under(100) == [2, 3, 5, 7, 11, 13]
assert sum(longest_seq_under(1000)) == 953
# import timeit
# timeit.Timer("sum(longest_seq_under(100000))", "from __main__ import longest_seq_under").timeit(1) # 0.51235757617223499
谢谢
最佳答案
我认为速度变慢是因为您遍历 longest-seq-under
中的序列的次数;每一次迭代都会付出代价。这是一个吸烟快速版本,基于您的代码和发布的答案的组合 here .注意 primes
是惰性的,所以我们可以用 def
和 defn
绑定(bind)它:
(defn prime? [n]
(let [r (int (Math/sqrt n))]
(loop [d 2]
(cond (= n 1) false
(> d r) true
(zero? (rem n d)) false
:else (recur (inc d))))))
(def primes (filter prime? (iterate inc 2)))
(defn make-seq-accumulator
[[x & xs]]
(map first (iterate
(fn [[sum [s & more]]]
[(+ sum s) more])
[x xs])))
(def prime-sums
(conj (make-seq-accumulator primes) 0))
(defn euler-50 [goal]
(loop [c 1]
(let [bots (reverse (take c prime-sums))
tops (take c (reverse (take-while #(> goal (- % (last bots)))
(rest prime-sums))))]
(or (some #(when (prime? %) %)
(map - tops bots))
(recur (inc c))))))
这在我的机器上用了大约 6 毫秒完成:
user> (time (euler-50 1000000))
"Elapsed time: 6.29 msecs"
997651
关于python - 为什么对于 Euler 50 的等效解决方案,Clojure 比 Python 慢 10 倍?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8064336/
为什么该语言的名称是“Clojure”? 我用谷歌搜索了一下,在#clojure 中询问。到目前为止,还没有运气。 最佳答案 Rich Hickey(他是 Clojure 的设计者)对此的评论是 wi
我不明白为什么升级后会出现以下编译错误: Compiling addr-verify.core Exception in thread "main" java.lang.NoClassDefFound
我试图将从映射操作返回的(惰性)序列传递给另一个映射操作,以便我可以在第一个序列中查找元素。代码从文本文件(以行/列格式)解析一些足球装置,清理它,然后返回一张 map 。 这是代码: (ns fix
我想过滤一组,例如: (filter-set even? #{1 2 3 4 5}) ; => #{2 4} 如果我使用clojure.core/filter我得到一个不是集合的seq: (filte
(defn hi[](+ 5 6)) (hi) (defn hi[](+ 6 7)) (hi) 你好,我是 clojure 的新手。如上所述,我编写了两个具有相同名称的函数。我们可以在 cloj
我按照这个伪代码递归地将十进制转换为二进制。 findBinary(decimal) if (decimal == 0) binary = 0 else binar
我正在尝试学习 Clojure 并尝试定义这个简单的函数: user=> (defn triple [arg] (* 3 arg)) #'user/triple user=> (triple 1) 3
是->和 ->>宏只是为了使代码更具可读性还是它们还有其他特定功能? 最佳答案 线程优先( -> )和线程最后( ->> )是为了使代码更具可读性。但这已经很重要了! 它允许取消嵌套函数调用(示例取自
我在 http://www.learningclojure.com/2010/11/yet-another-way-to-write-factorial.html 上找到了这个代码,但我不明白 pop
我正在阅读 Programming Clojure 2nd edition,在第 49 页它涵盖了 Clojure 的 for 循环结构,它说它实际上是一个序列理解。 作者建议使用以下代码: (def
Clojure 中有双端队列吗?我的印象是 Clojure 的 PersistentQueue 是单端的(我错了吗?)。我需要能够从队列的任一端删除(即“pop”)和“peek”数据。我所说的双端队列
换句话说,有没有办法在看起来不像 (MACRO arg* ...) 的表单上触发宏扩展? . 举一个假设的例子: (defmacro my-var (do (printf "Using my-va
我很难理解懒惰。 有人能帮我理解为什么我下面的函数不是懒惰的吗 (defn my-red ([f coll] (my-red f (first coll) (rest coll) ))
在 Clojure 核心中决定参数函数顺序的规则是什么(如果有的话)? 类似 map 的函数和 filter期望数据结构作为最后一个 争论。 类似 assoc 的函数和 select-keys期待数据
我在 clojuredocs 上遇到过 completing 函数,但目前没有文档。 你能提供一些例子吗? 最佳答案 completing 用于扩充可能没有具有一元“完成”元数的一元重载的二元归约函数
这个现在支持吗?我能找到的唯一信息是来自维基的示例( https://github.com/clojure/core.match/wiki/Deftype-and-defrecord-matching
我正在关注“Clojure in Action”,对此我感到困惑: (defn with-log [function-to-call log-statement ] (fn [& args
对于下面的代码,箭头是宏还是函数名称中的简单字符? (来自 here) (defn file->map [file] ;; TODO ) 最佳答案 箭头是函数名称的一部分。有一个函数定义,不是
Clojure 的 range函数包含来自 start独家在end (如果提供)。核心库中是否有一个函数可以提供完全包含(开始和结束)的范围? 我发现在某些情况下必须调整最终值的代码 - 例如向下而不
当我尝试从 REPL 运行以下代码时(使用动态记录): (defrecord (symbol "rec2") (vec (map symbol ["f1" "f2"]))) 我收到错误 Compile
我是一名优秀的程序员,十分优秀!