ruby - 优化的字符串插入算法

Question

我们的软件中有一小部分会在大量代码(平均长度为 900000 个字符)上的某个匹配字符串前后插入一个字符串。

例子:

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

替换为

Lorem Ipsum 只是 <span class="class1 class2">printing</span> 的虚拟文本和排版行业。 Lorem Ipsum 有 <span class="class1 class2 class3">been</span>行业标准虚拟文字<span class="class1">ever since the 1500s</span> ，当时一位不知名的打印商拿走了一个字体厨房，并把它加起来制作了一本字体样本书。

---

好的，到目前为止一切顺利。我们可以只搜索和替换，但内容在某种程度上是语义相关的，所以 printing在那种情况下被替换，但可能不在文本的其他地方。 我们所做的是在我们想要替换文本的位置建立索引，因此对于每次替换，我们都会得到一个起始位置和一个结束位置。

当前代码:

new_val = huge_string_goes_here
entities.each { |entity|
    add_before = "<span class=\"#{entity.getStuff}\">"
    add_after = '</span>'

    new_val.insert(entity.getStart+increment, add_before)
    increment = increment+add_before.length
    new_val.insert(entity.getEnd+increment, add_after)
    increment = increment+add_after.length
}

分析一个 900000 个字符长的字符串大约需要 15-20 秒。

有人对我们如何优化它有什么建议吗？

谢谢

Answer 1

考虑写一个 C extension module for Ruby它可以为您找到匹配索引 - 这种操作 native 应该比解释代码快得多。获得索引后，您可以使用 Ruby 插入前/后文本，或者如果性能仍需要提升，则考虑在 C 中全部完成。

请注意，与任何优化一样，关键是要确保您的“优化”确实改进了未优化的代码。为一些示例案例编写基准并跟踪纯 Ruby 代码所花费的时间，然后使用您的 native 扩展运行相同的基准并查看性能是否实际上更好。