Рабин Карп Реализация слишком медленная в Ruby

Question

Я работал над небольшим механизмом обнаружения плагиата, который использует Idea от MOSS . Мне нужна функция Rolling Hash, я вдохновлен алгоритмом Рабина-Карпа.

Код, который я написал ->

#!/usr/bin/env ruby
#Designing a rolling hash function.
#Inspired from the Rabin-Karp Algorithm

module Myth
  module Hasher

    #Defining a Hash Structure
    #A hash is a integer value + line number where the word for this hash existed in the source file
    Struct.new('Hash',:value,:line_number)

    #For hashing a piece of text we ned two sets of parameters
    #k-->For buildinf units of k grams hashes  
    #q-->Prime which lets calculations stay within range
    def calc_hash(text_to_process,k,q)

      text_length=text_to_process.length
      radix=26

      highorder=(radix**(text_length-1))%q

      #Individual hashes for k-grams
      text_hash=0

      #The entire k-grams hashes list for the document
      text_hash_string=""

      #Preprocessing
      for c in 0...k do
        text_hash=(radix*text_hash+text_to_process[c].ord)%q
      end

      text_hash_string << text_hash.to_s << " "

      loop=text_length-k

      for c in 0..loop do        
        puts text_hash
        text_hash=(radix*(text_hash-text_to_process[c].ord*highorder)+(text_hash[c+k].ord))%q
        text_hash_string << text_hash_string << " "
      end
    end

  end
end

Я запускаю его со значениями -> calc_hash (text, 5,101) где text - это строковый ввод.

Код очень медленный. Куда я иду не так?

Answer 1

Посмотрите на Ruby-Prof , профилировщик для Ruby. Используйте gem install ruby-prof для его установки.

Если у вас есть идеи, где код запаздывает, вы можете использовать Ruby's Benchmark , чтобы попробовать разные алгоритмы, чтобы найти самый быстрый.

Обнюхивая StackOverflow, вы увидите множество мест , где мы будем использовать Benchmark для тестирования различных методов, чтобы определить, какой из них самый быстрый. Вы также получите представление о различных способах настройки тестов.

---

Например, глядя на ваш код, я не был уверен, было ли добавление << лучше конкатенации с использованием + или с использованием интерполяции строк. Вот код для проверки этого и результаты:

require 'benchmark'
include Benchmark

n = 1_000_000
bm(13) do |x|
  x.report("interpolate") { n.times { foo = "foo"; bar = "bar"; "#{foo}#{bar}" } }
  x.report("concatenate") { n.times { foo = "foo"; bar = "bar"; foo + bar      } }
  x.report("append")      { n.times { foo = "foo"; bar = "bar"; foo << bar     } }
end

ruby test.rb; ruby test.rb
                   user     system      total        real
interpolate    1.090000   0.000000   1.090000 (  1.093071)
concatenate    0.860000   0.010000   0.870000 (  0.865982)
append         0.750000   0.000000   0.750000 (  0.753016)
                   user     system      total        real
interpolate    1.080000   0.000000   1.080000 (  1.085537)
concatenate    0.870000   0.000000   0.870000 (  0.864697)
append         0.750000   0.000000   0.750000 (  0.750866)

---

Мне было интересно узнать об эффектах использования фиксированных и переменных при добавлении строк на основе комментария @ Myth17 ниже:

require 'benchmark'
include Benchmark

n = 1_000_000
bm(13) do |x|
  x.report("interpolate") { n.times { foo = "foo"; bar = "bar"; "#{foo}#{bar}" } }
  x.report("concatenate") { n.times { foo = "foo"; bar = "bar"; foo + bar      } }
  x.report("append")      { n.times { foo = "foo"; bar = "bar"; foo << bar     } }
  x.report("append2")     { n.times { foo = "foo"; bar = "bar"; "foo" << bar   } }
  x.report("append3")     { n.times { foo = "foo"; bar = "bar"; "foo" << "bar" } }
end

В результате:

ruby test.rb;ruby test.rb

                   user     system      total        real
interpolate    1.330000   0.000000   1.330000 (  1.326833)
concatenate    1.080000   0.000000   1.080000 (  1.084989)
append         0.940000   0.010000   0.950000 (  0.937635)
append2        1.160000   0.000000   1.160000 (  1.165974)
append3        1.400000   0.000000   1.400000 (  1.397616)

                   user     system      total        real
interpolate    1.320000   0.000000   1.320000 (  1.325286)
concatenate    1.100000   0.000000   1.100000 (  1.090585)
append         0.930000   0.000000   0.930000 (  0.936956)
append2        1.160000   0.000000   1.160000 (  1.157424)
append3        1.390000   0.000000   1.390000 (  1.392742)

Значения отличаются от моего предыдущего теста, потому что код запускается на моем ноутбуке.

Добавление двух переменных происходит быстрее, чем когда задействована фиксированная строка из-за накладных расходов; Ruby должен создать промежуточную переменную и затем добавить к ней.

Большой урок здесь заключается в том, что мы можем принимать более взвешенные решения, когда пишем код, потому что мы знаем, что работает быстрее. В то же время различия не очень велики, так как большая часть кода не выполняет 1 000 000 циклов. Ваш пробег может отличаться.