Ordered Associative Table
 |
||
|
Ordered Associative Table |
|
--// CHILL CODE //-- -- table.ordered( [comp] ) -- -- Lua 5.x add-on for the table library. -- Table using sorted index. Uses binary table for fast Lookup. -- http://lua-users.org/wiki/OrderedTable by PhilippeFremy -- table.ordered( [comp] ) -- Returns an ordered table. Can only take strings as index. -- fcomp is a comparison function behaves behaves just like -- fcomp in table.sort( t [, fcomp] ). function table.ordered(fcomp) local newmetatable = {} -- sort func newmetatable.fcomp = fcomp -- sorted subtable newmetatable.sorted = {} -- behavior on new index function newmetatable.__newindex(t, key, value) if type(key) == "string" then local fcomp = getmetatable(t).fcomp local tsorted = getmetatable(t).sorted table.binsert(tsorted, key , fcomp) rawset(t, key, value) end end -- behaviour on indexing function newmetatable.__index(t, key) if key == "n" then return table.getn( getmetatable(t).sorted ) end local realkey = getmetatable(t).sorted[key] if realkey then return realkey, rawget(t, realkey) end end local newtable = {} -- set metatable return setmetatable(newtable, newmetatable) end --// table.binsert( table, value [, comp] ) -- -- LUA 5.x add-on for the table library. -- Does binary insertion of a given value into the table -- sorted by [,fcomp]. fcomp is a comparison function -- that behaves like fcomp in in table.sort(table [, fcomp]). -- This method is faster than doing a regular -- table.insert(table, value) followed by a table.sort(table [, comp]). function table.binsert(t, value, fcomp) -- Initialise Compare function local fcomp = fcomp or function( a, b ) return a < b end -- Initialise Numbers local iStart, iEnd, iMid, iState = 1, table.getn( t ), 1, 0 -- Get Insertposition while iStart <= iEnd do -- calculate middle iMid = math.floor( ( iStart + iEnd )/2 ) -- compare if fcomp( value , t[iMid] ) then iEnd = iMid - 1 iState = 0 else iStart = iMid + 1 iState = 1 end end local pos = iMid+iState table.insert( t, pos, value ) return pos end -- Iterate in ordered form -- returns 3 values i, index, value -- ( i = numerical index, index = tableindex, value = t[index] ) function orderedPairs(t) return orderedNext, t end function orderedNext(t, i) i = i or 0 i = i + 1 local index = getmetatable(t).sorted[i] if index then return i, index, t[index] end end
Tests:
t2= table.ordered() t2["A"] = 1 t2.B = 2 t2.C = 3 t2.D = 4 t2.E = 5 t2.F = 6 t2.G = 7 t2.H = 8 print("Normal iteration ordered table") -- will iterate over the table by next index table.foreach( t2, print )
Results:
Normal iteration ordered table A 1 C 3 B 2 E 5 D 4 G 7 F 6 H 8
Tests:
print("Ordered Iteration") for i,index,v in orderedPairs(t2) do print(index, v) end
Results:
Ordered Iteration A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8
Tests:
-- same example but reveres ordered t2= table.ordered( function(a,b) return b < a end ) t2["A"] = 1 t2.B = 2 t2.C = 3 t2.D = 4 t2.E = 5 t2.F = 6 t2.G = 7 t2.H = 8
print("Ordered Iteration of Reverse") for i,index,v in orderedPairs(t2) do print(index, v) end
Results:
Ordered Iteration of Reverse H 8 G 7 F 6 E 5 D 4 C 3 B 2 A 1
Now due to the problem that one cannot delete any entries, another option is to totally switch to a binary table and accessing it through t[index], while doing the sorting things in metatables.
--// CHILL CODE //-- -- table.ordered( [sorted reverse], [type] ) v 2 -- Lua 5.x add-on for the table library -- Table using sorted index, with binary table for fast lookup. -- http://lua-users.org/wiki/OrderedTable by PhilippeFremy -- table.ordered( [sorted reverse], [type] ) -- Gives you back a ordered table, can only take entered type -- as index returned by type(index), by default "string" -- sorted reverse, sorts the table in reverse order, else normal -- stype is the deault index type returned by type( index ), -- by default "string", it is only pssible to set one type as index -- will effectively create a binary table, and will always lookup -- through binary when an index is called function table.ordered(ireverse, stype) local newmetatable = {} -- set sort function if ireverse then newmetatable._ireverse = 1 function newmetatable.fcomp(a, b) return b[1] < a[1] end else function newmetatable.fcomp(a, b) return a[1] < b[1] end end -- set type by default "string" newmetatable.stype = stype or "string" -- fcomparevariable function newmetatable.fcompvar(value) return value[1] end -- sorted subtable newmetatable._tsorted = {} -- behaviour on new index function newmetatable.__newindex(t, key, value) if type(key) == getmetatable(t).stype then local fcomp = getmetatable(t).fcomp local fcompvar = getmetatable(t).fcompvar local tsorted = getmetatable(t)._tsorted local ireverse = getmetatable(t)._ireverse -- value is given so either update or insert newly if value then local pos, _ = table.bfind(tsorted, key, fcompvar, ireverse) -- if pos then update the index if pos then tsorted[pos] = {key, value} -- else insert new value else table.binsert(tsorted, {key, value}, fcomp) end -- value is nil so remove key else local pos, _ = table.bfind(tsorted, key, fcompvar, ireverse) if pos then table.remove(tsorted, pos) end end end end -- behavior on index function newmetatable.__index(t, key) if type(key) == getmetatable(t).stype then local fcomp = getmetatable(t).fcomp local fcompvar = getmetatable(t).fcompvar local tsorted = getmetatable(t)._tsorted local ireverse = getmetatable(t)._ireverse -- value if key exists local pos, value = table.bfind(tsorted, key, fcompvar, ireverse) if pos then return value[2] end end end -- set metatable return setmetatable({}, newmetatable) end --// table.binsert( table, value [, comp] ) -- Lua 5.x add-on for the table library -- Binary inserts given value into the table sorted by [,fcomp] -- fcomp is a comparison function that behaves just like -- fcomp in table.sort( table [, comp] ). -- This method is faster than doing a regular -- table.insert(table, value) followed by a table.sort(table [, comp]). function table.binsert(t, value, fcomp) -- Initialize compare function local fcomp = fcomp or function(a, b) return a < b end -- Initialize numbers local iStart, iEnd, iMid, iState = 1, table.getn( t ), 1, 0 -- Get insert position while iStart <= iEnd do -- calculate middle iMid = math.floor((iStart + iEnd) / 2) -- compare if fcomp(value , t[iMid]) then iEnd = iMid - 1 iState = 0 else iStart = iMid + 1 iState = 1 end end local pos = iMid+iState table.insert(t, pos, value) return pos end --// table.bfind(table, value [, compvalue] [, reverse]) -- Lua 5.x add-on for the table library. -- Binary searches the table for value. -- If the value is found it returns the index and the value of -- the table where it was found. -- fcompval, if given, is a function that takes one value and -- returns a second value2 to be compared with the input value, -- e.g. compvalue = function(value) return value[1] end -- If reverse is given then the search assumes that the table -- is sorted with the biggest value on position 1. function table.bfind(t, value, fcompval, reverse) -- Initialize functions fcompval = fcompval or function(value) return value end fcomp = function(a, b) return a < b end if reverse then fcomp = function(a, b) return a > b end end -- Initialize Numbers local iStart, iEnd, iMid = 1, table.getn(t), 1 -- Binary Search while (iStart <= iEnd) do -- calculate middle iMid = math.floor((iStart + iEnd) / 2) -- get compare value local value2 = fcompval(t[iMid]) if value == value2 then return iMid, t[iMid] end if fcomp(value , value2) then iEnd = iMid - 1 else iStart = iMid + 1 end end end -- Iterate in ordered form -- returns 3 values i , index, value -- ( i = numerical index, index = tableindex, value = t[index] ) function orderedPairs(t) return orderedNext, t end function orderedNext(t, i) i = i or 0 i = i + 1 local indexvalue = getmetatable(t)._tsorted[i] if indexvalue then return i, indexvalue[1], indexvalue[2] end end
Tests:
t2 = table.ordered() if t2 then print( t2 ) end t2["A"] = 1 t2.B = 2 t2.C = 3 t2.D = 4 t2.E = 5 t2.F = 6 t2.G = 7 t2.H = 8 print("Ordered Iteration") for i,index,v in orderedPairs(t2) do print( index, v ) end
Results:
table: 07864640 Ordered Iteration A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8
Tests:
-- same example but reveres ordered t2= table.ordered( "reverse" ) t2["A"] = 1 t2.B = 2 t2.C = 3 t2.D = 4 t2.E = 5 t2.F = 6 t2.G = 7 t2.H = 8 print("Ordered Iteration of Reverse") for i,index,v in orderedPairs(t2) do print(index, v) end
Results:
Ordered Iteration of Reverse H 8 G 7 F 6 E 5 D 4 C 3 B 2 A 1
Tests:
print("Set one Letter nil") t2.E = nil print("Ordered Iteration of Reverse") for i,index,v in orderedPairs(t2) do print(index, v) end
Results:
Set one Letter nil Ordered Iteration of Reverse H 8 G 7 F 6 D 4 C 3 B 2 A 1
Tests:
print("Update one value") t2.F = "updated" print("Ordered Iteration of Reverse") for i,index,v in orderedPairs(t2) do print(index, v) end
Results:
Update one value Ordered Iteration of Reverse H 8 G 7 F updated D 4 C 3 B 2 A 1
Tests:
print("Add with a no confirm key") -- will simply be not added t2[6] = "add" print( "Add a key" ) t2.a = "new key1" t2.Z = "new key 2" t2.d = "??" print( "Ordered Iteration of Reverse" ) for i,index,v in orderedPairs( t2 ) do print( index, v ) end -- get a key print( t2.Z )
Results:
Add with a no confirm key Add a key Ordered Iteration of Reverse d ?? a new key1 Z new key 2 H 8 G 7 F updated D 4 C 3 B 2 A 1 new key 2
Tests:
-- Speed testing -- build a n big inassociative table -- search it n2 times by hash clac used tim n1 = 100000 n2 = 100000 t = {} i0 = os.clock() for i = 1, n1 do t[tostring(i)] = i end local i1 = os.clock() for i = 1, n2 do local v = i, t[tostring(i)] --print(v , i) end print("Normal test of inassociative table") print("Time to add "..n2.." Items: "..(i1-i0)) print(os.clock()) print(i1) print(os.clock() - i1) print("Time to search "..n1.." Items: "..(os.clock() - i1)) -- do one sort i0 = os.clock() local ts = {} table.foreach(t, function(i,v) table.insert(ts, {i,i}) end) table.sort(ts, function(a, b) return b[1] < a[1] end ) print("Normalsort time: "..(os.clock()-i0)) -- Speed test with a ordered table t = table.ordered() i0 = os.clock() for i = 1, n1 do t[tostring(i)] = i end local i1 = os.clock() for i = 1, n2 do local v = i, t[tostring(i)] --print(v , i) end print("Normal test of Ordered inassociative table") print("Time to add "..n2.." Items: "..(i1-i0)) print(os.clock()) print(i1) print("Time to search "..n1.." Items: "..(os.clock() - i1))
Results:
Normal test of inassociative table Time to add 100000 Items: 1.6409999999996 19960.765 19960.125 0.63999999999942 Time to search 100000 Items: 0.63999999999942 Normalsort time: 2.8280000000013 Normal test of Ordered inassociative table Time to add 100000 Items: 52.281999999999 20021.593 20015.875 Time to search 100000 Items: 5.7180000000008
As shown, the code become very slow when adding new keys compared to the normal adding by index, around 100 times, and we are around 10 times slower when searching for a index, that is acceptable I think. Then I created a sorted array of the index from the normal table, and the result was again faster than the number of searches on the binary table. That brings me back to SortedIteration, which is the best way of doing what we want unless you need to run through your table more often than you check or add a value. Only in that specific case would this method be faster. Well, at least good to know :)
