插值搜索
 |
||
|
插值搜索 |
|
--[[ Interpolating Search v 0.2 LUA 5.1 compatible Can only search for values of type number table.intsearch( table, value [, compval ] ), for searching a normal sorted table table.intsearchrev( table, value [, compval ] ), for searching a reversed sorted table If the value is found: it returns a table holding all the matching indices (e.g. { startindice,endindice } ) endindice may be the same as startindice if only one matching indice was found If compval is given: then it must be a function that takes one value and returns a second value2, to be compared with the searched value, e.g.: compvalue = function( value ) return value[1] end Return value: on success: a table holding matching indices (e.g. { startindice,endindice } ) on failure: nil ]]-- do -- Avoid heap allocs for performance local default_fcompval = function( value ) return value end function table.intsearch( t,value,fcompval ) -- Initialise functions local fcompval = fcompval or default_fcompval -- Inistialise numbers local ilow,ihigh = 1,#t -- return on empty table if not t[ilow] then return end -- get values of indices local _ilow,_ihigh = fcompval( t[ilow] ),fcompval( t[ihigh] ) -- make sure slope cannot become 0 while _ilow and _ilow < _ihigh do -- get interpolated position local pos = math.floor( (value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow -- check for out of range if pos < ilow or pos > ihigh then return end -- get compare value local compval = fcompval( t[pos] ) if value == compval then -- insert found position local tfound,num = { pos,pos },pos-1 -- get all values that match while value == fcompval( t[num] ) do tfound[1],num = num,num-1 end num = pos+1 while value == fcompval( t[num] ) do tfound[2],num = num,num+1 end return tfound -- keep searching, -- left part of the table elseif value < compval then ihigh = pos-1 else ilow = pos+1 end _ilow,_ihigh = fcompval( t[ilow] ),fcompval( t[ihigh] ) end if value == fcompval( t[ilow] ) then -- only add values --> of ilow local tfound,num = { ilow,ilow },ilow+1 while value == fcompval( t[num] ) do tfound[2],num = num,num+1 end return tfound end end -- Interpolated search on a reversed table function table.intsearchrev( t,value,fcompval ) -- Initialise functions local fcompval = fcompval or default_fcompval -- Inistialise numbers local ilow,ihigh = 1,#t if not t[ilow] then return end local _ilow,_ihigh = fcompval( t[ilow] ),fcompval( t[ihigh] ) while _ilow and _ilow > _ihigh do -- get interpolated position local pos = math.floor( (_ihigh-value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow -- check for out of range if pos < ilow or pos > ihigh then return end local compval = fcompval( t[pos] ) if value == compval then -- insert found position local tfound,num = { pos,pos },pos-1 -- get all values that match while value == fcompval( t[num] ) do tfound[1],num = num,num-1 end num = pos+1 while value == fcompval( t[num] ) do tfound[2],num = num,num+1 end return tfound -- keep searching, -- left part of the table elseif value > compval then ihigh = pos-1 else ilow = pos+1 end _ilow,_ihigh = fcompval( t[ilow] ),fcompval( t[ihigh] ) end if value == fcompval( t[ilow] ) then -- only add values --> of ilow local tfound,num = { ilow,ilow },ilow+1 while value == fcompval( t[num] ) do tfound[2],num = num,num+1 end return tfound end end end -- CHILLCODE�
-- test: table size 0 t = {} local v = table.intsearch(t, 5); assert(v == nil) -- test: table size 1 t = {5} local v = table.intsearch(t, 4); assert(v == nil) local v = table.intsearch(t, 5); assert(v[1] == 1) local v = table.intsearch(t, 6); assert(v == nil) -- test: table size 2 t = {4,6} local v = table.intsearch(t, 3); assert(v == nil) local v = table.intsearch(t, 4); assert(v[1] == 1) local v = table.intsearch(t, 5); assert(v == nil) local v = table.intsearch(t, 6); assert(v[1] == 2) local v = table.intsearch(t, 7); assert(v == nil) -- test: typical, with duplicate t = {0,2,4,4,6,8,10} local v = table.intsearch(t, 0); assert(v[1] == 1) local v = table.intsearch(t, 10); assert(v[1] == 7) local v = table.intsearch(t, 4); assert(v[1] == 3 and v[2] == 4) local v = table.intsearch(t, 5); assert(v == nil) local v = table.intsearch(t, 11); assert(v == nil) local v = table.intsearch(t, -1); assert(v == nil) -- test: identical t = {1,1,1,1,1,1,1,1,1,1} local v = table.intsearch(t, 1); assert(v[1] == 1 and v[2] == 10) -- test: fcomp t = {10,52,34,44,86,38} local v = table.intsearch(t, 6, function(v) return v % 10 end); assert(v[1] == 5) local v = table.intsearch(t, 4, function(v) return v % 10 end); assert(v[1] == 3 and v[2] == 4) -- test: reverse t = {10,8,6,4,4,2,0} local v = table.intsearchrev(t, 6); assert(v[1] == 3) local v = table.intsearchrev(t, 4); assert(v[1] == 4 and v[2] == 5) print "DONE"
--[[ Interpolating Search on a String LUA 5.1 compatible Can only search sorted tables with value string table.intsearchstr( table, value ), for searching a normal sorted table table.intsearchstrrev( table, value ), for searching a reversed sorted table If the value is found: it returns a table holding all the matching indices (e.g. { startindice,endindice } ) endindice may be the same as startindice if only one matching indice was found Return value: on success: a table holding matching indices (e.g. { startindice,endindice } ) on failure: nil ]]-- do -- Avoid heap allocs for performance local getbytevalue = function( value ) if value then local num,mul = 0,1 -- set bytedept, 4 or 5 seems appropriate for i = 4,1,-1 do local byte = string.byte( string.sub( value,i,i ) ) or -1 byte,num,mul = byte + 1,num + mul*byte,mul*257 end return num end end -- Load the optimised binary function -- Avoid heap allocs for performance local fcompf = function( a,b ) return a < b end local fcompr = function( a,b ) return a > b end local function tablebinsearch( t,value,reversed,iStart,iEnd ) -- Initialise functions local fcomp = reversed and fcompr or fcompf -- Initialise numbers local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0 -- Binary Search while iStart <= iEnd do -- calculate middle iMid = math.floor( (iStart+iEnd)/2 ) -- get compare value local value2 = t[iMid] -- get all values that match if value == value2 then local tfound,num = { iMid,iMid },iMid - 1 while value == t[num] do tfound[1],num = num,num - 1 end num = iMid + 1 while value == t[num] do tfound[2],num = num,num + 1 end return tfound -- keep searching elseif fcomp( value,value2 ) then iEnd = iMid - 1 else iStart = iMid + 1 end end end -- The interpolationg Search Function on a String function table.intsearchstr( t,value ) -- Inistialise numbers local ilow,ihigh = 1,#t -- return on empty table if not t[ilow] then return end -- get byte values values of indices and searched value local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value) local oldpos = -1 -- make sure slope cannot become 0 while _ilow and _ilow < _ihigh do -- get interpolated position local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow -- check for out of range if pos < ilow or pos > ihigh then return end -- check for real match if value == t[pos] then -- insert found position local tfound,num = { pos,pos },pos-1 -- get all values that match while value == t[num] do tfound[1],num = num,num-1 end num = pos+1 while value == t[num] do tfound[2],num = num,num+1 end return tfound -- keep searching, -- left part of the table,check for real lower elseif value < t[pos] then ihigh = pos-1 else ilow = pos+1 end -- check if new position is further than 1 away if oldpos+1 == pos or oldpos-1 == pos then -- start binary search return tablebinsearch( t,value,_,ilow,ihigh ) end _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos end -- initiate binary seach function here since we could be in a flat for the interpolating search return tablebinsearch( t,value,_,ilow,ihigh ) end -- The interpolationg Search Function on a String function table.intsearchstrrev( t,value ) -- Inistialise numbers local ilow,ihigh = 1,#t -- return on empty table if not t[ilow] then return end -- get byte values values of indices and searched value local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value) local oldpos = -1 -- make sure slope cannot become 0 while _ilow and _ilow > _ihigh do -- get interpolated position local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow -- check for out of range if pos < ilow or pos > ihigh then return end -- check for real match if value == t[pos] then -- insert found position local tfound,num = { pos,pos },pos-1 -- get all values that match while value == t[num] do tfound[1],num = num,num-1 end num = pos+1 while value == t[num] do tfound[2],num = num,num+1 end return tfound -- keep searching, -- left part of the table,check for real lower elseif value > t[pos] then ihigh = pos-1 else ilow = pos+1 end -- check if new position is further than 1 away if oldpos+1 == pos or oldpos-1 == pos then -- start binary search return tablebinsearch( t,value,1,ilow,ihigh ) end _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos end -- initiate binary seach function here since we could be in a flat for the interpolating search return tablebinsearch( t,value,1,ilow,ihigh ) end end -- CHILLCODE�
-- test: table size 0 t = { "a","a","a","a","a","a","a","a","a","a","aa","z" } local v = table.intsearchstr(t, "aa"); assert(v[1] == 11) -- test flat for interpolatin search function t = { "aabb","aabbcc","aabc","aabc","aabc","aabc","aabc","aabc","aabc","aabc","aabc","aabc","aabc","aabca","aabcc" } local v = table.intsearchstr(t, "aabca"); assert(v[1] == 14) -- test: table size 1 t = { "a" } local v = table.intsearchstr(t, "b"); assert(v == nil) local v = table.intsearchstr(t, "a"); assert(v[1] == 1) local v = table.intsearchstr(t, "c"); assert(v == nil) -- test: table size 2 t = {"a","c"} local v = table.intsearchstr(t, "0"); assert(v == nil) local v = table.intsearchstr(t, "a"); assert(v[1] == 1) local v = table.intsearchstr(t, "b"); assert(v == nil) local v = table.intsearchstr(t, "c"); assert(v[1] == 2) local v = table.intsearchstr(t, "d"); assert(v == nil) -- test: typical, with duplicate t = {"a","b","c","c","d","e","f"} local v = table.intsearchstr(t, "a"); assert(v[1] == 1) local v = table.intsearchstr(t, "f"); assert(v[1] == 7) local v = table.intsearchstr(t, "c"); assert(v[1] == 3 and v[2] == 4) local v = table.intsearchstr(t, "da"); assert(v == nil) local v = table.intsearchstr(t, "fa"); assert(v == nil) local v = table.intsearchstr(t, "0"); assert(v == nil) -- test: identical t = {"a","a","a","a","a","a","a","a","a","a"} local v = table.intsearchstr(t, "a"); assert(v[1] == 1 and v[2] == 10) -- test: reverse t = {"f","e","d","c","c","b","a"} local v = table.intsearchstrrev(t, "d"); assert(v[1] == 3) local v = table.intsearchstrrev(t, "c"); assert(v[1] == 4 and v[2] == 5) print "DONE"
