gistfile1.rb

require 'benchmark'

letters = ('a'..'z').to_a

SHORT_LIST = (100.times.map do
  (3..5).to_a.sample.times.map do
    letters.sample
  end.join
end + ['aacc', 'ccaa']).shuffle

LIST = (1_000.times.map do
  (1..10).to_a.sample.times.map do
    letters.sample
  end.join
end + ['aacc', 'ccaa']).shuffle

BIG_LIST = (5_000.times.map do
  (1..20).to_a.sample.times.map do
    letters.sample
  end.join
end + ['aacc', 'ccaa']).shuffle

TEST_DATA   = ['acbb', 'aa', 'ccaa', 'cacc', 'accca', 'aacc']
TEST_WORD   = 'acca'
TEST_EXPECTED = ['aacc', 'ccaa']

# <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
# <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
# <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

def anagrams_sort_and_length(source, words)
  similars = []
  s = source.chars.sort
  len = s.size

  words.each do |result|
    next if result.size != len
    similars << result if s == result.chars.sort
  end

  similars
end


@dict_word_letters_dima = {}
def anagrams_dima(source, words)
  def to_i(w)
    r = 0
    w.each_char { |ch| r = r | (1 << ch.ord - 96) }
    r
  end

  if @dict_word_letters_dima.empty?
    words.each do |word|
      @dict_word_letters_dima[word] = to_i(word)
    end
  end

  res = []
  wh = to_i(source)
  @dict_word_letters_dima.each do |w, h|
    res << w if wh == h && w.length == source.length && w.chars.sort == source.chars.sort
  end

  res
end

@dict_word_letters_andrey = {}
def anagrams_andrey(source, words)
  def to_h(w)
    r = {}
    w.each_char do |ch|
      r[ch] ||= 0
      r[ch] += 1
    end
    r
  end

  if @dict_word_letters_andrey.empty?
    words.each do |word|
      @dict_word_letters_andrey[word] = to_h(word)
    end
  end

  res = []
  wh = to_h(source)
  @dict_word_letters_andrey.each do |w, h|
    res << w if wh == h
  end
  res
end

# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

def test(method)
  result = send method, TEST_WORD, TEST_DATA

  if result.sort == TEST_EXPECTED
    puts "#{method} is ok"
  else
    puts "wrong results are #{result}"
    fail "#{method} is fucking shit"
  end
end

methods = private_methods.grep /anagrams/
methods.each do |method|
  test method
end

@dict_word_letters_dima = {}
@dict_word_letters_andrey = {}

puts 'short list 250 items with 3..5 chars'
Benchmark.bm(30) do |x|
  methods.shuffle.each do |method|
    x.report(method) { 100.times { send method, TEST_WORD, SHORT_LIST } }
  end
end

@dict_word_letters_dima = {}
@dict_word_letters_andrey = {}
puts 'list 1000 items with 1..10 chars'
Benchmark.bm(30) do |x|
  methods.shuffle.each do |method|
    x.report(method) { 100.times { send method, TEST_WORD, LIST } }
  end
end

@dict_word_letters_dima = {}
@dict_word_letters_andrey = {}
puts 'short list 5000 items with 1..20 chars'
Benchmark.bm(30) do |x|
  methods.shuffle.each do |method|
    x.report(method) { 100.times { send method, TEST_WORD, BIG_LIST } }
  end
end

~/Projects/shoedazzle/newdazzle [project_shopping_cart] ruby test.rb
anagrams_sort_and_length is ok
anagrams_dima is ok
anagrams_andrey is ok
short list 250 items with 3..5 chars
user system total real
anagrams_dima 0.010000 0.000000 0.010000 ( 0.006238)
anagrams_andrey 0.000000 0.000000 0.000000 ( 0.004104)
anagrams_sort_and_length 0.020000 0.000000 0.020000 ( 0.012353)
list 1000 items with 1..10 chars
user system total real
anagrams_andrey 0.050000 0.000000 0.050000 ( 0.056994)
anagrams_dima 0.040000 0.000000 0.040000 ( 0.039509)
anagrams_sort_and_length 0.050000 0.010000 0.060000 ( 0.051050)
short list 5000 items with 1..20 chars
user system total real
anagrams_andrey 0.290000 0.000000 0.290000 ( 0.288560)
anagrams_sort_and_length 0.140000 0.000000 0.140000 ( 0.140252)
anagrams_dima 0.200000 0.000000 0.200000 ( 0.201446)
~/Projects/shoedazzle/newdazzle [project_shopping_cart] ruby test.rb
anagrams_sort_and_length is ok
anagrams_dima is ok
anagrams_andrey is ok
short list 250 items with 3..5 chars
user system total real
anagrams_dima 0.010000 0.000000 0.010000 ( 0.005546)
anagrams_sort_and_length 0.010000 0.000000 0.010000 ( 0.009120)
anagrams_andrey 0.000000 0.000000 0.000000 ( 0.005596)
list 1000 items with 1..10 chars
user system total real
anagrams_sort_and_length 0.050000 0.000000 0.050000 ( 0.051109)
anagrams_andrey 0.050000 0.000000 0.050000 ( 0.049093)
anagrams_dima 0.040000 0.000000 0.040000 ( 0.039407)
short list 5000 items with 1..20 chars
user system total real
anagrams_dima 0.180000 0.000000 0.180000 ( 0.182791)
anagrams_sort_and_length 0.140000 0.000000 0.140000 ( 0.142361)
anagrams_andrey 0.290000 0.010000 0.300000 ( 0.283605)
~/Projects/shoedazzle/newdazzle [project_shopping_cart] ruby test.rb
anagrams_sort_and_length is ok
anagrams_dima is ok
anagrams_andrey is ok
short list 250 items with 3..5 chars
user system total real
anagrams_sort_and_length 0.010000 0.000000 0.010000 ( 0.013953)
anagrams_dima 0.010000 0.000000 0.010000 ( 0.005767)
anagrams_andrey 0.000000 0.000000 0.000000 ( 0.004303)
list 1000 items with 1..10 chars
user system total real
anagrams_sort_and_length 0.040000 0.000000 0.040000 ( 0.049991)
anagrams_dima 0.030000 0.000000 0.030000 ( 0.029394)
anagrams_andrey 0.050000 0.000000 0.050000 ( 0.048615)
short list 5000 items with 1..20 chars
user system total real
anagrams_sort_and_length 0.140000 0.000000 0.140000 ( 0.135487)
anagrams_andrey 0.290000 0.010000 0.300000 ( 0.291958)
anagrams_dima 0.190000 0.000000 0.190000 ( 0.196466)
~/Projects/shoedazzle/newdazzle [project_shopping_cart] ruby test.rb
anagrams_sort_and_length is ok
anagrams_dima is ok
anagrams_andrey is ok
short list 250 items with 3..5 chars
user system total real
anagrams_andrey 0.010000 0.000000 0.010000 ( 0.006840)
anagrams_sort_and_length 0.010000 0.000000 0.010000 ( 0.008723)
anagrams_dima 0.000000 0.000000 0.000000 ( 0.005287)
list 1000 items with 1..10 chars
user system total real
anagrams_dima 0.040000 0.000000 0.040000 ( 0.039349)
anagrams_sort_and_length 0.050000 0.000000 0.050000 ( 0.046454)
anagrams_andrey 0.060000 0.010000 0.070000 ( 0.060367)
short list 5000 items with 1..20 chars
user system total real
anagrams_sort_and_length 0.120000 0.000000 0.120000 ( 0.125371)
anagrams_dima 0.200000 0.000000 0.200000 ( 0.200339)
anagrams_andrey 0.300000 0.000000 0.300000 ( 0.297637)