1,1,4,5,1,4按顺序进行四则运算可以得到的所有结果
-
如果是保留顺序的话复杂度是O(2^n) 不保留顺序的话复杂度是O(n!2^n)
所以没什么可优化的（暴言）
-
@arsdragonfly racket应该是有模式匹配的，但是我对scheme的了解仅限于SICP里讲到了的,因此我没有用
-
兄啊你这内存这么大可怎么用啊，快去看三章罢（指SICP
-
@sataycc fa!?，我记得三章讲的是状态吧，我感觉没有什么能用来降低内存使用量的办法；再加上GO是屑，所以赋值也是屑（暴论）
-
@田所浩治容疑者
迫真list, call-by-need的里技
Friedman, Daniel P. (1976). “Cons should not evaluate its arguments”. ICALP.印象中三章提到这个了
-
@sataycc 这里用惰性列表应该也省不了什么资源吧（困惑），不过Friedman这篇论文我也没看过，我只知道惰性列表有很强的表达能力
-
@田所浩治容疑者 兄啊你display一下这个(add-oprtor (divide ls))，想想也知道会指数爆炸吧，这么大的东西直接在内存里铺开map
-
@sataycc 但是在这个列表中的确是每一个元素都会被用到，因此无论列表是不是惰性的，使用的内存都是一个数量级的（反而应该说因为thunk的使用，惰性列表会消耗更多内存）。另外这道题答案本身就是指数级的，我也没办法啊（
-
@田所浩治容疑者 除了这个Qsort实在是太屑了无法lazy，剩下的操作都可以写成循环，所以可以在O(1)的空间复杂度完成。那么lazy就只是一个语法糖了。
-
@sataycc O(n)空间复杂度是immutable pair的原罪，因为每一次map都会导致创建一个新的列表，无论这个列表是否是惰性的（不过惰性列表求值map f (map g l) 类似的这种表达式有优势 ，但是空间依旧是O(n)的）。我觉得你对惰性求值的理解有点偏差
-
@田所浩治容疑者
我们当场表示一个所有自然数:
(define (n x) (cons x (lambda () (n (add1 x)))))
(define ns (n 1))
然后把所有自然数加1:
(define (mymap f s) (cons (f (car s)) (lambda () (mymap f ((cdr s))))))
(define nsplus1 (mymap add1 ns))
占用的空间只有两个元素而已。
不难理解吧？
-
@sataycc 但是这里知道的信息也只是表头是2而已，要想知道其他元素，还得继续求值。一个被求值了1个元素的流是一个元素，一个被求值了1000个元素的流也是一个元素，但是两者占用空间是不同的（后者多了999个用于记录的thunk）。
-
@田所浩治容疑者
当然要继续求值，但是每求下一个元素只是一个元素的计算量；稍微做一个代换就知道这样实现的lazy list是不会保存什么thunk的。
现在我们用O(1)的空间输出s中从m到n的所有数：（当然屏幕缓冲区是不算数的）
(define (output m n s)
(define (output-acc m n s acc)
(if (< acc m) (output-acc m n ((cdr s)) (add1 acc))
(if (>= m n) (display “finished”) (begin (display (car s)) (output-acc m (sub1 n) ((cdr s)) acc)))))
(output-acc m n s 0))
你可以在DrRacket里试着运行一下(output 100000000 100000001 ns)，如果你的说法成立，右下角的内存占用应该有至少400M的增长。
-
@sataycc 因为ns不是真正的流，用lambda把参数包起来之后再求值的确可以得到正确的惰性求值的结果（其实更像是只有文本替换的正则序展开），但是无法保存已被求值的元素（你这样计算得到了正确的输出结果，但是把表里面所有在过程中被求值出来的元素都给扔掉了）；所以在真正的惰性求值实现中，每一个被延时的对象都会有一个thunk（可以看SICP四章或者EOPL 4.5）。
证据的话你可以用lazy racket（drracket左下角就可以选）或者Haskell写一段逻辑相同的代码，看一看内存的使用情况。
(define (n x) (cons x (n (add1 x)))) (define ns (n 1)) (define (output m n s) (define (output-acc m n s acc) (if (< acc m) (output-acc m n (cdr s) (add1 acc)) (if (>= m n) (display "finished") (begin (display (car s)) (output-acc m (sub1 n) (cdr s) acc))))) (output-acc m n s 0)) (output 100000000 100000001 ns)
我的思路（指上面的114514计算器）的确不少都可以写成循环，但是要想要O(1)的空间复杂度的话只能用mutable pair加上imperative programming。
另外在“最后一步”用这样丢掉所有表头元素来用display实现尾递归进行输出的方法是可以节省内存的（因为之后这个列表就再也不会被用到了），但是前面是不行的（因为这个表还要被被用到）。
如果足够神触的话，说不定就可以将所有前面的过程都包到这个“最后一步”里，但这个是非常困难的，不够declarative（无知）。
-
@田所浩治容疑者
你的最后一段应该就是我想说的。
我从来没有把这个东西叫做流，正是因为它不是一个真正的流; 但是我觉得在这种每一步计算量不大的且需要枚举输出全部结果的场景下不保存中间结果这个tradeoff是赚的。
-
@田所浩治容疑者 顺便给你一个第零手资料: friedman作为call-by-need的发明者不太爱用lazy这个词，而他的学生说无论是否memoize都算lazy。所以我觉得在scheme的语境中大概这个词没那么重要。当然我也只上了他半个学期的课……
欢迎来IU，这破学校我连个inm民都没找到(
-
@sataycc fa!?，那不就是王垠大学吗？(迫真)。能亲自去上Friedman老爷子的课我也是挺羡慕的，我是国内土鳖211低端自学人（
更多本版内容
友情链接
