球拍中的队列？

Question

我用下面的代码解决了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))))

令我惊讶的是，它通过了时间限制为12秒的测试，只是在我将L20中的sequence-append更改为append之后。 documentation for sequence-append 表示：

The new sequence is constructed lazily.

但是，事实证明，这显然意味着除非需要，否则不会连接后续序列。但是当需要它们的元素时，即从 sequence-append 产生的序列被消耗得足够远时，就会产生与所有先前序列的长度总和成线性关系的时间成本。正确的？这就是它变慢的原因吗？

如果是这样，如何解决？（在这种情况下 append 的性能足够，但假设我真的需要一个结构，它至少是一个具有通常复杂性的 FIFO 队列。）在 racket 语言中是否有一个好的替代方案，没有 requireing 附加包（可能不可用，就像 Codewars 上的情况一样）？差异列表可能（很容易从头开始实施）？

Answer 1

我最终使用了明显的、迄今为止有意避免的：可变列表：

#lang racket
(provide sum-of-divided)

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

我还尝试了使用流的纯函数方法：

#lang racket
(provide sum-of-divided)

(define primes
  (letrec
    ([ps
      (stream*
        2
        (for*/stream
          ([i (in-naturals 3)]
           #:unless
             (for/or
               ([p ps])
               #:break (< i (sqr p))
               (= 0 (modulo i p))))
        i))])
    ps))

(define (sum-of-divided lst)
  (for/fold
    ([l lst]
     [r '()]
     #:result (reverse r))
    ([d primes])
    #:break (null? l)
    (values
      (remq*
        '(1)
        (map
          (λ (x)
             (let exhaust ([s x])
               (define q (/ s d))
               (if (integer? q)
                   (exhaust q)
                   s)))
          l))
      `(,@(for/fold
          ([a 0]
           [f #f]
           #:result
             (if f
                 `((,d ,a))
                 '()))
          ([n lst])
           (if (= 0 (modulo n d))
               (values (+ a n) #t)
               (values a f)))
        ,@r))))

令人惊讶的是，它总是超时，而上面的命令式从不超时。相信 Racket 实现者至少同样关心性能和功能风格，我很失望。

球拍中的队列？

Queues in Racket?

performance

queue

concatenation

racket

lazy-evaluation