Racket中sequence-append性能差异原因及无额外依赖的FIFO队列方案

背景 #

我使用如下代码解决Sum by Factors算法问题：

#lang racket
(provide sum-of-divided)

(define (sum-of-divided lst)
  (define (go ps n l)
    (define ((exhaust d) x)
      (define q (/ x d))
      (if (integer? q)
          ((exhaust d) q)
          (if (> x 1) `(,x) '())))
    (if (null? l)
        ps
        (if
          (for/or
            ([p ps])
            #:break (< n (sqr p))
            (= 0 (modulo n p)))
          (go ps (+ n 1) l)
          (go
            (append ps `(,n))
            (+ n 1)
            (append-map (exhaust n) l)))))
  (for*/list
    ([m (go '() 2 (map abs lst))]
     [s `(,(for/fold
       ([a '(0 #f)])
       ([x lst])
       (if (= 0 (modulo x m))
           `(,(+ (car a) x) #t)
           a))]
     #:when (cadr s))
    `(,m ,(car s))))

性能现象 #

测试时发现，只有将第20行的sequence-append替换为append后，代码才能在12秒的测试时限内通过。sequence-append的官方文档说明其特性为：

新序列是惰性构造的。

相关疑问 #

• 该惰性特性是否意味着序列仅在被访问时才会实际拼接？如果需要访问sequence-append生成序列的深层元素，会产生与之前所有序列长度总和成正比的时间开销，这是不是它性能更低的根本原因？
• 如果上述推测成立，该如何规避这类惰性序列的性能问题？
• 本次场景中append的性能已经足够，但如果需要常规时间复杂度的FIFO队列结构，有没有无需引入额外依赖包（类似Codewars这类算法平台通常无法引入第三方包）的原生Racket实现方案？
• 差量列表（自行实现难度很低）是不是可行的方案？

内容的提问来源于stack exchange，提问作者ByteEater