在Ruby中向一个集合添加短字符串很慢

Question

我正在尝试使用这个Ruby代码从我的utf-8法语词典文件中提取所有独特的字符.字典是3.7 MB.由于某种原因,它需要我的体面的计算机大约半小时执行.有任何想法吗？

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

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

Answer 1

在对其执行任何计算之前一次性读取整个文件可防止IO与计算交错.此外,它会增加内存压力(如果你的内存接近极限,则可能很重要)并大大降低缓存一致性.

我写了下面的小脚本,它在我的/usr/share/dict/words文件上执行了0.3秒- 不到一兆字节,但仍然足够大,有点有趣:

$ 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的相对较小的缓存行存储整个数据.

编辑

通过一个小测试用例,我能够将速度差异主要与each_charvs字符串子脚本隔离开来.Jörg指出字符串下标是一个O(N)操作 - 因为UTF-8字符串不能像人们预期的那样通过乘法简单地索引,找到第N个字符意味着从头开始.因此,你的做法是O(N ^ 2)和我只是O(N),并认为更进了很多进一步解释的性能差异.我终于满足于我们找出了核心原因.