优化lua表备份

2014-10-19 21:3:6
收藏：0
阅读：138
评论：1

我正在尝试创建一个快速的数独求解器，在其中一步中我需要保存谜题的状态。我开始使用各种深拷贝函数来做到这一点，但发现它相当缓慢。最后我想出了这两个函数，但是luatrace显示这两个函数仍然占用了相当大的时间。

有什么方法可以进行优化，还是该用C语言来编写它？

local function backupCells(cells)
    local serial = {{}, {}}
    for i = 1, #cells do
        serial[1][i] = {unpack(cells[i].domain)}
        serial[2][i] = cells[i].value
    end
    return serial
end

local function restoreCells(cells, serial)
    for i=1, #cells do
        cells[i].domain = serial[1][i]
        cells[i].value = serial[2][i]
    end
end

更新：（请求更多信息！）

因此，cells中的每个单元格代表数独网格上的一个正方形。 value属性在确定单元格的值后设置（否则为nil）。domain是所有可能值的表格。在对backupCells和restoreCells的调用之间完成了前向检查，并且单元格的值/域发生了相当大的变化-serial没有产生任何此类变化。

一般来说，恢复是一个“撤消”，以便求解器可以猜测另一个值并从那里进行前向检查。

点赞
用户3204551
用户3204551

我的建议：

简化你的单元格布局。

每个单元格都是一个包含所有可能值的表格，因此：

  • 如果‘not t[1]’，显然我们犯了一个错误。
  • 否则，如果‘not t[2]’，‘t[1]’是该单元格的值。
  • 否则，‘t’包含多个可能性。

因此，您可以复制以下棋盘：

local function cloneBoard(cells)
    local r = {}
    for i = 1, #cells do
        -- 选项1
        local t, cell = {}, cells[i]
        r[i] = t
        for j = 1, #cell, 1 do
            t[j] = cell[j]
        end
        -- 选项2
        r[i] = {unpack(cells[i])}
        -- 测量哪个选项对您来说更快
    end
    return r
end

接下来，丢弃旧棋盘，只使用（克隆的）保存棋盘。

2014-10-19 22:31:08

作者:

用户4159463

用户4159463
推荐文章