racket - for/list 是否做了不必要的反向操作？

Question

我第一次在宏步进器中探索，注意到 for/list 扩展为涉及名为 alt-reverse 的代码。 for/list 是否将每个项目放在空列表的前面，然后将其反转？这看起来效率很低。

我写了一个小测试:

(define (test n)
  (time
    (for/list ([x (in-range n)])
      (list x x)))
  (time
    (for/fold ([result '()])
              ([x (in-range n)])
      (cons (list x x) result)))
  (void))

事实上，for/list 版本的运行时间约为 for/fold 的 150%，没有 reverse，差异显然完全是由于额外的垃圾收集:

> (test 500000)
cpu time: 1059 real time: 2079 gc time: 940
cpu time: 614 real time: 1231 gc time: 550
> (test 500000)
cpu time: 1060 real time: 3889 gc time: 907
cpu time: 770 real time: 1363 gc time: 699
> (test 500000)
cpu time: 1035 real time: 2479 gc time: 917
cpu time: 736 real time: 2535 gc time: 651

听起来我不应该养成调用for/list的习惯。是否有更有效的方法以“向前”顺序创建列表(即最后评估的项目是列表中的最后一项)？

Answer 1

查看 Git 历史记录，我发现使 for/list 避免 reverse 的更改是 committed ，但是it didn't work因为与延续的微妙相互作用可能会触发二次时间行为。 (我确实想知道即将到来的 Chez Scheme 后端迁移是否意味着“有一天 Racket 能够更好地实现延续”实际上可能很快就会到来。)

您可以按“前向”顺序构建列表，正如第一个提交消息所说，“consing to a recursive call”。 Racket 指南 Tail Recursion 部分和 Recursion versus Iteration实际上详细讨论了 map 风格和 for/fold 风格方法之间的权衡。

另外，为了将来的引用，Racket 社区往往更加活跃和友好 racket-users mailing list在某种程度上，Slack channel 比 Stack Overflow 上的 channel 还要多。