Concurrent Clean : L.L.Ring : キミならどう書く 2.0 - ROUND 1 - 高速化編

[id:lethevert:20060616:p2] : 素直な回答
[id:lethevert:20060617:p1] : 頭部非ボックス化正格リスト
[id:lethevert:20060617:p2] : gccとの速度比較
ここまで、コードの外形には触れずにいましたが、コードの外形を変えて高速化してみましょう。

Start = last $ takeWhile ((>=) 10000) primes

primes = ps [2..]
  where
    ps [n:nr] = [n: ps $ filter (\x = (x rem n) <> 0) nr]

ポイントは２つ。

比較の順序を変更
比較の回数を減らす

１つ目は、最初の回答では、大きな素数から順に比較しているところを改善するということです。最もフィルター効率の高い素数から順に比較していく方が、比較回数を減らすことができるということを考えると、小さな素数から順に比較していく方が効率がよいということです。小さな素数から比較すれば、ある数が素数ではないことが分かるために必要な平均比較回数は、数が大きくなってもあまり増えない（たとえば、半分の数は、２の倍数であるので、１回の比較で素数ではないことが分かる）けれど、大きな素数から比較すると、数が大きくなると発見された素数の数の比例に近い勢いで比較回数が増加するのです。
２つ目は、比較すべき素数は、素数判定したい数の平方根より小さい素数までの比較で十分で、これより大きい素数で割り切れることはないというところを改善するということです。sqrt関数を使うのは効率が悪いので、素数の２乗と対象の数を比較します。また、素数の２乗を毎回計算するのではなく、計算後の値を記憶させておきます。また、素数とその２乗の値をタプルに持たせるよりも、正格レコードに持たせるほうが効率的です。

Start = last $ takeWhile ((>=) 10000) primes

::PrimeRecord = { p :: !Int, sq :: !Int }

primes = [p \\ {p} <- ps]
  where
    ps = [{p=2, sq=4}: [{p=n, sq=n*n} \\ n <- [3..] | isPrime n]]
    isPrime n = each ps
      where
        each [{p,sq}:pr]
            | sq < n = (0 <> n rem p) && each pr
                     = True

では、速度比較を。
比較対象は、gccの次のプログラムです。先のものから、アルゴリズムをCleanのプログラムにあわせて修正しています。

#include <stdio.h>

#define LEN 10000

int primes[LEN];
int primesSq[LEN];

int main(int argc, char** argv) {
	int i, j, k, b;
	j = 0;
	for (i=2; i<LEN; ++i) {
		b = 1;
		for (k=0; k<j; ++k) {
			if (primesSq[k] >= i) {
				break;
			}
			if (i % primes[k] == 0) {
				b = 0;
				break;
			}
		}
		if (b) {
			primes[j] = i;
			primesSq[j++] = i*i;
		}
	}
	
	printf("%d", primes[j-1]);
}

まず、「n=10,000」で。

gcc

$ time ./primes_c.exe
9973
real    0m0.084s
user    0m0.030s
sys     0m0.080s

Clean 高速版

$ time ./PrimesQuick.exe
9973

real    0m0.084s
user    0m0.040s
sys     0m0.030s

この時点で、互角です。
次、「n=1,000,000」で。

gcc

$ time ./primes_c.exe
999983
real    0m1.163s
user    0m1.051s
sys     0m0.050s

Clean 高速版

$ time ./PrimesQuick.exe
999983

real    0m1.601s
user    0m0.030s
sys     0m0.030s

ちょっと差がついてきたかな？
それでは、Cleanの方をさらに高速化するために、リストを頭部正格非ボックス化配列に変更します。

module PrimesQuickStrict

import StdEnv, OptEnv

Start = Last ls
  where
    ls :: [#Int]
    ls = TakeWhile ((>=) 1000000) primes

::PrimeRecord = { p :: !Int, sq :: !Int }

primes = [#p \\ {p} <|- ps]
  where
    ps = [#{p=2, sq=4}: [#{p=n, sq=n*n} \\ n <|- [#3..] | isPrime n]]
    isPrime n = each ps
      where
        each [#{p,sq}:pr]
            | sq < n = (0 <> n rem p) && each pr
                     = True

結果

Clean 高速版（頭部正格非ボックス化配列）

$ time ./PrimesQuickStrict.exe
999983

real    0m1.201s
user    0m0.010s
sys     0m0.040s

gccと互角ですね。
では、「n=10,000,000」では？

gcc

$ time ./primes_c.exe
9999991
real    0m20.469s
user    0m19.758s
sys     0m0.090s

Clean 高速版（頭部正格非ボックス化配列）

$ time ./PrimesQuickStrict.exe
9999991

real    0m22.655s
user    0m0.020s
sys     0m0.050s

やはり互角。
では、昨日あきらめた1,000,000番目の素数を計算してみます。

gcc

$ time ./primes_c.exe
15476717
real    0m35.950s
user    0m35.030s
sys     0m0.140s

Clean 高速版（頭部正格非ボックス化配列）

$ time ./PrimesQuickStrict.exe
15476717

real    0m36.504s
user    0m0.010s
sys     0m0.050s

余裕で計算完了できました。

- - -

せっかくなので、TBしとこ