ruby - 识别包含列表中每个字符的字符串

Question

我有单词 “dinosaur”、“dosimetry”和“moist”。我在想我有几十万字的情况。我想返回字符串中任意位置包含 "s"、"i"、"o"、"m" 的所有单词。该函数应返回 "dosimetry", "moist"。

有没有一种有效的方法可以做到这一点，还是我必须反复检查？

Answer 1

应要求，以更具可读性/永久性的形式发布我的比较基准。

require 'benchmark/ips'

words = %w(dinosaur dosimetry moist personal since including guide shop directory board
           location change white text small emotions rating rate movies government)
letters = %w[s i o m]
letters_freq = %w[m s i o]

# set up compiled greps
regexes = letters.map {|l| Regexp.compile(l) }

# set up search index
naive_search_index = words.each_with_object({}) do |word, memo|
  word.each_char do |c|
    memo[c] ||= []
    memo[c] << word
  end
end


# set up twiddle
n = 1
letter_flags = letters.each_with_object({}) do |c,h|
  h[c] = n
  n <<= 1
end
mask = n - 1


Benchmark.ips do |x|
  x.report('chained greps') do
    letters.reduce(words) do |result, letter|
      result.grep(Regexp.new(letter))
    end
  end

  x.report('compiled greps') do
    regexes.reduce(words) do |result, regex|
      result.grep(regex)
    end
  end

  x.report('include') do
    words.select do |word|
      letters.all?{|l| word.include?(l)}
    end
  end

  x.report('freq include') do
    words.select do |word|
      letters_freq.all?{|l| word.include?(l)}
    end
  end

  x.report("Cary") do
    words.select do |word|
      letters & word.chars == letters
    end
  end

  x.report('twiddle (cary 2)') do
    words.select do |word|
      n = 0
      word.each_char do |c|
        x = letter_flags[c]
        n |= x if x
      end
      n == mask
    end
  end

  x.report("mechnicov") do
    words.select do |word|
      word.match?(/(?=.*m)(?=.*s)(?=.*i)(?=.*o).*/)
    end
  end

  x.report('freq search index') do
    # most frequent first
    naive_search_index.values_at(*letters_freq).reduce(:&)
  end

  x.compare!
end

结果

Comparison:
   freq search index:   323531.8 i/s
           mechnicov:   244783.9 i/s - 1.32x  slower
        freq include:   100981.6 i/s - 3.20x  slower
             include:    94612.7 i/s - 3.42x  slower
      compiled greps:    54553.1 i/s - 5.93x  slower
       chained greps:    40979.6 i/s - 7.89x  slower
    twiddle (cary 2):    35767.6 i/s - 9.05x  slower
                Cary:    33402.4 i/s - 9.69x  slower