0

我正在为 Lua 程序设计 UI，其中一个元素要求用户从主表中选择现有值或在该表中创建新值。

我通常会使用带有 EDITBOX = "YES" 的 IUP 列表。

但是，用户可以选择的项目数量可能达到数百甚至数千，并且在 iup 中填充列表（以及从中进行选择）时的性能慢得令人无法接受。我无法控制表格中的项目数量。

我目前的想法是创建一个带有编辑框的列表，但没有任何值。当用户在编辑框中输入内容时（可能是 2-3 个字符之后），列表将填充以输入字符开头的表格项子集。然后用户可以从列表中选择一个项目或继续键入以缩小选项或创建一个新项目。

为此，我需要能够创建一个新表，其中包含以输入字符开头的主表中的项目。

一种选择是使用 Penlight 的“startswith”函数遍历主表以创建新表：

require "pl.init"
local subtable = {} --empty result table
local startstring = "xyz" -- will actually be set by the iup control
for _, v in ipairs (mastertable) do 
    if stringx.startswith(v, startstring) then
        table.insert(subtable,v)
    end
end

但是，如果主表很大，我担心这样做的性能。有没有更有效的编码方式，或者我可以实现 UI 的不同方式？

4

1 回答 1

1

您可以采取多种方法来提高前缀搜索的 big-O 性能，但会增加代码复杂性；也就是说，鉴于您的数据集的大小（数千个项目）和预期用途（由用户交互触发，而不是例如需要运行每一帧的游戏逻辑），我认为对选项进行简单的线性搜索几乎肯定会进行足够快。

为了测试这个理论，我对以下代码进行了计时：

local dict = {}
for word in io.lines('/usr/share/dict/words') do
  table.insert(dict, word)
end
local matched = {}
local search = "^" .. (...)
for _,word in ipairs(dict) do
  if word:match(search) then
    table.insert(matched, word)
  end
end
print('Found '..#matched..' words.')

我使用/usr/bin/time -v并尝试了 lua 5.2 和 luaJIT。

请注意，与您的代码相比，这相当悲观：

  • 没有尝试本地化重复调用的库函数，或者使用#而不是table.insert
  • 时间不仅包括搜索，还包括首先将字典加载到内存中的成本
  • string.match几乎可以肯定比stringx.startswith
  • 字典包含约 10 万个条目，而不是您在应用程序中期望的“成百上千”

即使有所有这些警告，在 lua5.2 中花费 50-100 毫秒，在 luaJIT 中花费 30-50 毫秒，超过 50 次运行。

如果我os.clock()用来计时实际搜索，它在 lua5.2 中始终花费大约 10 毫秒，在 luajit 中花费 3-4 毫秒。

现在，这是在相当快的笔记本电脑（Core i7）上运行的，但在比您预期处理的数据集大 10-100 倍的数据集上运行的非优化代码；鉴于此，我怀疑仅循环调用条目的天真方法startswith对于您的目的来说会非常快，并且会导致代码更加简单且易于调试。

于 2021-09-29T14:23:07.477 回答