在 Clojure 中获得意想不到的序列实现
Getting unexpected sequence realization in Clojure
在尝试对复杂计算进行故障排除时发现了一些奇怪的事情。我遇到了一个奇怪的错误，所以我开始逐步构建计算，并且很早就发现意外地实现了一个非常非常长的序列。我有一个这样的列表组合序列：
(0 1 2 3)
(0 1 2 4)
(0 1 2 5)
for n-choose-k for n = 143 and k = 4 sometimes unoriginally named "combos".我计划将其作为 seq 进行操作以保持合理的内存消耗，但这失败了：
(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通过identity函数实现只是为了运行它并检查它是否为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)))
我对示例做了如下修改：
(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 内存）：
Passed all tests
Finished at 16:37:28.484 (run time: 5.354s)
因此您可以看到该函数被调用了大约 1/2 百万次，在我的计算机上需要 5.3 秒。
我相信您看到的内容与 Clojure Don'ts: Concat. It's recursive form also reminds me of the famous Ackerman Function 中描述的类似，这是一个看似无害的函数如何“爆炸”的示例，即使对于较小的输入值也是如此。
您为什么不检查 (filter nil? (map identity combos)) 实际上 returns 传递给 combinations 的更小参数所期望的结果？我做到了。这就是 combinations returns 与参数 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? ...)所做的是保留所有满足谓词的元素。而输入序列中元素的none是nil?，所以它会扫描整个输入序列，会找到none。也许您想使用 (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)
我的一般建议是先用“较小”的数据（例如 2 和 5）测试您的函数，然后再使用“较大”的数据（例如 4 和 143）。
在尝试对复杂计算进行故障排除时发现了一些奇怪的事情。我遇到了一个奇怪的错误，所以我开始逐步构建计算，并且很早就发现意外地实现了一个非常非常长的序列。我有一个这样的列表组合序列：
(0 1 2 3)
(0 1 2 4)
(0 1 2 5)
for n-choose-k for n = 143 and k = 4 sometimes unoriginally named "combos".我计划将其作为 seq 进行操作以保持合理的内存消耗，但这失败了：
(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通过identity函数实现只是为了运行它并检查它是否为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)))
我对示例做了如下修改：
(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 内存）：
Passed all tests
Finished at 16:37:28.484 (run time: 5.354s)
因此您可以看到该函数被调用了大约 1/2 百万次，在我的计算机上需要 5.3 秒。
我相信您看到的内容与 Clojure Don'ts: Concat. It's recursive form also reminds me of the famous Ackerman Function 中描述的类似，这是一个看似无害的函数如何“爆炸”的示例，即使对于较小的输入值也是如此。
您为什么不检查 (filter nil? (map identity combos)) 实际上 returns 传递给 combinations 的更小参数所期望的结果？我做到了。这就是 combinations returns 与参数 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? ...)所做的是保留所有满足谓词的元素。而输入序列中元素的none是nil?，所以它会扫描整个输入序列，会找到none。也许您想使用 (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)
我的一般建议是先用“较小”的数据（例如 2 和 5）测试您的函数，然后再使用“较大”的数据（例如 4 和 143）。