Rubyのセットに短い文字列を追加するのが遅い

Question

この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 

Answer 1

計算を実行する前にファイル全体を1度読み込むと、IOが計算でインターリーブされないようになります。さらに、メモリの使用量が増えます（メモリの限界に近づいている場合には重要な可能性があります）。cache coherencyを大幅に削減します。

私は私の/usr/share/dict/wordsファイルに0.3秒で実行し、次の小さなスクリプトを書いた - メガバイト未満、やや興味深いものにするのに十分な、まだ大：あなたのプログラムがまだ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 

後で、私はあきらめた。

主な違いは、私が組み込みのイテレータを使用して、バッファに少量のファイル（たぶん4k〜16k）を読み込み、繰り返し実行するたびに特定の文字を渡すことです。これにより、同じ少量のメモリが何度も再利用され、CPUの比較的小さなキャッシュラインがデータ全体を格納できるようになります。

Iは、文字列のサブスクリプト対each_charに主に速度差を単離することができた小さなテストケースで編集

。 Jörg points out that string subscripting is an O(N) operation - UTF-8文字列は、期待されるように単純に乗算によってインデックス付けすることができないため、最初からN番目の文字を見つけることを意味します。したがって、あなたのアプローチはO（N^2）であり、私のものはO（N）であり、はがパフォーマンスの違いを説明するまでにさらに進んでいます。私は最終的に私たちが中心的な原因を理解したことに満足しています。