2

我有一个由 30 个实数组成的排序数组。数字分布均匀。我想在这个数组中搜索一个数字。目前，我正在使用线性搜索算法。为了提高我的应用程序的性能，我需要使用更好的搜索算法。我应该使用哪种搜索算法或者我应该在什么基础上选择“最佳”算法？

提前致谢！

4

6 回答 6

2

您没有指定语言，对于仅包含 30 个元素的数组，最快的方法可能会因语言而异。

但是，如果您编写一个测试 C# 程序，您会发现对于 RELEASE 构建，使用BinarySearch()会更快。C++ 和其他语言可能会给出不同的结果。

以下测试代码使用线性和二进制搜索在 30 个整数的数组中搜索不存在的元素。因为该元素不存在，所以两次搜索都将采用最大数量的操作。成功搜索的结果会有所不同。

结果是这样的：

IndexOf()      took 00:00:00.5463193
BinarySearch() took 00:00:00.3035060

表明二分搜索要快一些，至少在目标元素不存在时对于 C# 来说是这样。

int[] array = new int[30];
int count = 10000000;

for (int trial = 0; trial < 4; ++trial)
{
    var sw = Stopwatch.StartNew();

    for (int i = 0; i < count; ++i)
        Array.IndexOf(array, 1);

    Console.WriteLine("IndexOf() took " + sw.Elapsed);

    sw.Restart();

    for (int i = 0; i < count; ++i)
        Array.BinarySearch(array, 1);

    Console.WriteLine("BinarySearch() took " + sw.Elapsed);
}
于 2013-06-14T10:57:50.913 回答
2

你需要做一些时间来确定什么是最快的。这可能因平台、编程语言、CPU 架构、您拥有的数据等而异。还值得对整个程序执行计时，使用分析器或插入您自己的计时调用，只要您认为合适。

为了测试 C++ 中哪种技术最快，我运行了一个简单的测试程序来比较

  1. 对未排序数组 ( std::find) 进行线性搜索，O(n)，针对
  2. 对已排序数据进行二进制切割（使用std::lower_bound），O(log n)，针对
  3. 对排序数据进行线性搜索，O(n)。

一旦找到匹配项，对已排序数据的线性搜索就会停止，因此如果您要查找的元素在数组中，则其预期成本是对未排序数组进行线性搜索的一半。在我的测试程序中，我寻找的一半案例不在数组中，因此您预计其成本约为对未排序数据进行线性搜索的成本的 75%。当然，如果您必须经常对数组进行排序，则会大大增加运行时间！

在下图中，

  • 红色圆圈是对未排序数组进行二分查找与线性查找的成本之比，以及
  • 黑色圆圈是对已排序数据进行线性搜索的成本与未排序数据的比率。

在此处输入图像描述

至少在这种情况下，您可以看到，在 n=30 的技术之间没有太多选择，除非分析表明您有真正的性能瓶颈，否则最好遵循保持简单的规则，并且，如果您不必对数据进行排序，只需对未排序的数据进行线性搜索，这样您就没有排序数据的额外约束（或者如果排序是合理的约束，则对排序数据进行线性搜索）。

于 2013-06-14T12:55:16.433 回答
1

如果您的数字已排序，您应该使用二进制搜索。与线性搜索（O(n)）相比，它会O(log n)及时搜索

于 2013-06-14T10:32:58.947 回答
1

首先，您是否完全确定搜索确实代表了瓶颈？在编写代码之前优化您的日程安排，确保您在真正值得的地方进行优化。您很容易会惊讶地发现一些更简单的东西需要更长的时间。我建议进行分析以确保。如果您使用 C++，VerySleepy通常会为我完成这项工作。

现在，如果您注意到搜索确实代表了瓶颈，您可以切换到二进制搜索，如评论中所建议的（在 C++ 中，std::binary_search来自<algorithm>）。您也可以为hast table切换容器，但这取决于您的需求和情况。

配置文件，基准测试，选择最适合您的情况。

于 2013-06-14T10:33:21.937 回答
1

如果是 30 种原始类型的数组，线性搜索无疑是最佳选择。

于 2013-06-14T10:36:18.260 回答
1
  1. 如果您不知道输入数字的范围，可以使用二进制搜索。或者如果数组确实是排序的。
  2. 如果你知道你的号码范围。那么哈希一定是一个更好的选择。

对于 Hash ：如果您使用 C++ 编程，则可以使用 C++ 容器“Set”。否则，您可以简单地使用数组来完成您必须标记存在的元素的工作。为了搜索它，只需检查该元素的标志是设置还是未设置！

于 2013-06-14T10:41:08.323 回答