在试图排除复杂计算的故障时注意到一些奇怪的事情。我有一个奇怪的错误，所以我开始逐步建立计算，很早就发现一个非常非常长的序列出乎意料地实现了。我有一个列表的组合序列，如下所示:
(0 1 2 3)
(0 1 2 4)
(0 1 2 5)
对于n = 143和k = 4的n-choose-k有些非最初命名的"组合"。我计划将其操作为一个序列，以保持内存消耗合理，但这失败了:
(def combos (combinations 4 143))
(def semantically-also-combos
(filter nil? (map identity combos)))
;; this prints instantly and uses almost no memory, as expected
(println (first combos)) ; prints (0 1 2 3)
;; this takes minutes and runs the JVM out of memory
;; without printing anything
(println (first semantically-also-combos))
根据type，它们都是clojure.lang.LazySeq，但一个按预期工作，另一个崩溃进程。为什么整个seq只是通过恒等函数来实现并检查它是否为nil?
复制
的完整代码(ns my-project.core
(:gen-class))
;;; Copied from rosetta code
(defn combinations
"If m=1, generate a nested list of numbers [0,n)
If m>1, for each x in [0,n), and for each list in the recursion on [x+1,n), cons the two"
[m n]
(letfn [(comb-aux
[m start]
(if (= 1 m)
(for [x (range start n)]
(list x))
(for [x (range start n)
xs (comb-aux (dec m) (inc x))]
(cons x xs))))]
(comb-aux m 0)))
(println "Generating combinations...")
(def combos (combinations 4 143))
(def should-also-be-combos
(filter nil? (map identity combos)))
(defn -main
"Calculates combos"
[& _args]
(println (type combos))
(println (type should-also-be-combos)))
为什么不检查(filter nil? (map identity combos))实际上返回您期望传递给combinations的小得多的参数的结果?我做到了。这是combinations返回参数2和5的结果:
(combinations 2 5)
;; => ((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
这是我们通过示例中额外的惰性序列操作得到的结果:
(filter nil? (map identity (combinations 2 5)))
;; => ()
(filter nil? ...)所做的是保留所有满足谓词的元素。并且输入序列中没有一个元素是nil?，所以它将扫描整个输入序列并且将没有找到。也许您想使用(remove nil? ...)，它将删除满足谓词的元素?
(remove nil? (map identity (combinations 2 5)))
;; => ((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
回到原来的例子，这是我使用remove:
(first (combinations 4 143))
;; => (0 1 2 3)
(first (remove nil? (map identity (combinations 4 143))))
;; => (0 1 2 3)
我稍微修改了一下这个例子:
(ns tst.demo.core
(:use tupelo.core tupelo.test))
(def cnt (atom 0))
; Copied from rosetta code
(defn combinations
"If m=1, generate a nested list of numbers [0,n)
If m>1, for each x in [0,n), and for each list in the recursion on [x+1,n), cons the two"
[m n]
(let [comb-aux (fn comb-aux
[m start]
(swap! cnt inc)
(when (zero? (mod @cnt 100))
(print .)
(flush))
(when (zero? (mod @cnt 10000))
(newline)
(print @cnt " "))
(if (= 1 m)
(for [x (range start n)]
(list x))
(for [x (range start n)
xs (comb-aux (dec m) (inc x))]
(cons x xs))))]
(comb-aux m 0)))
(println "Generating combinations...")
(def combos (combinations 4 143))
(def should-also-be-combos
(filter nil? (map identity combos)))
和调用:
(dotest
(newline)
(spyx (type combos))
(spyx (type should-also-be-combos))
(newline)
(println :1)
(println (first combos))
(newline)
(println :2)
(println (first should-also-be-combos))
(newline))
与结果:
-------------------------------
Clojure 1.10.2 Java 15
-------------------------------
Testing tst.demo.core
(type combos) => clojure.lang.LazySeq
(type should-also-be-combos) => clojure.lang.LazySeq
:1
(0 1 2 3)
:2
....................................................................................................
10000 ....................................................................................................
20000 ....................................................................................................
30000 ....................................................................................................
40000 ....................................................................................................
50000 ....................................................................................................
60000 ....................................................................................................
70000 ....................................................................................................
80000 ....................................................................................................
90000 ....................................................................................................
100000 ....................................................................................................
110000 ....................................................................................................
120000 ....................................................................................................
130000 ....................................................................................................
140000 ....................................................................................................
150000 ....................................................................................................
160000 ....................................................................................................
170000 ....................................................................................................
180000 ....................................................................................................
190000 ....................................................................................................
200000 ....................................................................................................
210000 ....................................................................................................
220000 ....................................................................................................
230000 ....................................................................................................
240000 ....................................................................................................
250000 ....................................................................................................
260000 ....................................................................................................
270000 ....................................................................................................
280000 ....................................................................................................
290000 ....................................................................................................
300000 ....................................................................................................
310000 ....................................................................................................
320000 ....................................................................................................
330000 ....................................................................................................
340000 ....................................................................................................
350000 ....................................................................................................
360000 ....................................................................................................
370000 ....................................................................................................
380000 ....................................................................................................
390000 ....................................................................................................
400000 ....................................................................................................
410000 ....................................................................................................
420000 ....................................................................................................
430000 ....................................................................................................
440000 ....................................................................................................
450000 ....................................................................................................
460000 ....................................................................................................
470000 ....................................................................................................
480000 ..........................................................................nil
在我的台式电脑(5年，8核，32Gb RAM)上计时:
Passed all tests
Finished at 16:37:28.484 (run time: 5.354s)
所以你可以看到这个函数被调用了大约50万次，在我的电脑上花了5.3秒。
我相信你看到了类似Clojure Don'ts: Concat中描述的东西。它的递归形式也让我想起了著名的Ackerman函数，这是一个看似无害的函数如何"爆炸"的例子;