如何在ChezScheme中统计每次素数查找的耗时？

我正在MacOS上使用Chez Scheme完成SICP的练习1.22。查阅相关文档后，我得知可以使用time过程获取程序的CPU运行时间，但由于Chez Scheme没有教材中提供的runtime原语，无法直接使用教材代码。不过我认为该练习需要统计每次找到素数时的单次耗时，而time过程只能统计整个程序的总耗时，无法满足需求。

以下是我的素数查找代码：

(define (search-for-primes lb amt)
    (search-iter lb 0 amt))

(define (search-iter lb fd amt)
    (cond ((= fd amt) (display "all found"))
        ((not (prime? lb)) (search-iter (+ lb 1) fd amt))
        (else 
            (display "found prime:")
            (display lb)
            (newline)
            (search-iter (+ lb 1) (+ fd 1) amt)
            )))

; now to get the time elapse
(time (search-for-primes 1000 3))

素数判断代码如下：

(define (smallest-divisor n)
    (find-divisor n 2))

(define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (square x)
    (* x x))

(define (divides? a b )
    (= (remainder b a) 0))

(define (prime? n)
    (= (smallest-divisor n) n))

请问是否有方法可以统计每次找到素数时的耗时？

解决方法 #

Chez Scheme提供了直接获取时间的原语，完全可以实现单个素数判断的计时需求，不需要依赖只能统计总耗时的time过程。你可以用cpu-time（获取CPU耗时毫秒数）来模拟教材中runtime原语的功能，它返回从程序启动到当前的CPU时间，两次调用的差值就是单次判断的耗时。

修改方案1：封装计时测试过程 #

先定义一个带计时的素数测试过程，把判断和计时逻辑整合：

(define (timed-prime-test n)
  (let ((start (cpu-time)))
    (if (prime? n)
        (begin
          (display "found prime: ")
          (display n)
          (display " | 耗时: ")
          (display (- (cpu-time) start))
          (display " ms")
          (newline)
          #t) ; 返回true表示找到素数
        #f))) ; 返回false表示未找到

然后修改查找迭代过程，调用这个带计时的测试：

(define (search-iter lb fd amt)
  (cond ((= fd amt) (display "all found"))
        ((not (timed-prime-test lb)) (search-iter (+ lb 1) fd amt))
        (else (search-iter (+ lb 1) (+ fd 1) amt))))

; 调用测试
(search-for-primes 1000 3)

修改方案2：直接在迭代逻辑中添加计时 #

如果不想新增过程，也可以直接在原有的search-iter里修改else分支，在判断素数前后记录时间：

(define (search-iter lb fd amt)
  (cond ((= fd amt) (display "all found"))
        (else
         (let ((start (cpu-time)))
           (if (prime? lb)
               (begin
                 (display "found prime: ")
                 (display lb)
                 (display " | 耗时: ")
                 (display (- (cpu-time) start))
                 (display " ms")
                 (newline)
                 (search-iter (+ lb 1) (+ fd 1) amt))
               (search-iter (+ lb 1) fd amt))))))

说明 #

• cpu-time统计的是程序实际占用的CPU时间，不会受到系统其他进程的干扰，和教材中runtime的统计逻辑一致，适合用来做算法耗时分析。
• 如果需要统计实时流逝时间（包括系统等待时间），可以替换成real-time-clock，它返回的是从程序启动到当前的实时毫秒数。

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