有序关联表
lua-users home
wiki

以下代码提供了一种简单高效的方法来维护一个表中键的排序索引，然后使用该排序索引遍历表。我们首先考察删除被禁止时的简单情况。

方案一

--// CHILL CODE � //--
-- table.ordered( [comp] ) 
--
-- Lua 5.x add-on for the table library.
-- Table using sorted index.  Uses binary table for fast Lookup.
-- https://lua-users.lua.ac.cn/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

测试 

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 )

结果 

Normal iteration ordered table
A       1
C       3
B       2
E       5
D       4
G       7
F       6
H       8

测试 

print("Ordered Iteration")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

结果 

Ordered Iteration
A       1
B       2
C       3
D       4
E       5
F       6
G       7
H       8

测试 

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

结果 

Ordered Iteration of Reverse
H       8
G       7
F       6
E       5
D       4
C       3
B       2
A       1

方案二

现在由于无法删除任何条目，另一个选择是完全切换到二进制表，并通过t[index]访问它，同时在元表中进行排序操作。 

--// 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.
-- https://lua-users.lua.ac.cn/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

测试 

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

结果 

table: 07864640
Ordered Iteration
A       1
B       2
C       3
D       4
E       5
F       6
G       7
H       8

测试 

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

结果 

Ordered Iteration of Reverse
H       8
G       7
F       6
E       5
D       4
C       3
B       2
A       1

测试 

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

结果 

Set one Letter nil
Ordered Iteration of Reverse
H       8
G       7
F       6
D       4
C       3
B       2
A       1

测试 

print("Update one value")
t2.F = "updated"
print("Ordered Iteration of Reverse")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

结果 

Update one value
Ordered Iteration of Reverse
H       8
G       7
F       updated
D       4
C       3
B       2
A       1

测试 

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 )

结果 

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

测试 

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

结果 

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

如所示，与通过索引添加相比，添加新键时代码变得非常慢，大约慢了 100 倍，而我们在搜索索引时大约慢了 10 倍，我认为这是可以接受的。然后我创建了一个从普通表中索引的排序数组，结果再次比二进制表上的搜索次数快。这让我回到了SortedIteration，这是我们想要做的最好的方法，除非你比检查或添加值更频繁地遍历你的表。只有在这种特定情况下，这种方法才会更快。好吧，至少知道这一点很好:)

最近更改 · 偏好设置
编辑 · 历史记录
最后编辑于 2007 年 2 月 22 日凌晨 4:47 GMT (差异)