如何高效地从一个大主表中提取以指定字符串开头的所有值

2021-9-27 15:27:30
收藏：0
阅读：152
评论：1

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

通常我会使用IUP列表和EDITBOX = "YES"。

但是，用户可以选择的项目数量可能会达到数百甚至数千个，当在iup中填充列表（以及从列表中选择）时，性能太慢了。我无法控制表中的项目数量。

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

要使此工作，我需要能够创建一个新表，并将其中的项从主表中以所输入的字符开头的项插入该表中。

一种选择是使用Penlight的 'startswith' 函数迭代主表以创建新表：

require "pl.init"
local subtable = {} --空结果表
local startstring = "xyz" -- 实际上将由iup控件设置
for _, v in ipairs (mastertable) do
    if stringx.startswith(v, startstring) then
        table.insert(subtable,v)
    end
end

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

原文链接 https://stackoverflow.com/questions/69349159

点赞
stackoverflow用户2755919
stackoverflow用户2755919

有多种方法可以优化前缀搜索的大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 慢
  • 字典包含约100k个条目，而不是您的应用程序中期望的“数百到数千个”

即使有了所有这些警告，它在 lua5.2 中的成本为 50-100 毫秒，在 luaJIT 中为 30-50 毫秒，在50次运行中。

如果使用 os.clock() 计时实际搜索，它在 lua5.2 中的成本一直约为10ms，在 luajit 中为 3-4。

现在，这是在一台相当快的笔记本电脑上（Core i7）进行的，但也是在处理比您期望的大10-100倍的数据集上运行的非优化代码；鉴于这一点，我怀疑只是循环遍历调用 startswith 的朴素方法对于您的目的来说已经足够快，而且结果是更简单，更易于调试的代码。

2021-09-29 14:23:07

作者:

stackoverflow用户1943174

stackoverflow用户1943174
推荐文章