如何用Ruby快速计算字符串中子字符串的出现次数

Question

我有一个文本文件大小为300MB，我想计算文件中每个10,000个子字符串的出现次数。我想知道如何快速做到这一点。

现在，我使用下面的代码：

content = IO.read("path/to/mytextfile") 
Word.each do |w| 
    w.occurrence = content.scan(w.name).size 
    w.save 
end 
 

字是ActiveRecord类。

我花了差不多1天时间完成计算。无论如何要做得更快？谢谢。

编辑1： 再次感谢您。我正在运行rails 2.3.9。 name字段表中包含我正在搜索的内容，并且它仅包含唯一值。而不是使用Word.each，我使用批次（每次1000行）加载。它应该有所帮助。

我用bpaulon的思想重新编写了整个代码。现在只需要几个小时就可以完成计数。

我异型新版本的代码，现在最大的时间成本计算方法是UTF8编码支持的字符串截断码

def truncate(n) 
    self.slice(/\A.{0,#{n}}/m) 
end 

和字符计数代码

def utf8_length 
    self.unpack('U*').size 
end 

任何其他更快的方法来替代它们？

Answer 1

我想你可以解决这个问题不同

你并不需要扫描的文件很多次，你可以创建一个数据库，想在mongo或mysql，并为每个你找到的话，你取数据库为它，然后添加一些“计数器”字段。

你可以问我“但我必须扫描我的数据库很多，这可能需要更多”。那么，确定你不会问这个问题，但不会花费更多时间，因为数据库集中在IO中，除此之外你总是可以使用index it。

---

编辑：没有办法在所有划定？让我们说，你有一个Word.name字符串，你真的拥有一个（而不是简单的）正则表达式。正则表达式是否包含\ n？那么，如果正则表达式可以包含任何值，则应该估计正则表达式可以获取的字符串的最大大小，将其加倍，然后通过该字符集来扫描文件，但将光标移动该数字。

可以说你对你的正则表达式可以获取的最大值的估计就像你的文件有0到30000个字符的20个字符。你通过每个正则表达式，你有0到40个字符，然后再从20到60，从40到80等...

你还应该保持你找到的更小的正则表达式的位置，所以它不会重复。

最后，这个解决方案似乎不值得你付出努力，你的问题可能基于那些正则表达式有更大的解决方案，但它会比调用扫描Words.count时间更快的300Mb字符串更快。

Answer 2

您使用scan会创建一个数组，计算它的大小，然后将其丢弃。如果您在大文件中出现大量子字符串，您将暂时创建一个大数组，但可能会耗费内存管理的CPU时间，但即使在300MB的情况下，该时间仍应该很快运行。

因为Word是一个ActiveRecord类，它依赖于数据库中的模式和索引，以及数据库服务器可能遇到的任何问题。如果数据库未优化或响应速度缓慢，或者用于检索数据的查询效率不高，则迭代速度会很慢。你可能会发现它抓住Word的组合很快，因此它们在RAM中，然后迭代它们。

而且，如果数据库和你的代码是在同一台机器上运行，你可以从资源约束痛苦的样子只有一个驱动器，没有足够的RAM等

不知道更多关于你的环境和硬件这很难说。

---

编辑：

我可以抓住子到一个数组/哈希第一，则计数结果添加到数组或哈希，并且所有的计数是后的结果写回到数据库完成。你认为它会更快，对吧？

没有，我怀疑这将有很大的帮助，而且，不知道问题出在哪里你可能做的是使问题变得更糟，因为你必须加载10000条记录从数据库对象，然后再建一个10000个元素的散列或数组，这些元素也将与DB记录一起存储在内存中，然后写出它们。

Ruby目前只能使用一个核心，但您可以通过使用Ruby 1.9+来获得速度。我建议使用installing RVM并让它管理你的Ruby。请务必阅读该页面上的说明，然后运行rvm notes并按照这些说明操作。

你的Word模型和底层模式和索引是什么样的？数据库是否在同一台机器上？

---

编辑：从看你的表模式，你有除了id无索引这确实帮助不大正常的查找窗口。我建议在Stack Overflow的兄弟网站https://dba.stackexchange.com/上展示你的模式，并解释你想要做什么。至少我会在文本字段中添加一个键，以帮助避免对您执行的任何搜索进行全表扫描。

有什么可以帮助更多的是从“Active Record Query Interface”中读取：Retrieving Multiple Objects in Batches。

另外，看看您的Word.each正在运行时发出的SQL。是不是像"select * from word"？如果是这样的话，Rails会在10,000条记录中逐个迭代它们。如果它类似于"select * from word where id=1"，那么对于每次更新计数的记录，您都会读取数据库，然后写入数据。这是“批量检索多个对象”链接将有助于解决的情况。

此外，我猜content是您正在搜索的文本，但我无法确定。是否有可能您有重复的文本值，导致您对同一文本进行多次扫描？如果是这样，请在该字段上使用unique条件选择记录，然后一次更新所有匹配记录的计数。

你是否对你的代码进行了剖析，看看Ruby本身是否可以帮助你找出问题所在？修改你的代码来处理100或1000条记录。用-r profile标志启动应用程序。当应用程序退出分析器时，将输出一个表格显示时间花费在哪里。

你正在运行哪个版本的Rails？

Answer 3

您可以将整个“Word”表加载到Trie中，然后执行反向跟踪，因为您说文本中没有分隔符。

因此，对于文本中的每个字符，沿着三字之下。如果你打了一个字，增加它的计数。 “走下来”涉及三种情况：

1. 这个角色没有节点。 （如果你是中间搜索，弹出后退堆栈）
2. 这个角色有一个节点。 （但它不是一个字）
3. 这个角色有一个节点。 （这是一个字 - 增量和“脏”）

追溯只是跟踪你想要去的地方，你已经用尽了Trie的这个“搜索”，这是当你用完节点访问。这可能是你访问的每个角色都是Trie的根源。

完成此操作后，您可以访问您更改的所有节点并更新它们所代表的记录。

这将需要一些时间来实现，但肯定会比每个&扫描更快。