HTMLの差分検知の時間を短縮する方法は？

短い文字列比較の方が高速なのでは？というアイデア

クローラーを作成する時に、対象のURLの内容の変更を検知したいことはよくあるかと思います。

そこで単純にHMTL同士を比較するよりも、ハッシュ関数を利用して作成したダイジェストを比較することで、 時間を短縮することができるのではないかと思い、検証してみました。

ただし、ハッシュ関数を利用する場合、前回取得したダイジェストと今回取得したHTMLをハッシュ関数を利用してダイジェストに変換する処理が必要になるので、 以下のような２ステップ必要すると仮定します。

1: 取得したHTMLをハッシュ関数を利用してダイジェストを求める
2: 保存しておいたダイジェストと今取得したダイジェストを比較する

どのハッシュ関数が良いか？

今回の利用目的では脆弱性は問題とならないので、ダイジェストを作成する時の時間に注目して、ハッシュ関数を選びたいと思います。

require 'benchmark/ips'
require 'digest'

target = 'hello' * 1000

Benchmark.ips do |x|
  x.report('Digest::MD5') { Digest::MD5.new.update(target).digest }
  x.report('Digest::SHA1') { Digest::SHA1.new.update(target).digest }
  x.report('Digest::SHA512') { Digest::SHA512.new.update(target).digest }

  x.compare!
end

結果です。

Warming up --------------------------------------
         Digest::MD5    10.426k i/100ms
        Digest::SHA1    10.226k i/100ms
      Digest::SHA512     5.500k i/100ms
Calculating -------------------------------------
         Digest::MD5    118.802k (± 1.3%) i/s -    594.282k in   5.003149s
        Digest::SHA1     99.109k (± 1.3%) i/s -    501.074k in   5.056664s
      Digest::SHA512     53.405k (± 5.2%) i/s -    269.500k in   5.064988s

Comparison:
         Digest::MD5:   118801.8 i/s
        Digest::SHA1:    99109.1 i/s - 1.20x  (± 0.00) slower
      Digest::SHA512:    53405.4 i/s - 2.22x  (± 0.00) slower

※ 「繰り返し回数/時間(i/ms)」で処理を評価します。つまり、数値が大きいほど高速ということを意味しています。

生成するdigestの長さは、MD5: 16文字, SHA1: 20文字, SHA512: 64文字なので妥当な結果だと思われます。
今回の目的では「MD5」を利用するのが良さそうです。

ハッシュ関数 vs 文字列

冒頭で説明したハッシュ関数と単純な文字列を利用した方法の比較です。

require 'benchmark/ips'
require 'digest'

target = 'hello' * 10000
md5_digest = Digest::MD5.new.update(target).digest

def digest_compare(str, digest)
  digest == Digest::MD5.new.update(str).digest
end

def str_compare(str1, str2)
  str1 == str2
end

Benchmark.ips do |x|
  x.report('digest_compare') { digest_compare(target, md5_digest) }
  x.report('str_compare') { str_compare(target, target) }

  x.compare!
end

結果です。

Warming up --------------------------------------
      digest_compare     1.231k i/100ms
         str_compare     1.485M i/100ms
Calculating -------------------------------------
      digest_compare     13.293k (± 0.9%) i/s -     66.474k in   5.000995s
         str_compare     13.957M (± 7.1%) i/s -     69.813M in   5.047691s

Comparison:
         str_compare: 13957048.8 i/s
      digest_compare:    13293.2 i/s - 1049.94x  (± 0.00) slower

単純な文字列比較の方がはやいことがわかります。。。。
これは文字の長さを長くすると、ハッシュ関数の処理時間が増えることが原因か、差はさらに広がります。

結論

単純な文字列比較を行いましょう。