プログラムの高速化

moe        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木はデータ数とデータの次元からあまり効率は上がらないようです。


KA        2013/6/13(Thu) 20:17:48|NO.54865

2進数を16進数に変換してXOR。


moe        2013/6/13(Thu) 20:41:04|NO.54866

>2進数を16進数に変換してXOR。
私の質問のしかたがまずかったようです。
知りたかったのは距離の計算の高速化ではなく、計算しなければいけないペア数の削減の仕方です。
LSHとかkd-treeは距離が近くなりそうなものの検討をつける目的に使うことができます。


test        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近く時間掛かる


kanahiron        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倍です
総当りでも総当りの最適化というのも有りかなと思います


kekeke        2013/6/13(Thu) 21:59:13|NO.54879

誰も問題の本質が見えてないとか・・・
質問者さんは絶対的な計算時間じゃなくオーダーの話をしてるのに全く的外れな回答しかないね。

で、質問に関する回答だけどSB-LSHを試してないなら試してみるのもいいんじゃないかな。


test        2013/6/13(Thu) 22:13:24|NO.54880

繰り返しになりますが、絶対的な計算時間ではなくオーダーの話をしたいならそもそもこの掲示板に投稿するのが的外れなので、このような回答がつくのは当然ではないかと思います。

理論的にはオーダーを気にするのが重要なのは分かりますが、実際にプログラムを動かそうとしたら、絶対的な計算時間のほうも重要なのです。


774        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


YSR        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は、内容がよく分からなかったので検証していません。ごめんなさい。


MillkeyStars        2013/6/15(Sat) 06:28:59|NO.54899

んー。プログラム計算量を削減したいといっても、前提のデータベース配列に格納する処理を計算量に含めて考えるのか、
それとも一度読み込むだけなのか、どっちかわからないと改善方法は回答できないと思うよ。


//@ db(0) = "010101010101" // 実際は12次元ではなく256次元のベクトル db(1) = "000000101101" db(2) = "000011011100" // (省略) db(15000) = "011110111111" //@End //A 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 //AEnd

@とAが常に対で処理されるのであれば、たぶんプログラム計算量の削減は難しいと思う。
@とAがまったく別々での処理であれば、@に処理を行えば、Aの処理は最大で次元数 x 次元数(256次元 x 256種類)の処理で済む。


さか        2013/6/15(Sat) 10:04:38|NO.54907

まずは単純に処理回数を減らせないかを考えるのが良いと思います。
目的と比較データなど、もう少し明確になってると改善しやすいのでは思います。

例えば、目的が「dist(違い)が3以下」を求めるのであれば2重ループの回数削減が期待できます。
repeat 12
if strmid(query, cnt, 1) != strmid(target, cnt, 1) : dist++
if dist>3: break //←追加、dist>3の場合比較処理しても意味がないので抜ける
loop

また、以下のようにdb(n)値が昇順にならんでいるデータであれば1重ループの回数を半分にできます。
比較対象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


MillkeyStars        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回目以降(データベースの登録処理が終了し再度必要とする場合)の処理である。


774        2013/6/15(Sat) 20:11:06|NO.54926

NO.54896 が説明不足だったようなので一応補足を…
基本的には NO.54907 の さか様のような
ハズレ(dist>3)だと解った時点で次へ移行といったものです。

普通にデータ順、各データを先頭から検査するものが check_a。
ソート順、先頭からの検査の前に定点検査を加えたものが check_b。
「データ傾向によっては、ちょっとだけ早くなるケースもあるみたいですよ。」
と云うのが NO.54896 のスクリプトの内容(のつもり)です。

データベースがランダムだとすると、1/2^239でそもそも当る気がしませんし
実際はかなり傾向が偏ったものなのでは?という想像の基に思い付きで書いてみました。