0

我有一个元素数组。该数组按元素的 ID 排序，但 ID 是非连续的，例如 ID 编号之间存在间隙。

我今天使用二进制搜索来查找特定的 ID。

ID 为 3 个字节，提供了大约 1600 万种可能性。给定数组中的 ID 数量要少得多，可能是 10 000。

这是一个嵌入式/plc 平台，这意味着我不能有一个 16MB 的查找表，这会占用太多内存。我看过这样的位集，但我不确定这是否是正确的方法，或者如何计算数组偏移量。

我意识到这可能是一个艰难的问题，因为我想做旧的“内存速度”权衡，但我的内存非常少，可能只有 2MB 或更少的内存可用。但是硬件是固定的。

编辑：数组的元素对于给定的应用程序是固定的，没有插入或删除数组元素。

如何构建/预计算查找表或类似的表以加快查找 ID？

谢谢

4

2 回答 2

2

我假设二进制搜索太慢了。由于表是固定的，在运行时不会有增删改查，可以看一下“完美哈希”的解决方案。Wiki 有一篇非常好的文章来解释这个https://en.wikipedia.org/wiki/Perfect_hash_function

基本上，离线你需要通过一个完美的哈希生成器运行表，然后在运行时你通过离线生成的公式运行 ID 以获取表中项目的索引。

于 2018-12-14T15:17:38.290 回答
0

您只需要以 ID 开头的条目的排序表。该代码可以为您创建索引，并将索引与二进制搜索一起使用进行查找。索引将是 40kb。您可能可以节省那么多。如果 ID 真的只有 3 字节，它可以变成 30kb，但除非你真的短 10kb，否则这将是一个不必要的复杂化。

哈希可以放弃索引，但节省空间值得吗？如果条目比它们的 ID 大得多，那么就不会占用那么多空位来用完节省的空间。

VAR_GLOBAL
  entries : ARRAY[1..entryCount] OF ST_Entry := ...; // you need to preinitialize this array here
  index: ARRAY[1..entryCount] OF DINT;
  _dummy : BOOL := BuildIndex(ADR(index), ADR(entries), entryCount);
END_VAR
VAR_GLOBAL CONSTANT
  entryCount : DINT := 10000;
END_VAR

// Called once during PLC initialization only. Returns FALSE always.
FUNCTION BuildIndex : BOOL
VAR_INPUT
  index: POINTER TO DINT;
  entries : POINTER TO ST_ENTRY;
  count : DINT;
END_VAR
WHILE count > 0 DO
  index[count] := entries[count].Id;
  count := count - 1;
END_WHILE
END_FUNCTION

使用此设置，通过二进制搜索进行索引查找很容易：

FUNCTION LookupEntry : REFERENCE TO ST_Entry
VAR_INPUT
  id : DINT;
END_VAR
VAR
  begin : DINT := 1;
  mid : DINT;
  end : DINT := GVL.entryCount;
  midId : DINT;
END_VAR
WHILE TRUE DO
  mid := (begin + end) / 2;
  midId := index[mid];
  IF midId = id THEN
    LookupEntry REF= entries[mid];
    EXIT;
  END_IF
  IF mid=begin AND mid=end THEN
    EXIT;
  END_IF
  IF midId < id THEN
    begin := mid;
  ELSE
    end := mid;
  END_IF
END_WHILE;
// may return an invalid reference, use of reference will throw
END_FUNCTION
于 2019-10-23T07:17:29.260 回答