Interpolating Search

wiki

Showing revision 7
When searching for a value in a sorted array, the to preferring search algorithm is the binary search. In certain cases although we can be a lot faster using an interpolating search mechanism. tables optimal for a interpolating search are { 1,2,3,4,5,6,7,8,9,10 }, where as tables looking like { 1,1,1,1,1,1,1,1,1,2,10 } and searching it for the value 2 will use a alot more time than the binary search. So it depends on the scenario, but if used right one can be 3 times as fast as the binary search. I wrote an extra function for searching a reversed table, since it was the better option rather to changing all the variables and the < check.

--[[
   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™

Testsuit:

-- 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

See Also