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 与计算交错。此外，它会增加内存压力（如果您的内存接近极限，这可能很重要）并大大降低缓存一致性。

我编写了以下小脚本，该脚本在我的/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)，这更进一步解释了性能差异。我终于满足于我们找到了核心原因。