Soru Neden std :: binary_search argümanları ileri yineleyicilerdir?


Perusing yaparken http://en.cppreference.com/w/cpp/algorithm/binary_search Yinelemeyi bir argüman olarak aldığını fark ettim. Şimdi kafam karıştı, çünkü rasgele bir erişim yineleyicisi olacağını düşündüğümden, ikili arama aslında ikili olacak.

Merakımı tatmin etmek için küçük bir program yazdım:

#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 ile derlemek ve çalışıyor

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

Makinemde aşağıdaki sonuçları sağlar:

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

Yani aslında bir ileriye doğru bir liste üzerinde ikili arama yapmaz gibi görünüyor. Şimdi benim sorularım:

Neden böyle kafa karıştırıcı bir isim?

Kod böyle neden izin verdi?

Referans, neden "İlk ve son arasındaki mesafede Logaritmik" diyor?

Standart bunun hakkında ne söylemeli?

DÜZENLEME: Şimdi kod aramadan önce listeyi sıralar - aptal hata, şimdi sonuçlar:

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

Ve tabii ki hala logaritmik değil;)


18
2017-11-21 21:10


Menşei


Çalışmak için binary_search için listenin sıralanması gerekmez mi? - jcoder
@ J99 İyi nokta. Yakında sorumu güncelleyeceğim. - milleniumbug
Hala sadece ileri yineleyicilerle (ve rasgele erişim) log (n) karşılaştırmaları yapması gerekiyor. Rastgele erişimin avantajı, ileriye doğru aramaktan ziyade ileriye atlayabilme yeteneğidir. - Martin York


Cevaplar:


Standardın türetildiği orijinal SGI STL uygulamasının dokümanları, bunu belirtir

Karşılaştırmaların sayısı logaritmiktir: çoğu günlüğünde (son - ilk) + 2. Eğer ForwardIterator Rastgele Erişim Yineleyicidir, daha sonra aralıktaki adım sayısı da logaritmiktir; aksi halde, adımların sayısı sonuncuyla orantılıdır - önce.

Bu, sayısı karşılaştırmalar her zaman logaritmiktir, rasgele erişilebilirlikten etkilenen ilerlemelerin sayısı ise doğrusal olabilir. Uygulamada, stl::advance Muhtemelen yineleyici rasgele erişim, aksi takdirde doğrusal ise karmaşıklık sabit olduğu için kullanılır.

Doğrusal bir iteratör ilerlemesi sayısıyla ikili bir arama, ancak bir karşılaştırmanın çok pahalı olması durumunda, logaritmik karşılaştırmaların bir anlamı vardır. Örneğin, karşılaştırmak için disk veya ağ erişimi gerektiren karmaşık nesnelerin ayrılmış bir listesi varsa, muhtemelen bir ikili arama ile doğrusal bir olandan daha iyidir.


17
2017-11-21 21:14



Fakat lineer aramadan iki kat daha fazla yineleme olacak. Karşılaştırmalar daha hızlı olmak için çok pahalı olmalı, değil mi? - milleniumbug
Bu doğrudur, ancak bir yineleyiciyi ilerletmek genellikle çok ucuz olduğundan, onu yenmek kolaydır. Örneğin, karşılaştırmanız size bir dosya okuyabiliyorsa, ikili arama kolayca doğrusal aramayı yenecektir. - user1071136
Evet, şimdi bu mantıklı - kesinlikle bir işaretçiyi işaretlemek, sabit diske veya ağa erişmekten çok daha hızlıdır. Bu yüzden ikili arama bu tür bir durumda yararlı olabilir. Yeni bir şey öğrendim. Teşekkürler. - milleniumbug


Ne aksine web siteleri söyleyebilir (ör. "logaritmik distance(first, last)"), standart aslında sadece hakkında konuşuyor karşılaştırmalar (ör. 25.4.3.1, lower_bound):

Karmaşıklık: En fazla log2(last − first) + O(1) karşılaştırmalar

Yineleyicinin artırılması değil karmaşıklığa dahil! Standart kitaplığın tüm yineleyici artışlarının amortize edilmiş sabit karmaşıklığa sahip olmasını gerektirdiğine dikkat edin, bu nedenle yineleyicileri arttırmadan O (N) siparişinin maliyeti olacaktır (ancak bu muhtemelen çok küçük bir ön faktörü vardır). Özellikle (25.4.3):

Rastgele olmayan erişim yineleyicileri için [algoritmalar] doğrusal bir adımı yürütür.


6
2017-11-21 21:18





Standart sıralanmış arama algoritmalarını belirtir (std::lower_bound(), std::upper_bound(), ve std::binary_search()) İleri ve ikili yineleyiciler için doğrusal sürede çalışmak. Rasgele erişim için zaman logaritmiktir.

Sayısı comparisons Ancak, logaritmik olmak için sınırlıdır.


2
2017-11-21 21:18