performance - Racket 流比自定义流慢？

Question

我实现了一个简单但效率不高的埃拉托色尼筛。一次用于内置 Racket 流，一次用于自定义流。对我来说唯一已知的区别是内置流正在评估第一个项目，而不是在 build 中。在评估两个实现的前 1000 个素数时，自定义流的运行速度快 10-20 倍。有什么解释吗？

(define (integers-starting-from-stream n)
  (stream-cons n (integers-starting-from-stream (+ n 1))))

(define (stream-limit s limit)
    (when (not (= limit 0)) (stream-limit (stream-rest s) (- limit 1))))

(define x (integers-starting-from-stream 2))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (sieve s)
  (stream-cons
   (stream-first s)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-first s))))
           (stream-rest s)))))
(time (stream-limit (sieve x) 1000))

还是我错过了影响性能的东西？

(define-syntax-rule (s-delay exp)
  (λ() exp))

(define (s-force delayedObject)
  (delayedObject))

(define empty-s 'S-EMPTY-STREAM)

(define (s-empty? s)
  (eq? s empty-s))

(define (s-first s)
  (car s))

(define (s-rest s)
  (s-force (cdr s)))

(define-syntax-rule (s-cons a b)
  (cons a (s-delay b)))
(define (s-filter p s)
  (cond ((s-empty? s) empty-s)
        ((p (s-first s))
         (s-cons (s-first s)
                 (s-filter p (s-rest s))))
        (else (s-filter p (s-rest s)))))
;;;;;;;;;;;;;;;;;;;;
(define (divisible? x y)
  (= (remainder x y) 0))

(define (integers-starting-from n)
  (s-cons n (integers-starting-from (+ n 1))))

(define (s-limit s limit)
    (when (not (= limit 0)) (s-limit (s-rest s) (- limit 1))))

(define x (integers-starting-from 2))

(define (sieve s)
  (s-cons (s-first s) (sieve (s-filter (lambda(x) (not (divisible? x (s-first s)))) (s-rest s)))))
(time (s-limit (sieve x) 1000))

Answer 1

这是一个观察:

使用 integers-starting-from-stream 的版本打印数字
当它们生成时:

(define (integers-starting-from-stream n)
  (stream-cons n
               (begin
                 (display (~a n " "))
                 (integers-starting-from-stream (+ n 1)))))

同样:

(define (integers-starting-from n)
  (s-cons n
          (begin (display (~a n " "))
                 (integers-starting-from (+ n 1)))))

我们可以测试:

(collect-garbage) (collect-garbage) (collect-garbage)
(time (stream-limit (sieve x) 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(time (s-limit (s-sieve s-x) 10))

我们观察到流版本打印了从 2 到 51 的数字
其中 s-version 打印了 2 到 30 的数字。

流版本生成的列表几乎是两倍大小。

这是流版本比自定义版本慢的第一个(也是最重要的)原因。

流版本较慢的第二个原因是流版本缓存了 stream-first 的结果.当元素的计算速度很慢时，缓存通常会更快。

(define (integers-starting-from-stream n)
  (stream-cons (begin (sleep 1) n)
               (integers-starting-from-stream (+ n 1))))

和

(define (integers-starting-from n)
  (s-cons (begin (sleep 1) n)
          (integers-starting-from (+ n 1))))

然后运行:

(collect-garbage) (collect-garbage) (collect-garbage)
(define x (integers-starting-from-stream 2))
(time (stream-limit x 10))
(time (stream-limit x 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(define s-x (integers-starting-from 2))
(time (s-limit s-x 10))
(time (s-limit s-x 10))