在四维阵列搜索元素具有特殊性能

Question

我有一个四维阵列，其中的值是单调的。如何有效地搜索价值。

Answer 1

如果N不超过10000，那么不明白为什么你不能使用unordered_set。然后做一个单一的查找。如果每个维度都有重复值，那么您需要以某种方式跟踪该维度。但是，我不知道任何为C实现unordered_set的代码。因此，您可能必须使用C++。

如果您不能使用unordered_set，则由于数据是按排序顺序为每个维度，你也可以使用每个维度的二进制搜索。这意味着每个维度平均查找不超过15个值 - 假设每个维度中的元素总数小于16K。 15个查找* 4个维度= 60个查找。这太慢了吗？其他

一个改进可能是创建从4个维度一个大排序和独特的阵列和搜索一个代替。这将产生大约17次查找（假设< = 64K元素）.vs。 60，这是3.5倍以上的速度。但是，这也取决于值的添加或删除的频率以确定它是否真的会更快 - 因为您必须在单个表中添加和删除它们。另外，不要忘记使用表格来跟踪重复值 - 如果适用的话。

如果值是比较小的整数 - 说十亿或更少，那么你可能能够使用一个位映象方案。位图方案比每个维度使用unordered_set要快。一个字节数组可以用作位图。在位图中设置的值意味着该值存在。例如，如果该值为零，则将设置位零。如果该值为3，则会设置位2。如果该值为5，则会设置位4等。因此，需要使用100MB来映射所有值为10亿（2^30）的值。如果每个维度中都存在重复值，那么您需要跟踪该维度，以便从维度中删除值时 - 除非它不存在于其他维度中，否则不会从位图中删除。如果您的值是浮点数，那么如果有效数字的总数为< = 9，则可以将它们翻译为整数。如果这些值是字符串或结构体，那么如果可以找出一种方法，则位图方案可能仍然有效将其翻译为唯一的整数。