大数组场景下Ruby textQueries方法超时问题求优化方案

原代码的性能瓶颈 #

先聊聊你的原代码为啥处理大数据会超时——这些问题都是性能杀手：

• 重复计算冗余：每处理一个查询，都要重新拆分所有句子的单词，相当于把所有句子的拆分操作重复了M次（M是查询数量），完全是没必要的开销。
• 线性查找低效：用数组的include?检查单词是否存在，时间复杂度是O(S)（S是句子的单词数），每次查询都要对每个句子的所有查询词做线性查找，叠加起来复杂度高得吓人。
• 未处理重复查询词：比如查询里的"will will"，原代码会重复检查两次，纯纯浪费算力。

核心优化思路：预处理+倒排索引 #

解决这类多查询匹配问题，最经典的方案就是预处理构建倒排索引，把“句子找单词”反过来变成“单词找句子”，从根源上降低查询时的计算量。

具体步骤拆解：

1. 预处理阶段：遍历所有句子，为每个单词记录它出现的所有句子索引，形成一个哈希表（键是单词，值是包含该单词的句子索引数组）。同时对句子内的单词去重，避免同一个句子多次被加入同一个单词的列表。
2. 查询处理阶段：
   • 对查询词去重（比如"will will"变成["will"]），减少不必要的重复检查。
   • 如果有任何一个查询词不存在于倒排索引中，直接返回[-1]——毕竟没有句子能包含这个词，不用再往下算。
   • 取所有查询词对应的句子索引数组，求它们的交集——这个交集就是同时包含所有查询词的句子索引。
   • 额外优化：先把索引数组按长度排序，从最短的数组开始求交集，这样能最快缩小结果范围，减少计算量。

优化后的代码实现 #

def textQueries(sentences, queries)
  # 1. 预处理：构建倒排索引，记录每个单词对应的句子索引列表
  word_to_indices = Hash.new { |h, k| h[k] = [] }
  sentences.each_with_index do |sentence, idx|
    # 对句子内的单词去重，避免同一个句子重复加入同个单词的索引列表
    sentence.split(' ').uniq.each do |word|
      word_to_indices[word] << idx
    end
  end

  # 2. 处理每个查询
  queries.each do |query|
    # 查询词去重，消除重复检查的冗余
    unique_query_words = query.split(' ').uniq

    # 快速判断：如果有查询词从未在任何句子中出现，直接输出-1
    if unique_query_words.any? { |word| word_to_indices[word].empty? }
      puts "-1"
      next
    end

    # 按索引数组长度排序，从最短的开始求交集，提升效率
    sorted_index_lists = unique_query_words.map { |word| word_to_indices[word] }.sort_by(&:length)
    # 求所有索引列表的交集，得到符合条件的句子索引
    result = sorted_index_lists.inject(:&) || []

    # 输出结果：空数组则输出-1，否则输出空格分隔的索引
    puts result.empty? ? "-1" : result.join(' ')
  end
end

性能对比 #

• 原代码时间复杂度：O(M*N*(S+Q))（M=查询数，N=句子数，S=单句平均单词数，Q=单查询平均单词数），大数据下这个复杂度直接导致超时。
• 优化后代码时间复杂度：O(N*S + M*(Q + K))（K是交集操作的时间，远小于N），预处理只做一次，查询阶段的计算量被大幅压缩，处理超大数据集时性能会有质的飞跃。

内容的提问来源于stack exchange，提问作者Soumyadip Chakraborty