Решето Эратосфена в схеме, использующее мутацию локального состояния в процедуре фильтрации

Пока отвечая на недавний вопрос Я придумал следующий код, реализующий вариант решета Эратосфена, многократно отбрасывающий начальную последовательность 2...n, останавливаясь как можно раньше:

(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)))

Однако запуск (sieve 50) в Racket приводит к '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47).

В нем есть какая-то ошибка, что очевидно по результатам, и я не сразу вижу, где она. Это может быть либо какая-то глупая ошибка, которую я сделал, либо выражение какой-то фундаментальной несогласованности используемых алгоритмических частей, и я не могу сказать, что есть что.

Подскажите, что это за ошибка и как ее исправить?

Чтобы было ясно, я не прошу алгоритмических улучшений кода, я хочу вычислительную структуру, выраженную в нем, сохранить. Более того, задача, которую я увидел в связанном вопросе, заключалась в том, чтобы разработать отсутствующие функции - и изменить саму sieve - при сохранении функции sievehelper как указано, вплоть до некоторых незначительных изменений, как видно из этого код вопроса. Это также требование, которое я хотел бы указать в этом вопросе.

Меня также не устраивают два обращения к sievehelper2 в sieve2. Возможно, исправление структуры кода каким-либо образом также устранит ошибку?


primes scheme racket sieve-of-eratosthenes sieve
person Will Ness    schedule 24.02.2021    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Проблема здесь:

(loop next (sievehelper2 ls n))

Список ls передается во второй раз в sievehelper2 в этом вызове; но sievehelper2 нужно обработать 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)))))))

С этим изменением сито, кажется, работает так, как ожидалось:

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

Чтобы упростить код, избавьтесь от внешнего let в sieve2 и сделайте только один вызов 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 способствует ясности, код все же можно было бы сделать более понятным.

Первоначально sieve3 имела переменную result, которая с тех пор была изменена на filtered. result не был достаточно описательным, чтобы быть полезным, и я думаю, что это изменение является улучшением; в конце концов, filtered содержит результаты фильтрации списка candidates. Хотя начальное значение filtered в этом смысле бессмысленно, потому что candidates еще не отфильтровано.

Меня больше смущает конструкция:

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

Не очень ясно, что (car candidates) — это собираемое простое число, а (cdr candidates) — это частично отфильтрованный список кандидатов, или что цель состоит в том, чтобы объединить найденные простые числа в полностью отфильтрованный список кандидатов.

Вот улучшенная версия sieve, в которой используется явный аккумулятор primes для сохранения простых чисел по мере их появления. Когда sievehelper2 возвращает пустой список, мы знаем, что список filtered был полностью отфильтрован от непростых чисел. Наконец, найденные простые числа и полностью отфильтрованный список кандидатов могут быть добавлены вместе и возвращены (но не раньше, чем инвертировать список найденных простых чисел, поскольку самые последние найденные простые числа помещаются в начало primes). Эта sieve процедура также обладает преимуществом хвостовой рекурсии:

(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)
person ad absurdum    schedule 24.02.2021
comment
Ваш предыдущий комментарий теперь удален, но я тоже не был в восторге от sieve3 в своем ответе. До сих пор у меня не было времени что-либо с этим сделать; Я добавил несколько комментариев о проблемах с ясностью кода и, как мне кажется, об улучшенном выражении процедуры sieve. - person ad absurdum; 25.02.2021
comment
Я удалил свой ответ с указанными в нем причинами. большое спасибо за ответ! - person Will Ness; 28.02.2021