如何加快使用大正则表达式扫描大字符串的速度

Question

>我有大字符串：

string = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec nec neque..."
puts string.size # => 54555999

我还有一个很大的正则表达式：

regex = /Lorem|ipsum|dolor|sit|amet|consectetur|adipiscing|elit|Donec|nec|neque|facilisis|nulla|rhoncus|accumsan|non|in|arcu|Interdum|et|malesuada|fames|ac|ante|primis|faucibus|Pellentesque|habitant|morbi|tristique|senectus|netus|turpis|egestas|at|ut|metus|convallis|fringilla|Nullam|volutpat|risus|sodales|elementum|Fusce|vitae|dignissim|tortor|Vivamus|interdum|dapibus|leo|sed|Quisque|luctus|dui|ligula|consequat|augue|congue|a|Vestibulum|id|cursus|odio|Maecenas|libero|diam|placerat|Proin|sapien|gravida|Cras|eleifend|nisl|rutrum|lectus|Curabitur|auctor|urna|tellus|tincidunt|erat|eget|vulputate|nibh|tempor|Ut|vehicula|nisi|velit|suscipit|nunc|tempus|vestibulum|viverra|Duis|sagittis|dictum|justo|hendrerit|massa|mollis|ultricies|lorem|imperdiet|mattis|pharetra|Aenean|lacus|purus|condimentum|Integer|sem|ullamcorper|feugiat|venenatis|quis|pellentesque|felis|finibus|porta|Nam|pulvinar|est|Morbi|ex|eros|commodo|Praesent|mauris|scelerisque|enim|aliquet|Etiam|Mauris|eu|bibendum|efficitur|magna|maximus|ornare|Phasellus|vel|blandit|sollicitudin|Suspendisse|Sed|quam|pretium|mi|semper|molestie|In|Nulla|Aliquam|euismod|orci|varius|hac|habitasse|platea|dictumst|iaculis|ultrices|Nunc|aliquam|fermentum|lacinia|lobortis|porttitor|laoreet|posuere|cubilia|Curae|facilisi|potenti|Cum|sociis|natoque|penatibus|magnis|dis|parturient|montes|nascetur|ridiculus|mus|Class|aptent|taciti|sociosqu|ad|litora|torquent|per|conubia|nostra|inceptos|himenaeos/

我现在想用regex scan string：

puts Benchmark.measure { string.scan(regex) } # => 17.830000   0.380000  18.210000 ( 18.235952)

如您所见，扫描需要 17.83 秒，这对于我的用例来说太多了。

我怎样才能加快速度？

match和=~方法对我没有任何好处，因为我需要匹配数组。我想也许我需要走出 Ruby 来加快速度，但我不知道怎么做。

现实世界的

正则表达式是很多订单ID，现实世界的字符串是将大量电子邮件(主题和内容(合并到一个字符串中。扫描电子邮件以提及订单 ID 的目的是找出客户查询了哪些订单 ID。

编辑：

我想进行初始正则表达式测试的原因是因为我之后需要像这样做一个非常大的循环：

["order_id_1", "order_id_2"].each do |order_id|
  ["email body 1", "email body 2"].delete_if do |email_string|
    match = (email_string =~ Regexp.new(order_id)) != nil
    if match
      # do stuff
    end
    match
    end
  end
end

对于许多订单ID和许多电子邮件，这将成为一个非常大的循环，除非我最初评估哪些订单ID已经对应。

Answer 1

假设order_ids是一个订单ID数组，我假设它包含数字和/或数字，大小写不是问题。 如果email是包含一封电子邮件的字符串，

email.scan(/w+/) & order_ids

将为您提供该电子邮件中包含的所有订单ID。但是，您可以通过首先将order_ids转换为集合来加快速度：

require 'set'
order_id_set = order_ids.to_set
email.scan(/w+/).select { |w| order_id_set.include?(w) }

无论如何，将电子邮件串在一起没有任何好处。

我建议你使用以下方法将电子邮件分成几个单词：

email.scan(/w+/)

但你可能想要一些更精致的东西。 假设一封电子邮件如下：

email = "I am really annoyed that my order AB123 was shipped late, " +
  "that order CD456was poorly packed and I was overcharged for order EF789."

让我们看一下将其划分为单词的两种方式：

esplit = email.split
  #=> ["I", "am", "really", "annoyed", "that", "my", "order", "AB123",
  #    "was", "shipped", "late,", "that", "order", "CD456was", "poorly",
  #    "packed", "and", "I", "was", "overcharged", "for", "order", "EF789."]
escan = email.scan(/w+/)
  #=> ["I", "am", "really", "annoyed", "that", "my", "order", "AB123",
  #    "was", "shipped", "late", "that", "order", "CD456was", "poorly",
  #    "packed", "and", "I", "was", "overcharged", "for", "order", "EF789"]

你可以看到这两种方法正在酝酿麻烦(例如，"CD456was"(。现在让我们创建一组订单 ID：

require 'set'
order_id_set = %w{ AB123 CD456 EF789 GH012 }.to_set
  #=> #<Set: {"AB123", "CD456", "EF789", "GH012"}>

，然后在电子邮件中搜索订单 ID：

esplit.select { |w| order_id_set.include?(w) }
  #=> ["AB123"]
escan.select  { |w| order_id_set.include?(w) }
  #=> ["AB123", "EF789"]

如您所见，split(与 split(' ') 和 split(/s+/) 相同(，它在空格上拆分行，捕获了一阶 id，但错过了其他两个，CD456因为作者未能在该 id 和单词之间放置空格 "was" 和 EF789 ，因为它正在寻找"EF789."。

scan(/w+/)，它拆分出"单词"(w查找a-z，A-Z，0-9和_(，做得更好，将"EF789"标识为订单ID，因为句点是"非单词"字符。 然而，它也错过了"CD456"，因为"w"、"a"和"s"是单词字符，所以它包括了它们。 (这类似于您的"1234"示例。

这意味着您需要制作更好的正则表达式。例如，如果所有订单 ID 都像我示例中的 ID 一样(两个大写字母后跟三位数字(，您可以这样写：

email.scan(/(?<![A-Z])[A-Z]{2}d{3}(?!d)/)
     .select { |w| order_id_set.include?(w) }
  #=> ["AB123", "CD456", "EF789"]

这匹配两个大写字母，紧跟大

写字母以外的任何内容，后跟三位数字，紧跟另一个数字以外的任何字符。 这只是一个可能的例子。 您可能想发布另一个问题，该问题专门涉及使用正则表达式来识别电子邮件中可能的订单号。当然，为此，您必须更好地描述订单号的外观。

无论如何，您的正则表达式不会包含您提到的#{order_id}。唯一的方法是为每个订单ID使用单独的正则表达式检查每封电子邮件，这将非常低效。相反，您希望使用正则表达式来识别可能的订单号，然后根据订单号集检查它们。在选择正则表达式时，您可能会在遗漏的订单 ID 数量和浪费时间根据订单 ID 集检查的非订单 ID 字符串数量之间进行权衡。

Answer 2

不要使用正则表达式。相反，请使用适合要匹配的特定字符串和模式的专用算法。如果你绝对需要使用正则表达式，你可以尝试找到一个与 Ruby 原生使用的引擎不同的引擎(尽管我怀疑这会非常有成效(。如果你仍然需要更好的性能，用更快/更低级别的语言(如 C(编写算法，然后使用本机扩展或其他东西从 ruby 调用它。

以下是一些有助于本机扩展的资源：

• 自述文件。内线
• 红宝石内联
• Ruby-FFI

至于制作一个专门的算法，我可能帮不了你。

Answer 3

这是一个在

O(n^2)时间内运行的算法。这比正则表达式的性能要好得多，正则表达式的性能可能比O(n^2) 差得多。

该算法背后的直觉是，使用字符串和正则表达式的计算成本很高！正则表达式在小字符串上运行时或不经常运行时是功能强大的工具，但当正则表达式和字符串都很复杂时，正则表达式的性能很差。但是，在您的特定情况下，您对字符串是否以特定方式格式化并不真正感兴趣。相反，您想找出哪些电子邮件与哪些订单 ID 匹配。我们可以直接执行此操作，而无需使用正则表达式的开销。

根据您的一条评论，您收到的数据最初不是长字符串和长正则表达式的形式，而是两个大列表。这很好，因为使用列表可以更轻松地使用算法。由于您有兴趣了解哪些订单 ID 与电子邮件匹配，因此我们将设计算法，使其生成一个数组，其中包含与电子邮件匹配的每个订单 ID。

这是算法：

1. 创建匹配订单 ID 的数组。最初，它将是空的。
2. 对于电子邮件数组中的每个字符串，
   1. 对于订单 ID 数组中的每个订单 ID，请查看其中是否有任何 ID 与电子邮件匹配。
   2. 如果我们找到匹配项，请将订单 ID 添加到匹配的订单 ID 数组中。
3. 匹配的订单 ID 数组包含与电子邮件匹配的每个订单 ID。

如果有n电子邮件和m订单 ID，则此算法需要O(nm)时间。如果n和m大致相同，则算法在O(n^2)时间内运行。

---

这是一些实现此算法的 Ruby 代码：

emails = ['email1', 'email2', 'email3', #etc.
order_ids = ['order1', 'order2', 'order3', #etc.
# Create an array to hold the matched order IDs
matched_order_ids = []
# Perform a search for each email
emails.each |email| do
  order_ids.delete_if |order_id| do
    if email.include? order_id
      matched_order_ids.push order_id
      # tells delete_if to remove the order_id,
      # saving us time searching in future emails
      return true
    else
      # tells delete_if not to remove the order_id
      return false
    end
  end
end
# At this point, matched_order_ids contains every
# order ID that was matched in at least one of the
# emails