ruby - 将短字符串添加到 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 与计算交错。此外，它会增加内存压力(如果您的内存接近极限，这可能很重要)并大大减少 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 相对较小的缓存行来存储全部数据。

编辑

通过一个小的测试用例，我能够将速度差异主要归因于 each_char 与字符串子脚本。 Jörg points out that string subscripting is an O(N) operation -- 因为 UTF-8 字符串不能像人们预期的那样简单地通过乘法索引，找到第 N 个字符意味着从头开始。因此，您的方法是 O(N^2) 而我的只是 O(N)，that 更进一步解释了性能差异。我终于对我们找出核心原因感到满意。