TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超7個(gè)贊
它定義了一個(gè)生成器- 一個(gè)稱為“ 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
兩個(gè)Sieve和Filter是數(shù)據(jù)構(gòu)造與操作的內(nèi)部狀態(tài)和通過(guò)值參數(shù)傳遞語(yǔ)義。
在這里，我們可以看到，最突出的問題這段代碼是不是，重復(fù)不在于它使用審判庭從工作序列篩選出數(shù)倍，而它可以直接將它們找出來(lái)，通過(guò)在增量計(jì)數(shù)p。如果我們要用后者代替前者，那么生成的代碼將仍然具有極高的運(yùn)行時(shí)復(fù)雜性。
不，它最明顯的問題是它過(guò)早地將其Filter放在工作序列的頂部，只有在輸入中看到素?cái)?shù)平方之后才真正應(yīng)該這樣做。結(jié)果，與實(shí)際需要的相比，它創(chuàng)建了s 的二次數(shù)。它創(chuàng)建的s 鏈太長(zhǎng)，甚至根本不需要它們中的大多數(shù)。FilterFilter
過(guò)濾器的創(chuàng)建被推遲到適當(dāng)?shù)臅r(shí)候的更正版本是
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因?yàn)樵谀承┛谧g員中它可以更快，并且無(wú)論如何這些數(shù)字都是正數(shù)。
通過(guò)以問題大小點(diǎn)的運(yùn)行時(shí)間來(lái)衡量算法的局部增長(zhǎng)階次，如，我們得到第一個(gè)，而第二個(gè)正好在上面（以產(chǎn)生的素?cái)?shù)計(jì)）。t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n
只是為了澄清一下，可以用這種（虛構(gòu)的）語(yǔ)言定義缺少的部分，就像
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手冊(cè)中的第一個(gè)代碼實(shí)例，
primes = sieve [2..] sieve (p:nos) = p : sieve (remove (multsof p) nos)
實(shí)際上接受并實(shí)現(xiàn)了兩 對(duì)實(shí)現(xiàn)-一對(duì)用于此問題的試驗(yàn)部門篩網(wǎng)，另一對(duì)用于通過(guò)計(jì)算直接減去每個(gè)素?cái)?shù)的倍數(shù)（也就是真正的Eratosthenes篩子）的有序去除（兩者都是當(dāng)然不推遲）。在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
（如果他只是推遲選擇實(shí)際的實(shí)現(xiàn)方式...）
至于推遲的代碼，在帶有“列表模式” 的偽代碼中，
primes = [2, ...sieve primes [3..]] sieve [p, ...ps] [...h, p*p, ...nos] = [...h, ...sieve ps (remove (multsof p) nos)]
舉報(bào)