Lua

Question

我正在寻找一种按价值链对 Lua table 进行排序的方法。比如说，table:

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"},
}

谢谢。

Answer 1

您描述的是 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)

Answer 2

local id2val, tailsizes = {}, {}
for _, val in ipairs(vals) do id2val[val.id] = val end

local function tailsize(val)  -- memoized calculation of tails sizes
   if not tailsizes[val] then
      tailsizes[val] = 0                         -- cycle-proof
      if val.nextid and id2val[val.nextid] then  -- dangling nextid proof
         tailsizes[val] = tailsize(id2val[val.nextid]) + 1
      end
   end
   return tailsizes[val]
end

-- sorting according to tails sizes
table.sort(vals, function(a,b) return tailsize(a) > tailsize(b) end)

Lua - 如何按价值链对 table 进行排序

Lua - how to sort a table by the value chain

sorting

chain

lua-table