TA貢獻1796條經(jīng)驗 獲得超7個贊
它定義了一個生成器- 一個稱為“ sieve”的流轉(zhuǎn)換器，
Sieve s = while( True ): p := s.head s := s.tail yield p -- produce this s := Filter (nomultsof p) s -- go nextprimes := Sieve (Nums 2)
它使用等效于匿名函數(shù)的咖喱形式
nomultsof p x = (mod x p) /= 0
兩個Sieve和Filter是數(shù)據(jù)構造與操作的內(nèi)部狀態(tài)和通過值參數(shù)傳遞語義。
在這里，我們可以看到，最突出的問題這段代碼是不是，重復不在于它使用審判庭從工作序列篩選出數(shù)倍，而它可以直接將它們找出來，通過在增量計數(shù)p。如果我們要用后者代替前者，那么生成的代碼將仍然具有極高的運行時復雜性。
不，它最明顯的問題是它過早地將其Filter放在工作序列的頂部，只有在輸入中看到素數(shù)平方之后才真正應該這樣做。結(jié)果，與實際需要的相比，它創(chuàng)建了s 的二次數(shù)。它創(chuàng)建的s 鏈太長，甚至根本不需要它們中的大多數(shù)。FilterFilter
過濾器的創(chuàng)建被推遲到適當?shù)臅r候的更正版本是
Sieve ps s = while( True ): x := s.head s := s.tail yield x -- produce this p := ps.head q := p*p while( (s.head) < q ): yield (s.head) -- and these s := s.tail ps := ps.tail -- go next s := Filter (nomultsof p) s primes := Sieve primes (Nums 2)
primes = sieve primes [2..] sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0] where (p:pt) = ps (h,t) = span (< p*p) xs
rem此處使用而不是，mod因為在某些口譯員中它可以更快，并且無論如何這些數(shù)字都是正數(shù)。
通過以問題大小點的運行時間來衡量算法的局部增長階次，如，我們得到第一個，而第二個正好在上面（以產(chǎn)生的素數(shù)計）。t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n
只是為了澄清一下，可以用這種（虛構的）語言定義缺少的部分，就像
Nums x = -- numbers from x while( True ): yield x x := x+1Filter pred s = -- filter a stream by a predicate while( True ): if pred (s.head) then yield (s.head) s := s.tail
另見。
更新：奇怪的是，根據(jù)AJT Davie在1992年Haskell的書中，David Turner的1976 SASL手冊中的第一個代碼實例，
primes = sieve [2..] sieve (p:nos) = p : sieve (remove (multsof p) nos)
實際上接受并實現(xiàn)了兩 對實現(xiàn)-一對用于此問題的試驗部門篩網(wǎng)，另一對用于通過計算直接減去每個素數(shù)的倍數(shù)（也就是真正的Eratosthenes篩子）的有序去除（兩者都是當然不推遲）。在Haskell，removemultsof
multsof p n = rem n p==0 remove m xs = filter (not . m) xs multsof p = [p*p, p*p+p..] remove m xs = diff xs m
（如果他只是推遲選擇實際的實現(xiàn)方式...）
至于推遲的代碼，在帶有“列表模式” 的偽代碼中，
primes = [2, ...sieve primes [3..]] sieve [p, ...ps] [...h, p*p, ...nos] = [...h, ...sieve ps (remove (multsof p) nos)]
舉報