如何有效地提取大型 master table 中以指定字符串开头的所有值

Question

我正在为 Lua 程序设计 UI，其中一个元素要求用户 select 来自主 table 的现有值或在 table.

中创建一个新值

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

但是，用户可以 select 的项目数可能运行成数百甚至数千，并且在 iup 中填充列表时的性能（以及 select ing from it) 慢得令人无法接受。我无法控制 table.

中的项目数

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

为此，我需要能够使用主 table 中以输入的字符开头的项目创建一个新的 table。

一个选择是使用 Penlight 'startswith' 函数遍历主 table 以创建新的 table:

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

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

Answer 1

您可以采用多种方法来提高前缀搜索的大 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 运行s。

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

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

如何有效地提取大型 master table 中以指定字符串开头的所有值

How to efficiently extract all values in a large master table that start with a specified string

lua

iup