2

私は、 MOSSの Idea を使用する小さな剽窃検出エンジンに取り組んでいます。ローリング ハッシュ関数が必要です。Rabin-Karp アルゴリズムから着想を得ています。

私が書いたコード -->

#!/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) ここで、テキストは文字列入力です。

コードは非常に遅いです。どこが間違っていますか？

4

1 に答える 1

6

RubyのプロファイラーであるRuby-Profを見てください。を使用gem install ruby-profして取り付けます。

コードが遅れている場所をいくつか考えたら、Ruby のベンチマークを使用してさまざまなアルゴリズムを試し、最速のものを見つけることができます。

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)

コードはラップトップで実行されているため、値は以前のテストとは異なります。

2 つの変数を追加すると、オーバーヘッドがあるため、固定文字列が含まれる場合よりも高速になります。Ruby は中間変数を作成し、それに追加する必要があります。

ここでの大きな教訓は、何がより速く実行されるかを知っているので、コードを書くときに、より多くの情報に基づいた決定を下すことができるということです。同時に、ほとんどのコードは 1,000,000 ループを実行していないため、違いはそれほど大きくありません。走行距離は異なる場合があります。

于 2011-12-30T17:54:54.887 に答える