3

これが要旨のクラスです 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) 配列を 1 回並べ替え、バイナリ検索を 1000 回使用して異なる要素を検索する

于 2012-05-05T20:36:44.477 に答える
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(...)メソッドを使用する必要があります。

したがって、2つのケースがあります

  1. 大文字と小文字を区別せずにソートされたリストとcompareToIgnoreCase
  2. 大文字と小文字を区別してソートされたリストとcompareTo

二分探索のこれらのオプションに加えて、線形探索のオプションもあります：使用するequalsかequalsIgnoreCase。私はこれらすべてのケースについてテストを実行し、それらを比較しました。平均結果：

  • 線形探索equals：時間：725536 ns; 比較：117941; 時間/比較：6.15 ns
  • 線形探索equalsIgnoreCase：時間：1064334 ns; 比較：117940; 時間/比較：9.02 ns
  • compareToIgnoreCase：時間：1619nsの二分探索; 比較：16; 時間/比較：101.19 ns
  • compareTo：時間：763nsの二分探索; 比較：16; 時間/比較：47.69 ns

これで、問題がはっきりとわかります。この方法には、このcompareToIgnoreCase方法の約16倍の時間がかかりますequals。与えられた単語を見つけるのに平均して二分探索16回の比較が必要なので、その間に124回の線形比較を実行できます。したがって、それより短い単語リストでテストする場合、線形検索は、実際、使用している方法が異なるため、バイナリ検索よりも常に高速です。

私は実際に、線形検索が二分探索よりも速く見つけることができた単語の数を数えました：メソッドを使用する場合は164、compareToメソッドを使用する場合は614 compareToIgnoreCase。235882語のリストのうち、それは約0.3パーセントです。したがって、全体として、二分探索は線形探索よりも高速であると言っても差し支えないと思います。:)

binarySearch質問する前の最後のポイント：実際にはまったく異なるものであるため、メソッドから並べ替えコードを削除しました。2つの検索アルゴリズムを比較しているため、並べ替えアルゴリズムのコストをその数値に追加すると、もう一方は公平ではありません。すでに別の回答にコメントとして以下を投稿しましたが、完全を期すためにここにコピーします。

二分探索には、ソートのオーバーヘッドコストが追加されます。したがって、配列から1つの要素のみを検索する必要がある場合、線形検索は常に高速です。これは、並べ替えに少なくともO（n log n）時間がかかり、次にバイナリ検索にO（log n）時間がかかり、O（nログn）操作。線形探索はO（n）時間で実行されます。これは、O（n log n）よりも優れています。ただし、配列を並べ替えると、O（log n）はO（n）よりもはるかに優れています。

メソッドにsortingコマンドbinarySearchを含めることを主張する場合、私の設定では、最初にランダムな順序からの単語の長いリストのソートに、平均で140000000 ns、つまり0.14秒以上かかることに注意してください。equalsそのとき、このメソッドを使用して23000000の比較を実行できたため、a）配列がランダムな順序であり、b）そこから要素を1つまたは2つだけ見つける必要がある場合は、バイナリ検索を使用しないでください。 。

後もう一つ。この例では、文字列配列内の単語を検索している場合、配列はコンピューターの高速メインメモリに保存されるため、配列内の項目にアクセスするコストはごくわずかです。しかし、たとえば、大量の順序付けられたファイルがあり、それらから何かを見つけようとした場合、単一のファイルにアクセスするコストは、代わりに他のすべての計算のコストを無視できるようにします。したがって、バイナリ検索はそのシナリオでは完全に揺らいでしまいます（あまりにも）。

于 2012-05-06T11:31:24.610 に答える
1

多くの理由で、ベンチマークに欠陥があります。

  • ファイルの内容はわかりません。検索語が先頭にある場合、線形検索は二分検索よりも高速になります。
  • 線形検索は equals と比較されますが、二分検索は equalsIgnoreCase と比較されます。
  • JIT がコードをコンパイルするのに十分な回数コードを実行していない

二分探索アルゴリズムが正しいかどうかは確認していませんが、JDK に同梱されているもの (java.util.Arrays クラス内) を使用しないでください。

とにかく、何も測定する必要はありません。バイナリ検索は、平均して、線形検索よりも高速です。改めて証明する必要はありません。

于 2012-05-05T20:35:39.097 に答える
0 
} else if (array [midPt].compareToIgnoreCase (word) > 0)  {

このテストはまったく必要ありません。コードのこの時点では、他の可能性はありません。それは等しくなく、それよりも小さくありません: あなたはすでにそれらをテストしました。したがって、それはより大きくなければなりません。

したがって、比較を 33% 減らすことができます。

于 2012-05-06T00:30:37.907 に答える
0

コードはバイナリ検索を測定しませんが、検索を行う直前の配列の並べ替えも測定します。これは、単純な線形検索よりも常に長くなります。

于 2012-05-05T20:35:57.710 に答える