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