Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2010-02-27

KMRCLを眺める STRING-HASH (99)

| 23:21 | KMRCLを眺める STRING-HASH (99) - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める STRING-HASH (99) - わだばLisperになる

今回はKMRCLのstrings.lispから、STRING-HASHです。

動作は、

(KL:STRING-HASH "Aa")
;⇒ 162

という感じで文字列からハッシュ値を出すもののようです。

(defun string-hash (str &optional (bitmask 65535))
  (let ((hash 0))
    (declare (fixnum hash)
             (simple-string str))
    (dotimes (i (length str))
      (declare (fixnum i))
      (setq hash (+ hash (char-code (char str i)))))
    (logand hash bitmask)))

という定義になっていますが、文字コードを足しこむ感じなので

(KL:STRING-HASH "Aa")
;⇒ 162
(KL:STRING-HASH "aA")
;⇒ 162

という風に同じ値になりやすい気がします。

標準だと、SXHASHがありますが

(SXHASH "Aa")
;⇒ 20184128143102

(SXHASH "aA")
;⇒ 30096039371269

これだと駄目なんでしょうか。

速度は、

(DOTIMES (I 100000000)
  (KL:STRING-HASH "aA"))
;⇒ NIL
----------
Evaluation took:
  1.820 seconds of real time
  1.820000 seconds of total run time (1.820000 user, 0.000000 system)
  100.00% CPU
  4,357,212,408 processor cycles
  252,128 bytes consed
  
Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz

(DOTIMES (I 100000000)
  (SXHASH "aA"))
;⇒ NIL
----------
Evaluation took:
  0.042 seconds of real time
  0.040000 seconds of total run time (0.040000 user, 0.000000 system)
  95.24% CPU
  98,789,364 processor cycles
  0 bytes consed
  
Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz

という風にSXHASHの方が大分速いようです。

自分は文字列からハッシュ値を取り出したい局面にあまり遭遇したことがないのでいまいち分かっていません。

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20100227