5

この Ruby コードを使用して、utf-8 フランス語辞書ファイルから一意の文字をすべて抽出しようとしています。辞書は 3.7 MB です。何らかの理由で、まともなコンピューターで実行するのに約30分かかります。何か案は？

c = Set.new
f = open "dict"
s = f.read
f.close

for i in 0..s.length-1
    c << s[i]
end
4

1 に答える 1

5

計算を実行する前にファイル全体を一度に読み取ると、IO が計算にインターリーブされるのを防ぐことができます。さらに、メモリ プレッシャーが増加し (メモリの限界近くで実行している場合は潜在的に重要です)、キャッシュの一貫性が大幅に低下します。

私は次の小さなスクリプトを書きました。これは私のファイルで 0.3 秒で実行され/usr/share/dict/wordsます -- 1 メガバイト未満ですが、少し興味深いほど十分な大きさです。

$ cat /tmp/set.rb 
#!/usr/bin/ruby

require 'set'

c = Set.new
f = open "/usr/share/dict/words"

f.each_char do |char|
    c << char
end

p c
$ time /tmp/set.rb 
#<Set: {"A", "\n", "'", "s", "B", "M", "C", "T", "H", "I", "D", "S", "O", "L", "P", "W", "Z", "a", "c", "h", "e", "n", "l", "i", "y", "r", "o", "b", "d", "t", "u", "j", "g", "m", "p", "v", "x", "f", "k", "z", "w", "q", "ó", "ü", "á", "ö", "ñ", "E", "F", "R", "U", "N", "G", "K", "é", "ä", "Q", "è", "V", "J", "X", "ç", "ô", "í", "Y", "â", "û", "ê", "å", "Å"}>

real    0m0.341s
user    0m0.340s
sys 0m0.000s

あなたのプログラムは 1 分後にまだ実行されていたので、あきらめました。

主な違いは、組み込みの反復子を使用して少量のファイル (おそらく 4k-16k) をバッファーに読み込み、反復ごとに特定の文字を渡すことです。これにより、同じ少量のメモリが何度も再利用され、CPU の比較的小さなキャッシュ ラインにデータ全体を格納できるようになります。

編集

小さなテストケースで、速度の違いを主にeach_char対文字列の添え字に分離することができました。Jörg は、文字列の添字付けは O(N) 演算であると指摘しています。UTF-8 文字列は、予想されるように乗算によって単純にインデックス付けすることはできないため、N 番目の文字を見つけることは最初から開始することを意味します。したがって、あなたのアプローチは O(N^2) であり、私のアプローチは単なる O(N) であり、それはパフォーマンスの違いをさらに説明することになります。根本的な原因を突き止めたことに、ようやく満足しています。

于 2012-06-13T00:41:47.260 に答える