c++ - 对小型未排序数组进行最便宜的等式搜索

Question

就执行时间而言，在 C++ 中搜索大约 4 到 16 个元素的小数组以查找与您正在搜索的元素相等的元素的最有效方法是什么？在这种情况下，被搜索的元素是一个指针，所以它比较小。

（我的目的是防止点云中的点与已经与它们共享边缘的点创建边缘。边缘数组对于每个点来说都很小，但可能有大量的点。另外，我只是好奇也！）

Answer 1

您最好的选择是使用各种机制来分析您的特定应用程序，并查看哪个性能最佳。

我怀疑鉴于它未排序，直线搜索将最适合您。如果您能够对数组进行一次预排序并且它很少更新或从不更新，您可以预排序然后使用二进制搜索。

Answer 2

尝试线性搜索；尝试从一个或多个二进制斩波阶段开始。前者平均涉及更多比较；后者对于缓存未命中和分支错误预测具有更大的范围，并且需要对数组进行预排序。

只有通过测量你才能知道哪个更快，然后只有在你测量的平台上。

Answer 3

如果您必须多次执行此搜索，并且数组不会经常/根本不更改，请对其进行排序，然后使用二进制搜索。