优化小型 MCU 上稀疏数组中的元素查找

Question

我正在开发一个应用程序，涉及管理分布在大小为 M 的数组中的 N 个 Element 实例，其中 N << M (N is much smaller than M). These elements are accessible via their indices, and their distribution within the array is known at build time but follows no specific pattern.

主要目标：我寻求一种算法，允许通过索引有效（按时间）检索元素，同时还要注意空间限制。理想情况下，我想避免分配 O(M) 空间，这虽然会导致 O(1) 时间复杂度，但对于我的应用程序来说是不可行的。

上下文：此任务是为运行在 50 MHz 且没有浮点单元 (FPU) 的 16 位微控制器单元 (MCU) 开发 CanOpen 从属堆栈的一部分。传统的哈希表看似是一个显而易见的解决方案，但由于 MCU 的限制而不适用。

当前方法：我正在考虑使用简化的 Murmur 哈希函数的开放寻址哈希表。这是初步功能：

const int A = 16;
const int B = 0x45d9f3b;
const int C = B;

unsigned int hash(unsigned int x) {
    x = ((x >> A) ^ x) * B;
    x = ((x >> A) ^ x) * C;
    x = (x >> A) ^ x;
    return x;
}

我计划尝试使用不同的 A、B 和 C 值，以最大限度地减少访问时间并减少冲突。最终使用自动化脚本运行构建时间来找到最佳的 A、B、C 常量。

问题：考虑到限制，这种方法是否可行，或者是否有更有效的算法或方法更适合这种场景？我愿意接受其他建议，包括使用二分搜索的可能性。

附加信息

此设置是运行实时应用程序的小型 MCU 上 CANopen 从站堆栈的一部分。虽然 CanOpen 使用 16 位对象字典，但我的应用程序仅需要 100-200 个对象。关键是尽量减少每个对象的访问时间。

我的处理能力有限，MCU 上没有 FPU。空间效率与时间效率同样重要。

Answer 1

如果没有有关数组结构的更多信息，这是不可能的。

如果您有

100

对象，则有

100^m

可能的数组需要编码。如果无法发送那么多信号，就无法对所有可能的数组进行编码。这需要

m * log_2(100)

位。这是

O(m)

数据。

通过有关数组的附加数据，可以减少可能要编码的数组的数量，从而减少数据存储。但试图隐藏哈希函数背后的复杂性并不能让你摆脱鸽子洞原理——如果不使用足够的数据来创建

x

不同的可能信号，你就无法区分

x

不同的数组。这至少需要

log_2(x)

位。

如果你能负担得起

m

字节的数组，我会这样做。否则，您要么会发现有关如何生成数组的有用信息，要么必须将目标更改为可行的目标。

Answer 2

在考虑到限制的情况下，这种方法是否可行，或者是否有更有效的算法或方法更适合这种场景？

您描述的方法对于查找具有良好“平均”查找时间的哈希函数是可行的。 但是我强烈建议使用您拥有的实际内存大小（但在问题中未指定）对碰撞概率进行一些简单的餐巾纸数学计算（为了简单起见，您可以假设哈希函数是完美分布的）以获得关于

最坏情况

的想法。 您提到您有实时限制，所以我有一种感觉，最坏情况时间（源自碰撞链的最大长度）可能无法令您满意。您可以让构建时脚本循环，直到找到解决方案，但是（取决于您的限制）可能并不总是有一个解决方案，因此您的构建在极少数情况下可能会失败。

另一种方法是使用

完美的哈希函数

，它可以为您提供保证最坏的情况，因为它没有冲突。