Определение строк, которые содержат каждый символ в списке

Question

У меня есть слова "dinosaur", "dosimetry", and "moist".Я думаю о случае, когда у меня есть сотни тысяч слов.Я хочу вернуть все слова, содержащие "s", "i", "o", "m" в любом месте строки.Функция должна вернуть "dosimetry", "moist".

Есть ли эффективный способ сделать это, или мне нужно повторить и проверить?

Answer 1

Только для опыта

Использование регулярного выражения в положительном ключе

words = %w(dinosaur dosimetry moist)

words.select { |word| word.match?(/(?=.*m)(?=.*s)(?=.*i)(?=.*o).*/) }

#=> ["dosimetry", "moist"]

Чтобы увеличить скорость поиска, я расположил буквы в регулярном выражении в соответствии с Частота английских букв .

Answer 2

По запросу публикуя мой сравнительный тест в более читабельной / постоянной форме.

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

Answer 3

A = ['o', 'i', 's', 'm']
words = ["dinosaur", "dosimetry", "moist", "personal", "since",
  "including", "guide", "shop", "directory", "board", "location",
  "change", "white", "text", "small", "emotions", "rating",
  "rate", "movies", "government"]

Вот два метода, которые возвращают слова в words, которые содержат все буквы, содержащиеся в A.

# 1

def select_some(words)
  words.select { |word| A & word.chars == A }
end

select_some(words)
  #=> ["dosimetry", "moist", "emotions", "movies"] 

Оперативная строка может быть изменена на

words.select { |word| (A-str.chars).empty? }

# 2

n = 1
H = A.each_with_object({}) do |c,h|
  h[c] = n
  n <<= 1
end
  #=> {"s"=>1, "i"=>2, "o"=>4, "m"=>8} 
N = n - 1
  #=> 15

def select_some(words)
  words.select do |word|
    n = 0
    word.each_char do |c|
      x = H[c]
      n |= x if x
    end
    n == N
  end
end

select_some(words)
  #=> ["dosimetry", "moist", "emotions", "movies"]