21

http://en.cppreference.com/w/cpp/algorithm/binary_searchを熟読しているときに、前方反復子を引数として取ることに気付きました。むしろランダムアクセスイテレータの方がいいと思っていたので、今は混乱しています。そのため、バイナリ検索は実際にはバイナリになります。

私の好奇心を満たすために、私は小さなプログラムを書きました:

#include <iostream>
#include <vector>
#include <forward_list>
#include <list>
#include <deque>
#include <algorithm>
#include <chrono>
#include <random>

int main()
{
    std::uniform_int_distribution<int> uintdistr(-4000000, 4000000);
    std::mt19937 twister(std::chrono::high_resolution_clock::to_time_t(std::chrono::high_resolution_clock::now()));
    size_t arr[] = { 200000, 400000, 800000, 1600000, 3200000, 6400000, 12800000 };
    for(auto size : arr)
    {
        std::list<int> my_list;
        for(size_t i = 0; i < size; i++)
            my_list.push_front(uintdistr(twister));
        std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
        my_list.sort(); //fixed
        start = std::chrono::high_resolution_clock::now();

        std::binary_search(my_list.begin(), my_list.end(), 1252525);

        end = std::chrono::high_resolution_clock::now();
        long long unsigned elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
        std::cout << "Test finished in " << elapsed_time << "\n";
    }
}

gcc 4.7.0 でコンパイルして実行する

g++ -std=c++11 test.cpp

私のマシンで次の結果を提供します：

Test finished in 0
Test finished in 15625
Test finished in 15625
Test finished in 46875
Test finished in 93750
Test finished in 171875
Test finished in 312500

そのため、実際には転送リストでバイナリ検索を実行していないようです。今私の質問は次のとおりです。

なんでこんな紛らわしい名前？

このようなコードが許可されるのはなぜですか?

参照が「最初と最後の間の距離の対数」であると言っているのはなぜですか?

標準はそれについて何を言わなければなりませんか？

編集:コードは検索の前にリストをソートします-愚かな間違い、結果は次のようになります:

Test finished in 46875
Test finished in 109375
Test finished in 265625
Test finished in 546875
Test finished in 1156250
Test finished in 2625000
Test finished in 6375000

もちろん、まだ対数ではありません;）

4

3 に答える 3

19

標準が派生した元のSGISTL実装のドキュメントには、次のように記載されています。

比較の数は対数です。最大でlog（last --first）+ 2です。ForwardIteratorがランダムアクセスイテレータの場合、範囲内のステップ数も対数です。それ以外の場合、ステップ数はlast-firstに比例します。

つまり、比較の数は常に対数ですが、ランダムなアクセス可能性の欠如によって影響を受ける進歩の数は線形である可能性があります。実際にstl::advanceは、おそらくが使用されます。イテレータがランダムアクセスの場合は複雑さが一定で、それ以外の場合は線形です。

線形の数のイテレータの進歩を伴うが、対数の比較の数を伴う二分探索は、比較が非常に高価である場合に意味があります。たとえば、複雑なオブジェクトのソートされたリンクリストがあり、比較するためにディスクまたはネットワークアクセスが必要な場合は、線形検索よりもバイナリ検索の方がはるかに優れています。

于 2012-11-21T21:14:34.203 に答える
6

ウェブサイトが言うこととは反対に(例: 「対数distance(first, last)」)、標準は実際には比較についてのみ述べています(例: 25.4.3.1, lower_bound):

複雑さ: せいぜいlog2(last − first) + O(1)比較

イテレータのインクリメントは複雑さに含まれていません! ただし、標準ライブラリでは、すべてのイテレータのインクリメントが一定の複雑さを償却する必要があるため、イテレータをインクリメントすることで O(N) のオーダーのコストが発生することに注意してください (ただし、これには非常に小さな主要因があると思われます)。特に (25.4.3):

非ランダム アクセス イテレータ [アルゴリズム] では、線形数のステップを実行します。

于 2012-11-21T21:18:37.100 に答える
2

標準では、ソートされた検索アルゴリズム ( std::lower_bound()、std::upper_bound()、およびstd::binary_search()) が順方向反復子およびバイナリ反復子に対して線形時間で機能するように指定されています。ランダム アクセスの場合、時間は対数です。

ただし、 の数はcomparisons対数に制限されていることに注意してください。

于 2012-11-21T21:18:08.173 に答える