3

这是关于 gist 的课程 https://gist.github.com/2605302

我已经用不同的文件对其进行了多次测试，即使对二进制搜索进行的比较较少，所花费的时间也总是更多。怎么了？

public static int linerSearch ( String array [], String word, long resultsArray [])
{
    int comparisons = 0;
    int pos = -1;
    //i have started the timer where the search actualy starts
    long start = System.nanoTime ();
    for (int i = 0; i < array.length; i++){
        comparisons = comparisons + 1;
        if (array [i].equals (word)){
            pos = i;
            break;
        }
    }
    long stop = System.nanoTime ();
    long total = stop - start;
    resultsArray [0] = total;
    resultsArray [1] = (long) (long) array.length;
    resultsArray [2]= (long) (long) comparisons;
    return pos;
}

这是下一个 binarySearch 类

public  static int binarySearch (String [] array, String word, resultsArray []) {
    int start = 0;
    int end = array.length - 1;;
    int midPt;
    int pos = -1;
    int comparisons2 = 0;
    long start2 = System.nanoTime ();
    Arrays.sort (array);
    while (start <= end) {
        midPt = (start + end) / 2;
        comparisons2 = comparisons2 + 1;
        if (array [midPt].equalsIgnoreCase (word)) {
            pos = midPt;
            break;
        }
        else if (array [midPt].compareToIgnoreCase (word) < 0) {
            start = midPt + 1;
            comparisons2 = comparisons2 + 1;
            //camparisons2 addition was added inside this elseif and other elseif as a work around for not breaking the elseif statement tree, if it has made it two the last elseif then two camparisons after the first one will have been done
        } else if (array [midPt].compareToIgnoreCase (word) > 0)  {
            comparisons2 = comparisons2 + 2;
            end = midPt - 1;
        }
    }
    long stop2 = System.nanoTime ();
    long total2 = stop2 - start2;
    resultsArray [0] = total2;
    resultsArray [1] = (long) (long) array.length;
    resultsArray [2]= (long) (long) comparisons2;
    return pos;
}

编辑：我还应该补充一点，我在没有那行代码的情况下在一个已经排序的数组上尝试过它，但它不应该的时间仍然更长

4

5 回答 5

2

您的基准测试的问题是 Arrays.sort(array) 花费的时间最多，并且您不计算它的比较。线性搜索需要 N 次比较。当您对数组进行排序时，您会花费超过 N 次比较。

要查看二进制搜索更快，您应该进行这样的测试：

1) 使用线性搜索搜索不同的元素 1000 次

2) 对数组进行一次排序并使用二分法搜索不同的元素 1000 次

于 2012-05-05T20:36:44.477 回答
1

您的基准测试存在缺陷，原因有很多：

  • 我们不知道文件的内容。如果搜索到的词在开头，那么线性搜索会比二分搜索快
  • 线性搜索与equals比较，而二分查找与equalsIgnoreCase比较
  • 您执行代码的次数不足以让 JIT 编译代码

我还没有验证你的二分搜索算法是否正确，但你为什么不使用与 JDK 捆绑的算法（在 java.util.Arrays 类中）。

无论如何，你不必测量任何东西。平均而言，二分搜索比线性搜索快。无需再次证明这一点。

于 2012-05-05T20:35:39.097 回答
1

好的，我已经为你一劳永逸地解决了这个问题。首先，这是我使用的二进制搜索方法：

public static int binarySearch(String[] array, String word, long resultsArray[]) {
    int start = 0;
    int end = array.length - 1;
    int midPt;
    int pos = -1;
    int comparisons2 = 0;

    //Arrays.sort(array);

    long start2 = System.nanoTime();
    while (start <= end) {
        midPt = (start + end) / 2;
        int comparisonResult = array[midPt].compareToIgnoreCase(word);
        comparisons2++;
        if (comparisonResult == 0) {
            pos = midPt;
            break;
        } else if (comparisonResult < 0) {
            start = midPt + 1;
        } else { // comparisonResult > 0
            end = midPt - 1;
        }
    }
    long stop2 = System.nanoTime();
    long total2 = stop2 - start2;

    resultsArray[0] = total2;
    resultsArray[1] = (long) array.length;
    resultsArray[2] = (long) comparisons2;
    return pos;
}

您会注意到我通过保存比较结果并使用它来减少比较次数。

接下来，我下载了这个 235882 个单词的列表。它已经排序，忽略大小写。然后，我构建了一个测试方法，将该文件的内容加载到一个数组中，然后使用这两种搜索方法来查找该列表中的每个单词。然后，它分别对每种方法的比较次数和次数进行平均。

我发现你在选择使用哪种比较方法时必须小心：如果你Arrays.sort(...)是一个列表并且你compareToIgnoreCase在二分搜索中使用它，它会失败！通过失败我的意思是它无法从给定的列表中找到这个词，即使这个词确实存在在那里。这是因为Arrays.sort(...)它是一个区分大小写的字符串排序器。如果你使用它，你必须使用compareTo(...)它的方法。

所以，我们有两种情况

  1. 不区分大小写的排序列表和使用compareToIgnoreCase
  2. 区分大小写的排序列表和使用compareTo

除了二进制搜索中的这些选项之外，您还可以在线性搜索中选择：是否使用equals或equalsIgnoreCase. 我对所有这些案例进行了测试并进行了比较。平均结果：

  • 线性搜索equals：时间：725536 ns；比较：117941；时间/比较：6.15 ns
  • 线性搜索equalsIgnoreCase：时间：1064334 ns；比较：117940；时间/比较：9.02 ns
  • 二进制搜索compareToIgnoreCase：时间：1619 ns；比较：16；时间/比较：101.19 ns
  • 二进制搜索compareTo：时间：763 ns；比较：16；时间/比较：47.69 ns

所以，现在我们可以清楚地看到您的问题：该compareToIgnoreCase方法花费的时间大约是该方法的 16 倍equals！因为，平均而言，二进制搜索需要 16 次比较才能找到给定的单词，所以您可以在这段时间内执行 124 次线性比较。因此，如果您使用比这更短的单词列表进行测试，由于它们使用的方法不同，线性搜索确实总是比二分搜索快。

实际上，我还计算了线性搜索能够比二进制搜索更快地找到的单词数：使用该方法时为 164，使用该compareTo方法时为 614 compareToIgnoreCase。在 235882 个单词的列表中，这大约是 0.3%。所以总而言之，我认为仍然可以肯定地说二进制搜索比线性搜索快。:)

在你问之前的最后一点：我从binarySearch方法中删除了排序代码，因为这实际上是完全不同的事情。由于您正在比较两种搜索算法，因此如果您将排序算法的成本添加到其数字中，这对另一个是不公平的。我已经在另一个答案中发布了以下内容作为评论，但为了完整起见，我将在此处复制：

二分查找增加了排序的开销。所以如果你只需要从数组中找到一个元素，线性搜索总是更快，因为排序至少需要 O(n log n) 时间，然后二进制搜索需要 O(log n) 时间，主要由 O(n登录 n) 操作。线性搜索在 O(n) 时间内执行，优于 O(n log n)。但是一旦你对数组进行了排序，O(log n) 就比 O(n) 好得多。

如果您坚持在binarySearch方法中使用排序命令，您应该知道，在我的设置中，从最初的随机顺序排序长长的单词列表平均需要超过 140000000 ns 或 0.14 秒。equals在那个时候，您可以使用该方法执行大约 23000000 次比较，因此如果 a）您的数组是随机顺序的，并且 b）如果您只需要从那里找到一个或几个元素，那么您真的不应该使用二进制搜索.

还有一件事情。在此示例中，您正在搜索字符串数组中的单词，访问数组中的项目的成本可以忽略不计，因为该数组保存在计算机的快速主存储器中。但是，如果你有一大堆有序的文件，并且你试图从中找到一些东西，那么访问单个文件的成本将使其他计算的成本可以忽略不计。因此，在那种情况下，二分搜索也会完全摇摆不定。

于 2012-05-06T11:31:24.610 回答
0

您的代码不测量二进制搜索，但也在进行搜索之前对数组进行排序。这总是比简单的线性搜索要长。

于 2012-05-05T20:35:57.710 回答
0 
} else if (array [midPt].compareToIgnoreCase (word) > 0)  {

你根本不需要这个测试。此时代码中没有其他可能性。它不相等，而且不少于：您已经测试过这些；所以它必须大于。

因此，您可以减少 33% 的比较。

于 2012-05-06T00:30:37.907 回答