Lua - 如何按值排序表

2015-9-12 8:40:44
收藏：0
阅读：112
评论：2

我正在寻找一种按其值链（values chain）对 Lua 表进行排序的方法。例如，给出该表：

local vals = {
{ id = "checkpoint4" },
{ id = "checkpoint1", nextid = "checkpoint2" },
{ id = "checkpoint3", nextid = "checkpoint4" },
{ id = "checkpoint2", nextid = "checkpoint3" },
}

排序后，应该变成：

local vals = {
{ id = "checkpoint1", nextid = "checkpoint2" },
{ id = "checkpoint2", nextid = "checkpoint3" },
{ id = "checkpoint3", nextid = "checkpoint4" },
{ id = "checkpoint4" },
}

它们的名称并非完全相同，可能会有所变化。我想要比较“checkpoint”后面的数字，但结果发现我必须使用这种动态的表格（已按照我想要的方式排序）：

local vals = {
{ id = "checkpoint1", nextid = "cp" },
{ id = "cp", nextid = "chp" },
{ id = "chp", nextid = "mynextcheckpoint" },
{ id = "mynextcheckpoint"},
}

谢谢。

点赞
用户142162
用户142162

你所描述的被称为topological sorting。然而，因为这是一个受限制的情况，我们不必实现一个完整的topological sorting算法：

function sort_list(tbl)
  local preceding = {}
  local ending
  local sorted = {}
  for i, e in ipairs(tbl) do
    if e.nextid == nil then
      ending = e
    else
      preceding[e.nextid] = i
    end
  end
  if ending == nil then
    return nil, "no ending"
  end
  local j = #tbl
  while ending ~= nil do
    sorted[j] = ending
    ending = tbl[preceding[ending.id]]
    j = j - 1
  end
  if sorted[1] == nil then
    return nil, "incomplete list"
  end
  return sorted
end

使用方法：

local sorted = sort_list(vals)
2015-04-18 16:56:59
用户1847592
用户1847592 
local id2val, tailsizes = {}, {}
-- 创建 id2val 和 tailsizes 空表
for _, val in ipairs(vals) do id2val[val.id] = val end

local function tailsize(val)  -- memoized calculation of tails sizes
   -- 根据表中是否存在 val 键来判断是否进行后面的操作
   if not tailsizes[val] then
      tailsizes[val] = 0                         -- cycle-proof
      -- 判断表中是否存在 nextid 和 id2val，如果判断未通过，则不进行计算
      if val.nextid and id2val[val.nextid] then  -- dangling nextid proof
         tailsizes[val] = tailsize(id2val[val.nextid]) + 1
      end
   end
   return tailsizes[val]
end

-- 根据尾部长度进行排序
table.sort(vals, function(a,b) return tailsize(a) > tailsize(b) end)
2015-04-22 11:26:58

作者:

用户3519618

用户3519618
推荐文章