|
|
|
2013/6/13(Thu) 19:51:07|NO.54863
下のようなプログラムを高速化する方法を教えてください。
（プログラムは一部省略して簡略化しています。） db(0) = "010101010101" // 実際は12次元ではなく256次元のベクトル
db(1) = "000000101101"
db(2) = "000011011100"
// (省略)
db(15000) = "011110111111"
query = "001101110111"
repeat length(db)
title "" + cnt
target = db(cnt)
dist = 0
repeat 12
if strmid(query, cnt, 1) != strmid(target, cnt, 1) : dist++
loop
if dist <= 3 : mes target + " : " + dist
loop このプログラムはデータベースの中からクエリとなるベクトルとのハミング距離が
一定以下のものを列挙するプログラムです。
実際のデータベースには15000ベクトルが格納されていてベクトルは256次元です。
上のプログラムは総当りをしているのでとても遅いです。
これを改善する方法（データ構造とか）を教えてください。
LSHは試しましたが、実データでは偏りがあるようであまり速くなりません。
kd木はデータ数とデータの次元からあまり効率は上がらないようです。
|
|
|
2013/6/13(Thu) 20:17:48|NO.54865
２進数を１６進数に変換してＸＯＲ。
|
|
|
2013/6/13(Thu) 20:41:04|NO.54866
>２進数を１６進数に変換してＸＯＲ。
私の質問のしかたがまずかったようです。
知りたかったのは距離の計算の高速化ではなく、計算しなければいけないペア数の削減の仕方です。
LSHとかkd-treeは距離が近くなりそうなものの検討をつける目的に使うことができます。
|
|
|
2013/6/13(Thu) 20:58:39|NO.54867
ペア数の削減の仕方は、HSPとは関係がないのではないでしょうか。他の場所で聞くとより詳しい人から答えがもらえると思います。
このような大量の処理を行う場合は、HSPはインタプリタなのでCなどで作った場合に比べて遅さが目立ちますから、他の言語を使うことも検討してみましょう。
HSPで行う場合は、計算の高速化はKDさんの方法がよいでしょう。1つのデータが256bitならばsdimで配列を確保して、32bitずつ切り出してxorするのがいいかと思います。
また、strmidなど文字列処理はHSPでは遅いですから、peekを使ってみても少し改善すると思います。
|
|
|
2013/6/13(Thu) 21:06:08|NO.54869
>上のプログラムは総当りをしているのでとても遅いです。
NO.54863が遅い一番の原因はtitle命令
title変更は1ms近く時間掛かる
|
|
|
2013/6/13(Thu) 21:12:21|NO.54871
まず先に 自分はこういうなんちゃら法とかのアルゴリズムは全く知りません
HSPは計算速度も他の言語に比べて遅めなので○○法を使ったとしてそこまで早くなる気がしません
moeさんの書かれている方法で、256次元で5001ベクトルの処理時間は626msでした
titleとmesは除きました
dim query_,256
repeat 256
query_ = peek(query,cnt)
loop
repeat length(db)
target = db(cnt)
dist = 0
repeat 256
if query_.cnt != peek(target,cnt) : dist++
loop
loop
だと204msになります
総当りといえば総当りですが、一応計算量は半分で速度は3倍です
総当りでも総当りの最適化というのも有りかなと思います
|
|
|
2013/6/13(Thu) 21:59:13|NO.54879
誰も問題の本質が見えてないとか・・・
質問者さんは絶対的な計算時間じゃなくオーダーの話をしてるのに全く的外れな回答しかないね。
で、質問に関する回答だけどSB-LSHを試してないなら試してみるのもいいんじゃないかな。
|
|
|
2013/6/13(Thu) 22:13:24|NO.54880
繰り返しになりますが、絶対的な計算時間ではなくオーダーの話をしたいならそもそもこの掲示板に投稿するのが的外れなので、このような回答がつくのは当然ではないかと思います。
理論的にはオーダーを気にするのが重要なのは分かりますが、実際にプログラムを動かそうとしたら、絶対的な計算時間のほうも重要なのです。
|
|
|
2013/6/15(Sat) 01:02:19|NO.54896
クエリ？ハミング距離？オーダー？といった状態ですので
見当違いな回答でしたらごめんなさい。
ソート順に検査して行き、相違箇所が閾値以上ならその場所と値を保持。
以降その値に変化がある迄どんどんスキップするというのはどうでしょうか？
効果は微妙、閾値とベクトルや次元数との比率がかなり高くないと逆効果。
止めにソート処理自体に恐ろしく時間が掛かりますけど…
#const dD 24 ;次元数?
#const dL $4000 ;ベクトル数?
#const distout 4 ;ハミング距離?閾値 (ハズレにする相違数)
sdim db,dD+1,dL ;ベクトル配列
sdim query,dD+1 ;クエリ?
sdim target,dD+1
dim sa,dL ;ソート用配列
dim distI,distout ;判定用配列a (位置)
dim distV,distout ;判定用配列b (値)
dim dist :dim cHit :dim cSkp
#module
#uselib "kernel32.dll"
#cfunc global _GetTickCount "GetTickCount"
#define global GetTickCount _GetTickCount()
#defcfunc strcmp var p0, var p1, local a ;文字列比較
a=0,0,0 :*@ :a.1=peek(p0,a),peek(p1,a)
if(a.1)*(a.1==a.2){a.0++ :goto *@b} :return a.1-a.2
#deffunc mSort array p0, array p1, array p2, int p3, int p4, local a ;ソート配列作成
a.0=p3,0,0,p4,p4-p3+1 :a.2=a.4/2+p3 :a.1=a.2-1
if(a.1-a.0){mSort p0,p1,p2,a.0,a.1} :if(a.3-a.2){mSort p0,p1,p2,a.2,a.3}
repeat a.4
If(a.0>a.1){p2(cnt)=p1(a.2) :a.2++ :continue}
If(a.2>a.3){p2(cnt)=p1(a.0) :a.0++ :continue}
If(strcmp(p0(p1(a.0)),p0(p1(a.2)))>0){p2(cnt)=p1(a.2) :a.2++}else{p2(cnt)=p1(a.0) :a.0++}
loop
repeat a.4 :p1(cnt+p3)=p2(cnt) :loop
return
#global
randomize
i=(dD+20)*6 :if(i<320){i=320}
screen 0,i,240 :color :boxf
font msgothic,12 :hsvcolor ,,255 :pos 2,0
mes "ベクトル配列つくってます.."
repeat dL ;ベクトルでっち上げ
dup s,db(cnt) :s="" :i.0=rnd($1000),0
*@ :repeat 12
if(i&1){s+="1"}else{s+="0"} :i.0>>=1
i.1++ :if(i.1>=dD){break} :loop
if(i.1<dD){i.0=rnd($1000) :goto *@b}
loop
sdim s :ct=GetTickCount
mes "ソート配列つくってます.."
repeat dL :sa(cnt)=cnt :loop ;ソート配列の初期化
dim tmp,dL :mSort db,sa,tmp,0,dL-1
logmes strf("SORT:%dms",GetTickCount-ct) :dim tmp
hsvcolor ,,255 :mes "press any key <check_a> [esc:EXIT]"
*@ :await 5 :stick i :if(i==0){goto *@b} :if(i&128){end}
*check_a
query="" :i.0=rnd($1000),0
*@ :repeat 12 ;クエリでっち上げ
if(i&1){query+="1"}else{query+="0"} :i.0>>=1
i.1++ :if(i.1>=dD){break} :loop
if(i.1<dD){i.0=rnd($1000) :goto *@b}
title "check_a" :ct=GetTickCount :cHit=0
repeat dL
target=db(cnt) :dist=0
repeat dD
if(peek(query,cnt)^peek(target,cnt)){dist++ :if(dist>=distout){break}}
loop
if(dist<distout){
if((cHit\20)==0){color :boxf :hsvcolor ,,255 :pos 2,0} :cHit++
s=strf("%s :%2d [%5d]",target,dist,cnt) :mes s ;:logmes s
}
loop
s=strf("a|%2d/%d %dms",cHit,dL,GetTickCount-ct) :title s :LogMes s
if(((cHit+1)\20)<2){color :boxf :hsvcolor ,,255 :pos 2,0}
hsvcolor 48,192,255 :mes strf("%s : query",query)
hsvcolor ,,255 :mes "press any key <check_b> [esc:EXIT]"
*@ :await 5 :stick i :if(i==0){goto *@b} :if(i&128){end}
*check_b
title "check_b" :ct=GetTickCount :cHit=0 :cSkp=0 :distI=-1
repeat dL
target=db(sa(cnt)) :dist=0
if(distI>=0){
repeat distout
if(peek(target,distI(cnt))==distV(cnt)){dist++}else{break}
loop
if(dist==distout){cSkp++ :continue} :dist=0
}
repeat dD
i=peek(target,cnt)
if(peek(query,cnt)^i){
distI(dist)=cnt :distV(dist)=i
dist++ :if(dist>=distout){break}
}
loop
if(dist<distout){distI=-1
if((cHit\20)==0){color :boxf :hsvcolor ,,255 :pos 2,0} :cHit++
s=strf("%s :%2d [%5d]",target,dist,sa(cnt)) :mes s ;:logmes s
}
loop
s=strf("b|%2d/%d %dms [%dskp]",cHit,dL,GetTickCount-ct,cSkp) :title s :LogMes s
if(((cHit+1)\20)<2){color :boxf :hsvcolor ,,255 :pos 2,0}
hsvcolor 48,192,255 :mes strf("%s : query",query)
hsvcolor ,,255 :mes "press any key <check_a> [esc:EXIT]"
*@ :await 5 :stick i :if(i==0){goto *@b} :if(i&128){end}
goto *check_a
| |
|
|
2013/6/15(Sat) 03:13:00|NO.54898
「Cで書けよ」というツッコミは横に置いて、実験してみました。
まず、乱数で0・1を生成して
----------------------
01011101010...1010110
10101110101...1011111
...
10110111111...1110010
----------------------
と、15000行のテキストデータを作成。これをタネとして、
読み込み→(乱数で生成した)クエリを検索させる→10回行い、時間の平均値を取る
といった方法で検証を行いました。
(Core i5-3210M、メモリ4GB、Win764bit機で実施)
まず、質問者が書いている方法。これで平均2503.5[ms/query]。
randomize
#uselib "winmm.dll"
#cfunc timer "timeGetTime"
#func timeBeginPeriod "timeBeginPeriod" int
#func timeEndPeriod "timeEndPeriod" int
#define dimention 256
#define size 15000
#define times 10
sdim query, dimention
candist = 3
;データ読み込み
sdim db, dimention, size
notesel buf :noteload "db.txt"
repeat size
memcpy db(cnt), buf, dimention, ,cnt * (dimention + 2)
loop
;クエリを投げて速度計測
alltime=0
timeBeginPeriod 1
for k,0,times
;クエリ作成
repeat dimention
poke query, cnt, '0' + rnd(2)
loop
;検索
time_s=timer()
count = 0 ;DB中ヒットした数
repeat size
target = db(cnt)
dist = 0
repeat dimention
if strmid(query, cnt, 1) != strmid(target, cnt, 1): dist++
loop
if dist <= candist :count++
loop
alltime += timer() - time_s
next
timeEndPeriod 1
dialog ""+(1.0 * alltime / times)+"[ms/query]"
stop
次に、NO.54871が示した方法。これで平均819.9[ms/query]。通常の3倍ですな。
randomize
#uselib "winmm.dll"
#cfunc timer "timeGetTime"
#func timeBeginPeriod "timeBeginPeriod" int
#func timeEndPeriod "timeEndPeriod" int
#define dimention 256
#define size 15000
#define times 10
sdim query, dimention
candist = 3
;データ読み込み
sdim db, dimention, size
notesel buf :noteload "db.txt"
repeat size
memcpy db(cnt), buf, dimention, ,cnt * (dimention + 2)
loop
;クエリを投げて速度計測
alltime=0
timeBeginPeriod 1
for k,0,times
;クエリ作成
repeat dimention
poke query, cnt, '0' + rnd(2)
loop
;検索
time_s=timer()
dim query_, dimention
repeat dimention
query_ = peek(query, cnt)
loop
count = 0 ;DB中ヒットした数
repeat size
target = db(cnt)
dist = 0
repeat dimention
if query_(cnt) != peek(target,cnt): dist++
loop
if dist <= candist :count++
loop
alltime += timer() - time_s
next
timeEndPeriod 1
dialog ""+(1.0 * alltime / times)+"[ms/query]"
stop
最後に、NO.54867さんが示した方法。これで141.1[ms/query]。速度が更に6倍に！
randomize
#uselib "winmm.dll"
#cfunc timer "timeGetTime"
#func timeBeginPeriod "timeBeginPeriod" int
#func timeEndPeriod "timeEndPeriod" int
#const dimention 256
#const dimsize dimention / 32
#const size 15000
#const times 10
candist = 3
;データ読み込み
dim db, dimsize, size
notesel buf :noteload "db.txt"
repeat size
i = cnt
repeat dimsize
j = cnt
db(j, i) += peek(buf, i * (dimention + 2) + j * 32) - '0'
repeat 31, 1
db(j, i) <<= 1
db(j, i) += peek(buf, i * (dimention + 2) + j * 32 + cnt) - '0'
loop
loop
loop
;クエリを投げて速度計測
alltime=0
timeBeginPeriod 1
for k,0,times
;クエリ作成
dim query, dimsize
repeat dimsize
j = cnt
query(j) += rnd(2)
repeat 31, 1
query(j) <<= 1
query(j) += rnd(2)
loop
loop
;検索
time_s=timer()
count = 0 ;DB中ヒットした数
repeat size
i = cnt
dist = 0
repeat dimsize
diff = query(cnt) ^ db(cnt, i)
diff = (diff & $55555555) + (diff >> 1 & $55555555)
diff = (diff & $33333333) + (diff >> 2 & $33333333)
diff = (diff & $0f0f0f0f) + (diff >> 4 & $0f0f0f0f)
diff = (diff & $00ff00ff) + (diff >> 8 & $00ff00ff)
dist += (diff & $0000ffff) + (diff >>16 & $0000ffff)
loop
if dist <= candist :count++
loop
alltime += timer() - time_s
next
timeEndPeriod 1
dialog ""+(1.0 * alltime / times)+"[ms/query]"
stop
……NO.54896は、内容がよく分からなかったので検証していません。ごめんなさい。
| |
|
|
2013/6/15(Sat) 06:28:59|NO.54899
んー。プログラム計算量を削減したいといっても、前提のデータベース配列に格納する処理を計算量に含めて考えるのか、
それとも一度読み込むだけなのか、どっちかわからないと改善方法は回答できないと思うよ。
//��
db(0) = "010101010101" // 実際は12次元ではなく256次元のベクトル
db(1) = "000000101101"
db(2) = "000011011100"
// (省略)
db(15000) = "011110111111"
//��End
//��
query = "001101110111"
repeat length(db)
title "" + cnt
target = db(cnt)
dist = 0
repeat 12
if strmid(query, cnt, 1) != strmid(target, cnt, 1) : dist++
loop
if dist <= 3 : mes target + " : " + dist
loop
//��End
�，鉢△�常に対で処理されるのであれば、たぶんプログラム計算量の削減は難しいと思う。
�，鉢△�まったく別々での処理であれば、�，暴萢�を行えば、�△僚萢�は最大で次元数 x 次元数(256次元 x 256種類)の処理で済む。
|
|
|
2013/6/15(Sat) 10:04:38|NO.54907
まずは単純に処理回数を減らせないかを考えるのが良いと思います。
目的と比較データなど、もう少し明確になってると改善しやすいのでは思います。
例えば、目的が「dist(違い)が3以下」を求めるのであれば２重ループの回数削減が期待できます。
repeat 12
if strmid(query, cnt, 1) != strmid(target, cnt, 1) : dist++
if dist>3: break //←追加、dist>3の場合比較処理しても意味がないので抜ける
loop
また、以下のようにdb(n)値が昇順にならんでいるデータであれば１重ループの回数を半分にできます。
比較対象queryがdb(0)〜db(7499)、db(7500)〜db(15000)のどちら側にあるかを先に決めて、あるほうのデータのみ比較処理します。
db(0)="000000000001"
db(1)="000000000010"
db(2)="000000000011"
・・・
db(7499)="111110111111"
db(7500)="111111000000"
db(7501)="111111000001"
・・・
db(15000)="111111111111" // 実際にはdb(32767)？
query = "001101110111"
st=0: mx=7499: if strmid(query,1,6)==strmid(db(7500),1,6):st=7500: mx=15000 //←追加 半分だけ比較する
//↓に変更 repeat length(db)
repeat mx, st
|
|
|
2013/6/15(Sat) 13:31:33|NO.54909
No.54899 で書いていなかったけど、計算量 = length(db) * 256次元文字数 の話ね。
最終的な計算量は、ループ回数 x 比較回数として計算するとわかりやすい。
単純に、256次元 2進数文字列 256種 の場合で、データベースが 15000 項目だとすると、
最大で、256 * 15000 = 3,840,000 の比較が必要である。
他の回答者さんも回答している通り、データベースを配列に格納している条件が整えば、改善する方法もあるが、
前提となる、データベース配列に格納する際に何らかの処理をすれば、その処理分を計算量として加算しなければならない。
1.データベースはランダムである。
2.dist は 3以上で判断する。
しか情報がないので回答のしようがない。
すべての状況に当てはまる事だけど、最初から削減は難しいと思う。
オーダー最適化が済むのは、2回目以降(データベースの登録処理が終了し再度必要とする場合)の処理である。
|
|
|
2013/6/15(Sat) 20:11:06|NO.54926
NO.54896 が説明不足だったようなので一応補足を…
基本的には NO.54907 の さか様のような
ハズレ(dist>3)だと解った時点で次へ移行といったものです。
普通にデータ順、各データを先頭から検査するものが check_a。
ソート順、先頭からの検査の前に定点検査を加えたものが check_b。
「データ傾向によっては、ちょっとだけ早くなるケースもあるみたいですよ。」
と云うのが NO.54896 のスクリプトの内容(のつもり)です。
データベースがランダムだとすると、1/2^239でそもそも当る気がしませんし
実際はかなり傾向が偏ったものなのでは？という想像の基に思い付きで書いてみました。
|
|
プログラムの高速化
