|
MAXScript に関する質問と回答 > 処理速度を上げる方法 >Bsearch を使用してテーブル検索を高速化する |
3ds Max 2009 以降で使用可能な bsearch() メソッドを使用すると、ソートされた配列内でのテーブル検索処理を非常に高速に実行できます。
配列の配列があり、各サブ配列には同じレイアウトで同じ数の要素が格納されていると仮定します。多くの場合、この情報を 1 回だけ収集した後、シーン内のすべてのオブジェクトを再度ループしなくても、レコード全体を表現する単一の検索値(「キー」)を提供することで、特定のサブ配列に格納されているデータ(「レコード」)を取得できることが望まれます。
たとえば、オブジェクトの名前、頂点とポリゴン数、およびジオメトリ内の三角形の数、四角形ポリゴン、n 角形ポリゴンを含む、シーン内のすべての編集可能ポリゴン オブジェクトのリストがこの例になります。ポリゴン側面データの収集は、比較的低速です(すべてのポリゴンをループして次数を調べる必要があるため)。このため、このデータを 1 回だけ収集し、「「Box25」という名前のオブジェクトにいくつの三角形と四角形が含まれるか」を素早く問い合わせることができます。
ユーザが作成した MAXScript 関数を使用したこの問題の解決策は、比較的低速になります。これには、配列内の線形検索、つまり、検索キー(上の例ではオブジェクトの名前)をテーブルの各サブ配列に格納された名前と比較するループが必要になります。各エントリが一意であると仮定すれば、一致するキーが見つかった瞬間に検索を停止してよいことになります。もちろん、この仮定での線形検索は、該当オブジェクトがたまたま配列内の最初のレコードにあれば非常に高速になりますが、最後のレコードにあった場合はずっと低速になります。平均の検索時間はその中間であると考えられます。
|
線形検索の例: |
|
以下は、このページで後ほど bsearch() との比較に使用する、線形検索関数の例です。簡単に説明すると、この関数は検索キーと検索対象のテーブルを渡され、一致する項目が見つかるまでこれをループします。見つかった時点で、ループを抜けて現在の値を返します。 |
fn LookupMAXScriptLoop3 itemKey itemTable = ( for i in itemTable do if i[1] == itemKey do exit with i ) |
MAXScript 関数による検索の高速化には、元のテーブルをキーだけを含む第 2 の配列を作成し、これに findItem() メソッドを使用して、レコードのインデックスを取得するという方法が考えられます。これも技術的には線形検索の一種ですが、findItem() は C++ で実装されており、MAXScript の FOR ループよりも非常に高速です。
|
FINDITEM 検索の例: |
|
ここでは、キー、検索対象のテーブル、検索テーブルと同じ順序ですべてのキーが含まれるテーブルを渡します。findItem() は、リスト内にキーが存在しない場合には 0、存在する場合は正のインデックスを返します。このインデックスを使用して、指定されたキーを持つレコードを返すことができます。 |
fn LookupMAXScriptFindItem itemKey itemTable keyTable =( local theIndex = findItem keyTable itemKey if theIndex > 0 then itemTable[theIndex] else undefined ) |
bsearch() 関数は、qsort によって事前に検索キー順にソートされたテーブルを使用することにより、この問題を解決します。この関数は、ソートに使用するのと同じ比較関数を検索に使用します。次のとおり、bsearch() はテーブルのサイズが増加してもそれに適切に対応し、テーブル内のレコードの位置には依存しません。検索するレコードが先頭でも真中でも末尾でも同じだけの時間を要します。
以下のテスト スクリプトを使用すると、さまざまな MAXScript 関数に対して、bsearch() メソッドをテストできます。
|
テスト スクリプト: |
( -- Same compare function used by bsearch and qsort: fn LookupTableComparator a b = ( if a[1] > b[1] then 1 else if a[1] < b[1] then -1 else 0 ) -- Finds an item in a lookup table; -- A lookup table is a sorted array of items, -- where each item is an array with its key as the same entry as the sort key. -- In our case the LookupTableComparator uses the first element as the key --So we have to make the search key an array too --in order to make it compatible with the qsort function! fn LookupTableLookup itemKey itemTable = ( local lookupKey = #(itemKey) bsearch lookupKey itemTable LookupTableComparator ) --MAXScript Function1 -collects all matches and returns the first, if any fn LookupMAXScriptLoop1 itemKey itemTable = ( result = for i in itemTable where i[1] == itemKey collect i if result.count > 0 then result[1] else undefined ) --MAXScript Function2 -loops until a match is found and returns the result, if any fn LookupMAXScriptLoop2 itemKey itemTable = ( for i in itemTable do if i[1] == itemKey do return i undefined ) --MAXScript Function3- loops until a match is found and exists with the result, if any fn LookupMAXScriptLoop3 itemKey itemTable = ( for i in itemTable do if i[1] == itemKey do exit with i ) --MAXScript Function loops using a while - managing the i var. is slower! fn LookupMAXScriptLoop4 itemKey itemTable = ( local i = 0 result = undefined while i < itemTable.count do ( i+=1 if itemTable[i][1] == itemKey do ( result = itemTable[i] i = itemTable.count + 1 ) ) result ) fn LookupMAXScriptFindItem itemKey itemTable keyTable = ( local theIndex = findItem keyTable itemKey if theIndex > 0 then itemTable[theIndex] else undefined ) --TEST VALUES: local searchKey ="5498"--the key to search for local iterations = 10--number of search calls local tableElements = 10000--number of elements in the table --Create an array to search in. --Its elements will have the form #("NNN", "TestNNN", NNN). --But the table could contain ANYTHING, this is just an example searchTable =for i = 1 to tableElements collect #( (i as string), "Test"+(i as string), i) --For BSearch to work, the search table has to be sorted array! st = timestamp() qsort searchTable LookupTableComparator format "QSort Time: %ms\n" (timestamp()-st) --Print the current first, middle and last element for best, mean and worst case searches format "First Element : %\n" searchTable[1] format "Mid. Element : %\n" searchTable[tableElements/2] format "Last Element : %\n" searchTable[tableElements] local returnValue--variable to show the result local st =timestamp() for i = 1 to iterations do returnValue = LookupMAXScriptLoop1 searchKey searchTable local totalTime =(timestamp()-st) format "MXS Loop 1 - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n" returnValue st =timestamp() for i = 1 to iterations do returnValue = LookupMAXScriptLoop2 searchKey searchTable local totalTime =(timestamp()-st) format "MXS Loop 2 - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n" returnValue st =timestamp() for i = 1 to iterations do returnValue = LookupMAXScriptLoop3 searchKey searchTable local totalTime =(timestamp()-st) format "MXS Loop 3 - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n" returnValue st =timestamp() for i = 1 to iterations do returnValue = LookupMAXScriptLoop4 searchKey searchTable local totalTime =(timestamp()-st) format "MXS Loop 4 - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n"returnValue local keyTable = (for i in searchTable collect i[1]) --collect all keys local st =timestamp() for i = 1 to iterations do returnValue = LookupMAXScriptFindItem searchKey searchTable keyTable local totalTime =(timestamp()-st) format "FindItem - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n"returnValue st =timestamp() for i = 1 to iterations do returnValue = LookupTableLookup searchKey searchTable local totalTime =(timestamp()-st) format "BSEARCH - Total: %ms Per Search: %ms\n" totalTime (1.0*totalTime/iterations) format "%\n"returnValue ) |
|
出力: |
QSort Time: 375ms
First Element : #("1", "Test1", 1)
Mid. Element : #("5498", "Test5498", 5498)
Last Element : #("9999", "Test9999", 9999)
MXS Loop 1 - Total: 18812ms Per Search: 18.812ms
#("5498", "Test5498", 5498)
MXS Loop 2 - Total: 9750ms Per Search: 9.75ms
#("5498", "Test5498", 5498)
MXS Loop 3 - Total: 9594ms Per Search: 9.594ms
#("5498", "Test5498", 5498)
MXS Loop 4 - Total: 18609ms Per Search: 18.609ms
#("5498", "Test5498", 5498)
FindItem - Total: 1812ms Per Search: 1.812ms
#("5498", "Test5498", 5498)
BSEARCH - Total: 0ms Per Search: 0.0ms
#("5498", "Test5498", 5498)
OK
|
qsort を使用してソートされた 10,000,5498 レコードのテーブルでは、キー「5498」はソートされたテーブルのまさしく中間にあります。
MXS Loop 1 はすべての要素を必ずループしなくてはならないため、最悪のケースのシナリオの「9999」と同じくらいパフォーマンスが悪くなります。
MXS Loop 2 関数と MXS Loop 3 関数は、ループの途中でブレイクするため半分の時間で終了します。たとえば「9999」を検索していた場合、これらの結果は MXS Loop 1 の結果に近いものとなります。これに対し、「1」を検索していた場合、テストでは最初にヒットするため非常に高速になると考えられます。
FindItem 手法では、格段に高速になることが証明されています。
最後に、BSEARCH メソッドは非常に高速であるため、その時間を測ることも不可能です(1000 回の呼び出しで 1 ミリ秒以内)。
以下の表は、すべてのメソッドについて、さまざまなテーブル サイズでの最善のケース、中間のケース、最悪のケースにおける検索あたりの時間を示しています。非常に多数の反復 (レコード数に応じて 1000 ～ 100000回) を使用することで、高精度を保証しています。
|
要素 |
キー |
Loop 1 |
Loop 2 |
Loop 3 |
Loop 4 |
FindItem |
Bsearch |
|
10 |
"1" |
0.01734ms |
0.06266ms |
0.04093ms |
0.00813ms |
0.00375ms |
0.01266ms |
|
|
"4" |
0.01719ms |
0.06781ms |
0.04562ms |
0.01844ms |
0.00421ms |
0.00813ms |
|
|
"9" |
0.01657ms |
0.07438ms |
0.05156ms |
0.03015ms |
0.00469ms |
0.01062ms |
|
100 |
"1" |
0.13031ms |
0.06437ms |
0.04078ms |
0.00797ms |
0.00406ms |
0.02032ms |
|
|
"53" |
0.12922ms |
0.12297ms |
0.10454ms |
0.13016ms |
0.00829ms |
0.00812ms |
|
|
"99" |
0.12984ms |
0.18688ms |
0.16859ms |
0.25812ms |
0.01329ms |
0.01546ms |
|
1000 |
"1" |
1.3516ms |
0.0609ms |
0.0391ms |
0.0078ms |
0.0031ms |
0.0328ms |
|
|
"548" |
1.4187ms |
0.7156ms |
0.7000ms |
1.3000ms |
0.0547ms |
0.0078ms |
|
|
"999" |
1.3875ms |
1.4250ms |
1.4156ms |
2.7469ms |
0.1063ms |
0.0187ms |
|
10000 |
"1" |
17.344ms |
0.0620ms |
0.0470ms |
0.0160ms |
0.0160ms |
0.0470ms |
|
|
"5480" |
17.250ms |
8.8590ms |
8.7970ms |
20.187ms |
1.6090ms |
0.0310ms |
|
|
"9999" |
18.641ms |
18.531ms |
18.625ms |
40.375ms |
3.6870ms |
0.0310ms |
|
100000 |
"1" |
191.56ms |
0.0630ms |
0.0470ms |
0.2650ms |
0.0150ms |
0.5940ms |
|
|
"54998" |
194.38ms |
97.180ms |
96.570ms |
3172.0ms |
19.530ms |
0.0150ms |
|
|
"99999" |
187.34ms |
187.03ms |
188.59ms |
5659.22ms |
38.750ms |
0.2660ms |
この表から分かるように、最もパフォーマンスがよいのは findItem と bsearch メソッドの 2 つです。配列内のレコード数が非常に少ない場合、findItem のほうが少し高速です。
これに対し、配列内のレコード数が増えるにつれ、中間ケースのシナリオ(中央レコードの検索)でも最悪ケースのシナリオ(末尾レコードの検索)でも、bsearch 手法のほうが結果がよくなります。一方、findItem の線形検索は最善のケースのシナリオでのみ最も良い結果となっています。このため、レコード リストがたとえば 100,000 などのように非常に大きい場合、ランダムなレコードをキーで検索するのに bsearch() を使用すると、findItem() を使用するより 1300 倍高速となり、MAXScript の最も高速な線形検索 (ループ) 関数を使用するより 6400 倍高速になります。
上記の時間には、bsearch() を使用するのに必要な qsort() によるテーブルのソートの時間、および findItem() メソッドを使用するのに必要なキー配列の収集の時間は考慮されていません。ここでは、これらの処理が別のステップで 1 回実行された後、非常に多数のランダム検索を非常に高速に実行しなくてはならない状況を想定しています。qsort を使用して 100,000 レコードをソートするのに必要な時間は約 30 秒です。このため、この検索関数を何千回も呼び出すことが分かっている場合には、30 秒かかっても bsearch() のためにリストを事前ソートすることに意味があり、結果的に検索時間を大幅に短縮することができます。
前のヒント