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版本运行的时间约为 150% 的for/fold时间没有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，但由于与延续的微妙交互，可能会使四边形时间行为摇摆不定，因此它不起作用。(我确实想知道即将转向Chez Scheme后端是否意味着"当Racket有一天获得更好的延续实现时"实际上可能很快就会到来。

你可以按照"转发"顺序构建一个列表，正如第一个提交消息所说的那样，"cons递归调用"。球拍指南中关于尾递归和递归与迭代的部分实际上详细讨论了map风格和for/fold风格方法之间的权衡。

此外，为了将来参考，Racket社区倾向于更多地生活在非常活跃和友好的球拍用户邮件列表上，在某种程度上生活在Slack频道上，而不是在Stack Overflow上。