在四維陣列搜索元素具有特殊性能

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，則可以將它們翻譯爲整數。如果這些值是字符串或結構體，那麼如果可以找出一種方法，則位圖方案可能仍然有效將其翻譯爲唯一的整數。