アルゴリズム図鑑という本のハッシュテーブルの説明のMOD 5という記述が引っかかり、
連想記憶、プログラムでの課題になかなかいいかもと作ってみることにしました。
データは1万件、Key、value共にランダムに並んだアルファベット10文字、
ハッシュテーブルは1000個(行?)にしてみました。
テストは100件のランダム抽出
順次アクセス検索
自前のハッシュテーブルと追加、取得関数
辞書型と時間を計測してみました。
途中経過は一切確認していませんのでバグはあります。きっと
実行結果
fullTestOk
0.1218867301940918
hashTestOk
0.0007932186126708984
dicTestOk
6.4849853515625e-05
フルアクセスより辞書型は遅い??
再度、よく見ると辞書型のテスト結果e-05がついている
実は自作の10倍以上速かったです。
連想記憶、プログラムでの課題になかなかいいかもと作ってみることにしました。
データは1万件、Key、value共にランダムに並んだアルファベット10文字、
ハッシュテーブルは1000個(行?)にしてみました。
テストは100件のランダム抽出
順次アクセス検索
自前のハッシュテーブルと追加、取得関数
辞書型と時間を計測してみました。
途中経過は一切確認していませんのでバグはあります。きっと
import random import time #mod 5 def randomKey(l): o="" for i in range(l): o+=chr(random.randint(0,25)+ord("a")) return o def hashAdd(HashName,key,value): tn=sum(ord(s) for s in str(key))%1000 for i in HashName[tn]: k,v=i if k==key: print("duplicate error") return HashName[tn].append((key,value)) def hashGet(HashName,key,default): tn=sum(ord(s) for s in str(key))%1000 for i in HashName[tn]: k,v=i if k==key:return v return default data=[] hash=[[] for i in range(1000)] dic={} for i in range(10000): data.append((randomKey(10),randomKey(10))) k,v=data[-1] hashAdd(hash,k,v) dic[k]=v testKey=[] checkValue="" for i in range(100): k,v=data[random.randint(0,9999)] testKey.append(k) checkValue+=v #fullAccess start = time.time() fullValue="" for i in range(100): for j in range(10000): k,v=data[j] if k==testKey[i]: fullValue+=v break if checkValue==fullValue: print("fullTestOk") print(time.time() - start) #hashAccess start = time.time() hashValue="" for i in range(100): hashValue+=hashGet(hash,testKey[i],"") if checkValue==hashValue: print("hashTestOk") print(time.time() - start) #DicAccess start = time.time() dicValue="" for i in range(100): dicValue+=dic.get(testKey[i],"") if checkValue==dicValue: print("dicTestOk") print(time.time() - start)
実行結果
fullTestOk
0.1218867301940918
hashTestOk
0.0007932186126708984
dicTestOk
6.4849853515625e-05
フルアクセスより辞書型は遅い??
再度、よく見ると辞書型のテスト結果e-05がついている
実は自作の10倍以上速かったです。