algorithm - 从 2^24 值到 2^7 索引的高效映射

Question

我有一个数据结构，其中存储一个 24 位宽的值。我有很多这些对象。

为了最大限度地降低存储成本，我从 2^24 个可能值中计算出 2^7 个最重要的值，并将它们存储在静态数组中。因此，我只需在我的数据结构中为该数组保存一个 7 位索引。

问题是:我得到了这些 24 位值，我必须即时将它们转换为我的 7 位索引(无法进行预处理)。计算基本上是搜索 2^7 个值中最适合的一个。显然，对于大量对象，这需要一些时间。

一个明显的解决方案是创建一个长度为 2^24 的简单字节映射数组。但这需要 16 MB 的 RAM。太多了。

对 16 MB 数组的一个观察:平均有 31 个连续值是相同的。不幸的是，还有许多不同的连续值。

---

您将如何实现从 24 位值到 7 位索引的转换，从而尽可能节省 CPU 和内存？

Answer 1

如果不知道“最适合”的定义是什么，很难说。也许是 kd-tree将允许根据某种指标或其他指标的接近度进行合适的搜索，以便您快速排除大多数候选人，并且只需要实际测试 2^7 中的一些来查看哪个是最好的？

这听起来类似于图像处理器在缩小到较小的调色板时遇到的问题。我实际上并不知道为此使用了哪些算法/结构，但我确信它们是可查找的，并且可能会有所帮助。