在其过滤过程中使用局部状态突变的方案中的 Eratosthenes 筛选 [英] Sieve of Eratosthenes in Scheme using mutation of local state in its filtering procedure

问题描述

虽然回答最近的问题我想出了以下代码，实现了 Eratosthenes 筛的变体，反复剔除初始 2...n 序列，尽可能早地停止:

While answering a recent question I came up with the following code, implementing a variant of the sieve of Eratosthenes, repeatedly culling the initial 2...n sequence, stopping as early as possible:

(define (sieve2 n)
  (let ((ls (makelist n)))
    (let loop ((ls ls) 
               (next (sievehelper2 ls n)))
      (if (null? next)
          ls
          (cons (car ls) 
                (loop next (sievehelper2 ls n)))))))

(define (sievehelper2 list n)
  (if (> (* (car list) (car list)) n)
      '()
      (filterfunc (not-divisible-by (car list)) 
                  list)))

(define filterfunc filter)

(define (not-divisible-by n)
  (let ((m n))   ; the current multiple of n
    (lambda (x)
      (let ((ret (not (= x m))))
        (if (>= x m) (set! m (+ m n)) #f)
        ret))))

(define (makelist n)
  (range 2 (+ 1 n)))

在 Racket 中运行 (sieve 50) 会得到 '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47).

Running (sieve 50) in Racket results in '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47) though.

它有一些错误，这在结果中很明显，我没有立即看到它在哪里.这可能是我犯的一些愚蠢的错误，也可能是所使用的算法部分的一些根本性错位的表达，我不能说哪个是哪个.

It has some error in it, as is obvious in the results, and I don't immediately see where it is. It can either be some stupid mistake that I made or an expression of some fundamental misalignment of the algorithmic pieces in use, and I can't say which is which.

请问这是什么错误，如何修复?

What is that error and how can it be fixed, please?

明确地说，我不是要求对代码进行算法改进，我希望计算结构在其中表达的保留.此外，我在链接问题中看到的挑战是设计缺失的功能——并改变 sieve 本身——同时保持 sievehelper 功能作为给定，在这个问题的代码中明显有一些小的改动.这也是我想在这个问题中提出的要求.

To be clear, I'm not asking for algorithmic improvements to the code, I want the computational structure expressed in it preserved. Moreover, the challenge that I saw in the linked question was to devise the missing functions -- and alter the sieve itself -- while keeping the sievehelper function as given, up to some minor alterations as evident in this question's code. This is also a requirement I'd like to make in this question.

我对 sieve2 中对 sievehelper2 的两次调用也不满意.也许以某种方式修复代码结构也会使错误消失?

I'm also not happy with the two calls to sievehelper2 in sieve2. Perhaps fixing the code structure somehow will also make the error go away?

推荐答案

问题出在这里:

(loop next (sievehelper2 ls n))

列表ls在这次调用中被第二次传递给sievehelper2；但是sievehelper2需要处理next:

The list ls is passed for a second time to sievehelper2 in this call; but sievehelper2 needs to process next:

(define (sieve2 n)
  (let ((ls (makelist n)))
    (let loop ((ls ls) 
               (next (sievehelper2 ls n)))
      (if (null? next)
          ls
          (cons (car ls) 
                (loop next (sievehelper2 next n)))))))

通过此更改，筛子似乎按预期工作:

With this change, the sieve seems to work as expected:

sieve2.rkt> (sieve2 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

去掉sieve2中的外层let，只调用一次sievehelper2，可能有助于代码清晰:

It may help code clarity to get rid of the outer let in sieve2, and make only one call to sievehelper2:

(define (sieve3 n)
  (let loop ((filtered '())
             (candidates (makelist n)))
    (if (null? candidates)
        filtered
        (cons (car candidates) 
              (loop (cdr candidates) (sievehelper2 candidates n))))))

这也按预期工作:

sieve2.rkt> (sieve3 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

---

一些改进

我对上面的 sieve3 不满意.虽然我认为只显示一个对 sievehelper2 的调用有助于清晰，但仍然可以使代码更加清晰.

---

Some Improvements

I am not happy with sieve3 above. While I think that showing only one call to sievehelper2 aids clarity, the code could still be made more clear.

最初 sieve3 有一个 result 变量，此后已更改为 filtered.result 描述性不够，无法提供帮助，我认为这种变化是一种改进；毕竟，filtered 确实包含过滤candidates 列表的结果.虽然，filtered 的初始值在这个意义上是没有意义的，因为 candidates 还没有被过滤.

Initially sieve3 had a result variable which has since been changed to filtered. result was not descriptive enough to be helpful, and I think that the change is an improvement; after all, filtered does contain the results of filtering the candidates list. Although, the initial value of filtered is meaningless in that sense because candidates has not yet been filtered.

更让我烦恼的是结构:

(cons (car candidates) 
      (loop (cdr candidates) (sievehelper2 candidates n)))

不是很清楚(汽车候选)是被收集的素数，(cdr候选)是部分过滤的候选列表，或者目标是将在完全过滤的候选列表中找到的 cons 素数.

It is not very clear that (car candidates) is a prime that is being collected and that (cdr candidates) is the partially filtered list of candidates, or that the goal is to cons primes which have been found onto a fully filtered list of candidates.

这是 sieve 的改进版本，它使用显式累加器 primes 来保存遇到的素数.当 sievehelper2 返回一个空列表时，我们知道 filtered 列表已经完全过滤了非质数.最后，找到的素数和完全过滤的候选列表可以附加在一起并返回(但不能在反转找到的素数列表之前，因为最近找到的素数被放在素数的前面).这个 sieve 过程还具有尾递归的优点:

Here is an improved version of sieve that uses an explicit accumulator primes to save prime numbers as they are encountered. When sievehelper2 returns an empty list, we know that the filtered list has been fully filtered of non-prime numbers. Finally, the found primes and the fully filtered list of candidates can be appended together and returned (but not before reversing the list of found primes, since the most recently found primes are consed onto the front of primes). This sieve procedure also has the virtue of being tail-recursive:

(define (sieve n)
  (let loop ((primes '())
             (filtered (makelist n)))
    (let ((next (sievehelper2 filtered n)))
      (if (null? next)
          (append (reverse primes) filtered)
          (loop (cons (car filtered) primes)
                next)))))

sieve2.rkt> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

这篇关于在其过滤过程中使用局部状态突变的方案中的 Eratosthenes 筛选的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！