4

いくつかのオイラーの苦労の一環として、因数分解ホイールを使用してエラトステネスのふるいをコーディングしようとしています。これまでの私のコードは次のとおりです。

(defun ring (&rest content)
"Returns a circular list containing the elements in content.
 The returned list starts with the first element of content."
   (setf (cdr (last content)) content))

(defun factorization-wheel (lst)
"Returns a circular list containing a factorization 
 wheel using the list of prime numbers in lst"
   (let ((circumference (apply #'* lst)))
     (loop for i from 1 to circumference
           unless (some #'(lambda (x) (zerop (mod i x))) lst)
             collect i into wheel
           finally (return (apply #'ring 
                             (maplist 
                                 #'(lambda (x) ; Takes exception to long lists (?!)
                                     (if (cdr x)
                                         (- (cadr x) (car x))
                                         (- circumference (car x) -1)))
                                 wheel))))))

(defun eratosthenes (n &optional (wheel (ring 4 2)))
"Returns primes up to n calculated using
 a Sieve of Eratosthenes and a factorization wheel"
   (let* ((candidates (loop with s = 1
                            for i in wheel
                            collect (setf s (+ i s))
                            until (> s n))))
       (maplist #'(lambda (x) 
                    (if (> (expt (car x) 2) n)     
                        (return-from eratosthenes candidates))
                    (delete-if 
                        #'(lambda (y) (zerop (mod y (car x)))) 
                        (cdr x))) 
                candidates)))

ホイールが 6 要素よりも長い場合、次の結果が得られました。理由がよくわかりませんでした：

21 > (factorization-wheel '(2 3 5 7 11 13))
(16 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 ...)
21 > (factorization-wheel '(2 3 5 7 11 13 17))
> Error: Too many arguments.
> While executing: FACTORIZATION-WHEEL, in process listener(1).

それ以外の場合、アルゴリズムは正常に機能しているようで、要素が 6 以下のホイールで素数を生成します。

長いリストが渡されると、明らかにapply、またはring鼻を上げます。

しかし、リストは単一の引数として数えるべきではないでしょうか? 私は完全に困惑していることを認めます。どんな入力でも大歓迎です。

4

1 に答える 1

8

ANSI Common Lisp では、関数に渡すことができる引数の最大数を実装で制限できます。この制限はcall-arguments-limitによって指定され、50 まで小さくすることができます。

連想プロパティ ( +、 、およびその他) に従う代数群演算子のように動作する関数の場合、関数をバイナリとして扱いながら、listを使用して入力リストをデシメーションすることにより、制限を回避できます。reduce

たとえば、数字の大きなリストを追加するには:(reduce #'+ list)ではなく(apply #'+ list).

注意事項reduce

Common Lisp ではreduce、リストが空であっても動作するように見えます。これを提供する言語は他にほとんどなく、実際にはreduce. しかし、+を使用する(reduce #'+ nil)と、 と同じように、ゼロを計算できます(apply #'+ nil)。

何故ですか？関数は引数なしで呼び出すことができるため、+引数なしで呼び出すと、加法群の恒等要素が生成されます: 0. これはreduce関数と一致します。

他の一部の言語では、foldorreduce関数に初期シード値 ( など0) を指定するか、空でないリストを指定する必要があります。どちらも指定されていない場合は、エラーになります。

Common Lispreduceは、空のリストと no が指定された場合:initial-value、引数なしでカーネル関数を呼び出し、戻り値を初期値として使用します。その値が唯一の値 (リストは空) であるため、その値が返されます。

左端の引数に特別なルールがある関数に注意してください。例えば：

(apply #'- '(1)) -> -1  ;; same as (- 1), unary minus semantics.

(reduce #'- '(1)) -> 1  ;; what?

何が起こっているかとreduceいうと、 に要素が 1 つのリストが与えられると、関数を呼び出さずに要素を返すだけです。

基本的には、上記の数学的仮定に基づいており、 no:initial-valueが指定されている場合、は をサポートすることfが期待されます。これは、シングルトン リスト を削減する際の初期値として使用されます。(f) -> iif(f i x) -> x(reduce #'f (list x)) -> (f (f) x) -> (f i x) -> x

関数はこれらの-規則に従いません。(- a 0)は「 からゼロを引く 」を意味するaため、 が得られますaが、(- a)は の加法逆でありa、おそらく純粋に実用的な表記上の理由によるものです (つまり、 Lisp プログラマー(- 0 a)に符号を反転させるためだけに書かせず、 と の下で-より一貫した動作をさせるためです) 。 . 関数は、引数なしで呼び出すこともできません。reduceapply-

数値のリストを取り、それらすべてを値から減算したい場合x、そのパターンは次のとおりです。

(reduce #'- list-of-numbers :initial-value x)
于 2015-12-10T06:06:56.617 に答える