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

Question

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

ruby-on-railsrubyperformancestringbenchmarking

3

我有一个大小为300MB的文本文件，我想要统计文件中每个10,000个子字符串的出现次数。我想知道如何快速完成它。

现在，我使用以下代码：

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

Word是一个ActiveRecord类。

这个过程花了我将近1天的时间来完成计数。有没有更快的方法呢？谢谢。

编辑1：再次感谢。我正在运行rails 2.3.9。words表的name字段包含我正在搜索的内容，并且它只包含唯一值。我使用批处理（每次1000行）加载，应该会有所帮助。

我根据bpaulon的思路重写了整个代码。现在只需要几个小时就能完成计数。

我对新版本代码进行了分析，现在耗时最长的方法是支持utf8编码的字符串截断代码。

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

字符计数代码

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

有其他更快的方法来替换它们吗？

- yang

你可以将文件分割并在不同的线程中扫描。 - bpaulon

这些子字符串是否总是由空格分隔？或者它们中的一些是否可能包含空格？ - Nemo157

不包含空格分隔符。有些可能包含空格。 - yang

bpaulon，你能详细告诉我吗？我的代码只能使用一个CPU核心，而且这个核心始终被占用了100%。 - yang

我做到了！我把Word表格分成了两部分！现在每个线程都处理其中的一部分，CPU使用率达到了100％，而不是50％。 - yang

似乎jruby可以更快地完成它：http://www.ruby-forum.com/topic/212074 - yang

3个回答

1

我认为你可以用不同的方法来解决这个问题。

你不需要扫描文件这么多次，你可以创建一个数据库，就像mongo或mysql一样，对于每个单词，你可以在数据库中查找它，然后添加一些“计数器”字段。

你可能会问我：“但是那样我将不得不频繁地扫描我的数据库，这可能需要更多的时间。” 好吧，当然你不会这样问，但它不会花费更多的时间，因为数据库专注于IO，此外你总是可以索引它。

编辑：根本没有办法进行分隔吗？假设您拥有一个 Word.name 字符串，实际上保存了（不简单的）正则表达式。正则表达式可以包含 \n 吗？如果正则表达式可以包含任何值，则应估计正则表达式可以获取的字符串的最大大小，并将其乘以2，然后通过该数量的字符扫描文件，但通过该数字移动游标。

假设您估计正则表达式可以获取的最大值为20个字符，而您的文件从0到30000个字符不等。您将每个正则表达式从0到40个字符传递一次，然后再从20到60，从40到80等等......

您还应保持找到较小的正则表达式的位置，以便不重复它。

最后，这个解决方案似乎不值得努力，您的问题可能有一个更好的解决方案，基于那些正则表达式，但它将比调用扫描 Words.count 次您的 300MB 字符串要快。

- bpaulon

我没有扫描文件。我先加载它，然后扫描内容。 - yang

我指的是 Ruby 的“scan”方法，抱歉造成了歧义。 - bpaulon

你看，对于数据库中的每个单词，你都会在整个文件上触发“扫描”方法，而我认为你应该相反地做，对于文件中的每个单词，你都要在数据库中查找它并将其计数器加一。 - bpaulon

我现在明白你的意思了。这将是一个不错的解决方案，但我的问题是我要计数的不是单词，而是字符串，并且没有分隔符将整个文件分成“每个单词”。 - yang

我编辑了我的回答。请问这个“substrings”的格式是什么？ - bpaulon

显示剩余2条评论

0

你可以将整个“Word”表加载到Trie中，然后进行回溯，因为你说文本中没有分隔符。

所以对于文本中的每个字符，沿着单词的Trie树向下走。如果遇到一个单词，就增加它的计数。“沿着Trie树向下走”涉及三种情况：

这个字符没有节点。（如果你正在搜索中间，请弹出回溯堆栈）
这个字符有一个节点。（但它不是一个单词）
这个字符有一个节点。（它是一个单词-增加并“脏化”）

回溯只是跟踪你在耗尽这个Trie树的“搜索”之后想要去的地方，这通常是你访问的每个字符都是Trie树的根节点。

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

这需要一些时间来实现，但肯定比每次扫描快。

- Colin Curtin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- the Tin Man · Accepted Answer

你使用的scan创建了一个数组，计算其大小，然后将其丢弃。如果在大文件中有许多子字符串的出现，您将暂时创建一个大数组，可能会因内存管理而消耗CPU时间，但即使是300MB，它仍应该运行得非常快。

由于Word是一个ActiveRecord类，它依赖于数据库中的架构和任何索引，以及您的数据库服务器可能遇到的任何问题。如果数据库未经过优化或响应缓慢，或用于检索数据的查询不高效，则迭代将变慢。您可能会发现，抓取Word组以使它们位于RAM中，然后对它们进行迭代会更快。

如果数据库和您的代码在同一台机器上运行，那么您可能会遭受资源限制，例如只有一个驱动器，内存不足等。

没有更多关于您的环境和硬件的信息，很难说。

编辑：

我可以先将子字符串抓取到数组/哈希表中，然后将计数结果添加到数组或哈希表中，在完成所有计数后将结果写回数据库。你认为这会更快，对吗？

不，我怀疑这样做并不能帮助很多，而且如果不知道问题出在哪里，你可能只会让问题变得更糟，因为你需要从数据库中加载10,000条记录作为对象，然后构建一个有10,000个元素的哈希表或数组，它们也将与DB记录一起存储在内存中，然后再将它们写出。

Ruby目前只使用单个核心，但您可以通过使用Ruby 1.9+来提高速度。我建议安装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？