import List import Data.IntSet n = 7000 a = [i + j | i <- [1..n], j <-[1..n]] --b = List.nub $ List.sort a // メモリ莫迦食いで目茶遅い 途中で落ちる b = Data.IntSet.toList $ Data.IntSet.fromList a main = do print $ length b
ううむ、複雑に考えすぎではないでしょうか…。fib=1:1:... は単にリストを作って変数fibに持っている式なので、素直に動かすと全リストが保持されます。たまたま１回しか使わないならば残す必要がないので最適化で消えるだけで。そうなのか. リストの要素の遅延評価に何か多大なものを期待しすぎてたのかな. 必要になるまで作られない(と強調されていることが多い)のだから, 逆に必要なくなれば(要素ごとに)すぐ消えてしまうと思い込んでました. 今回の場合は(fibを2回使うまで)メモリ食ってなかったし. でも一般的に「必要ないなら」の判断は難しいからそういうわけにはいかないか(それはまさにGCだ).
なるほど, とするとMemoiseのfibのメモ化の答えの一つがfib = 1:1:...でもあるのか. ただし, n番目しか必要ない場合はリストを使うべきではないし, もちろん何度も計算が必要になる再帰呼び出しのfib n = fib(n - 1) + fib (n - 2)を使うべきでもないと. なんだ当たり前の結論だ. でもちまたのHaskellの解説はミスリーディングなのが多い気がする…(言い訳).
いやいやいや, でもHaskellの場合はループがないからリストを使うことが多いのに「普通は全部持つ」なんて言われてもあちこちで使う[1..]が全部メモリにもたれたらたまらんよなあ. 最適化で消えてくれるかもしれないけど, 全部保持してても文句言うなよだと困る気がする. まだ複雑に考えすぎ?
試したらそうだった.
cat t.hs f = [1..] main = do print $ f !! 100000000 --- >runghc t.hs t.hs: getMBlocks: VirtualAlloc MEM_COMMIT failed: The paging file is too small for this operation to complete. >ghc t.hs && main 100000001sumと一緒なんだな. わかったよ.
zipWith'::(a -> b -> c) -> [a] -> [b] -> [c] zipWith' f (x:xs) (y:ys) = ((f $! x) $! y):zipWith' f xs ys zipWith' _ _ _ = [] fib = 1:1:zipWith (+) fib (tail fib) fib' = 1:1:zipWith' (+) fib' (tail fib')
ベンチマーク(ghc -O3@core2duo 2.6GHz memory 2GB).
| fib | fib' | fib'' | ||||||
|---|---|---|---|---|---|---|---|---|
| !! n | foldl1' (+) | sum | !! n | foldl1' (+) | sum | !! n | sum | |
| 100000 | 0.88 | 0.41 | 0.42 | 1.30 | 0.41 | 0.39 | 0.22 | 0.41 |
| 200000 | 4.61 | 1.44 | 1.44 | 8.08 | 1.44 | 1.44 | 0.73 | 1.44 |
| 300000 | 12.91 | 3.14 | 3.14 | 24.23 | 3.14 | 3.14 | 1.59 | 3.14 |
| 400000 | 27.80 | 5.55 | 5.55 | 54.02 | 5.55 | 5.55 | 2.75 | 5.55 |
なかなかおもろい結果になりました. 勉強会に参加したときもzipWith'を作れば速くなるのでは, という意見があったのですがやってみるとちょうど2倍遅くなりました. 正格評価は関係なくて組み込みのzipWithとの差が出たのかなという感じです. あるいはこれでは正格評価になってなくて, もっとちゃんとしたzipWith'じゃないといけないのかもしれません. 私はわかりません.
[追記] kinabaさんに教えていただきました.
zipWith'' f (x:xs) (y:ys) = ((:) $! (f x y)) (zipWith'' f xs ys) fib'' = 1:1:zipWith'' (+) fib'' (tail fib'')とすべきだそうです. ありがとうございました. このfib''によるベンチマークは一番理解できる挙動になりました. というわけで上記zipWith'は間違いでした.
sumは今朝試しました. 初めてHaskellを触ったとき, sum [1..1000000]がこけてsumは使うまいと思ってたので試してなかったのですが, 意外なことに正格評価のfoldl1'と同じでした.
[追記] -O3オプションでコンパイルするとsumもfoldl1'なみの速度で計算するようになりました. このレベルでは同じようになるようです.
一つ想像するのはfibは二つ前ぐらいの値はやはりキャッシュされているのではないかということです. でないとfold1'やsumでO(n^2)はでないと思います. というわけでMemoiseの「fib 7のときにfib 5を2度計算してる」というのは違うんじゃないでしょうか(もちろん最適化の程度には依存しそうですけど).
[追記] 捨ててるか残してるかは(fib !! n)したあと(fib !! (n-1))すればわかるのでは?という疑問があがりました. で, 試してみると予想外の挙動を示しました.
なんと2倍ぐらいの時間がかかりました. じゃあキャッシュしてないのかと更にfib !! (n-2)も追加して3倍の処理時間を期待しましたが, 2倍のまま. メモリ使用量を見るとどうやら複数箇所のfib !! をかくとfibであろうと正格評価版のfib''であろうと全リストのメモリを保存しようとするようです. たとえばsumとfib!!を組み合わせても全リストを保持しようとしてるように見えました.
遅延/正格評価だけでなく, 値が再利用されるかどうかで, 時間使用量だけでなく空間使用量も変動する. したがって(2GBメモリの私のマシンでは) n = 400000のときはfib''版ですら2回値を取得できない. この挙動は読めないなあ.
A.
fib = 1:1:zipWith (+) fib (tail fib)
B.
fib = 1:1:[f n | n <- [2..]]
where f 0 = 0
f 1 = 1
f n = (fib !! (n-1)) + (fib !! (n-2))
C.
f (x, y) = (y, x + y)
fib = map fst (iterate f (1, 1))
D.
fib 0 = 1
fib 1 = 1
fib n = f n 1 1
where f 1 _ y = y
f n x y = f (n - 1) y (x + y)
E.
import Array
fib = array (0,n) ((0,1):(1,1):[(k, fib!(k-2)+fib!(k-1))| k<-[2..n]])
Aは定番. Bはtanakhさんの大昔のサンプル.
Cは自分で手続き型プログラムのを素直にiterateしてみた. Dは西尾さんところの. Eはtosさんの.
別にこれらの種別に他意はありません(勉強しようと検索してヒットしたのを並べてます).
テストは2種類.
| A1 | A2 | B1/B2 | C1 | C2 | D1 | D2 | E1 | E2 | |
|---|---|---|---|---|---|---|---|---|---|
| 100000 | 1.23 | 0.56 | x | 0.06 | 0.61 | 0.33 | x | 3.32 | 3.21 |
| 200000 | 6.69 | 1.97 | x | 1.28 | 2.00 | 1.01 | x | x | x |
| 300000 | 18.11 | 4.30 | x | 6.22 | 4.32 | 2.25 | x | x | x |
| 400000 | 38.78 | 7.55 | x | 17.43 | 7.57 | 3.81 | x | x | x |
まずn = 100000だと最後の方の一つの数値は20KBほどで, n = 0から単に数値を格納するだけで2GBいってしまうので明示的に領域を作ってしまうのはほぼアウトです.
n番目だけ求めるならDの専用関数を用意したものが流石に速いです. D2がこけてるのは[fib i | i<-[1..n]]が各iごとに計算するのですごいオーダーになってるからでしょう.
AとCではCの方がよさそうですが, オーダーがA1はO(n^2.4)ぐらいなのに対してC1はO(n^3.8)ぐらいあります. n = 800000だと逆転しそうですね. となるとAが一番よいという感じです. しかも面白いのはfoldl1'したときの数値(A2)がC2とほぼ同じで最速だということです. 逆にA1の方が遅いのが気持ち悪いです. なんとなく憶測ですがA2がこんだけ速くなるということはAの値を計算するときに少しはメモ化(あるいは一つ前の値の再利用)が行われているということではないでしょうか. A2がD2とオーダーがほぼ同じだというのもその傍証です. どうなんでしょうかね.
def get_primes(N):
primes = []
for i in range(2, N):
if all(i % p != 0 for p in primes):
primes.append(i)
yield i
print sum(get_primes(200000))
| Python | Haskell(コンパイル) | Hakell(インタプリタ) | C++(番外) | |
|---|---|---|---|---|
| 10000 | 0.17 | 0.06 | 1.27 | - |
| 50000 | 1.67 | 0.56 | 18.41 | - |
| 100000 | 5.59 | 2.36 | 70.52 | - |
| 200000 | 19.27 | 14.14 | 272.86 | - |
| 250000 | 28.92 | 25.36 | - | - |
| 300000 | 39.92 | 39.73 | - | - |
| 400000 | 67.20 | 77.00 | - | - |
| 2000000 | - | - | - | 0.08 |
| 4000000 | - | - | - | 0.13 |
| 8000000 | - | - | - | 0.27 |
primes = 2:[x | x <- [3..], all (\p -> x `mod` p /= 0) $ takeWhile(\i -> i * i <= x) primes] main = do print $ sum . takeWhile( < 2000000) $ primesPythonは上のコードのprimes.append(i)の直前にif i * i <= N:を追加する. もう一度ベンチ(但し上のベンチとはマシンが違うので数値の直接比較はできない).
| Python | Haskell(コンパイル) | Hakell(インタプリタ) | |
|---|---|---|---|
| 10000 | 0.38 | - | 0.78 |
| 50000 | 0.59 | - | 1.55 |
| 100000 | 0.92 | 0.42 | 2.78 |
| 200000 | 1.75 | 0.55 | 5.55 |
| 400000 | 3.44 | 0.81 | 12.28 |
| 800000 | 7.78 | 1.42 | 28.67 |
| 1000000 | 9.70 | 1.78 | 37.86 |
| 2000000 | 22.86 | 3.97 | 91.38 |
| 4000000 | 52.55 | 8.97 | - |
sieve [] = [] sieve (p:xs) = p:sieve[x | x <- xs, x `mod` p /= 0] sum $ sieve [2..2000000]だといつまで経っても終わらない. 待ってる間に10分弱で書いたC++なら一瞬なんだけどな.
#include <iostream>
#include <bitset>
#if defined(_MSC_VER) && (MSC_VER <= 1500)
typedef __int64 int64_t;
#else
#include <stdint.h>
#endif
const size_t N = 2000000;
typedef std::bitset<N> Table;
int main()
{
Table t;
t.flip();
t[0] = false;
t[1] = false;
for (size_t i = 2; i < N; i++) {
size_t m = i * 2;
while (m < N) {
t[m] = false;
m += i;
}
}
int64_t sum = 0;
for (size_t i = 0; i < N; i++) {
if (t[i]) {
sum += i;
}
}
std::cout << "sum=" << sum << std::endl;
}
sieveのオーダーはO(n^2)なんよね(それすら違ってる?). 単に係数が大きすぎるだけ?
仕方ないので他のやり方を考えるけど富豪的じゃないなあ.