İkili arama, n modern bir CPU'da doğrusal aramadan daha hızlı mı?

Question

Şube tahmininin harikalarından dolayı, bir ikili arama, bir tam sayı dizisi boyunca doğrusal bir aramayla daha yavaş olabilir. Tipik bir masaüstü işlemcisinde, bu dizinin ikili arama kullanmadan önce ne kadar büyük olması gerekir? Yapının birçok arama için kullanılacağını varsayalım.

Answer 1

Biraz C++ kıyaslama denedim ve şaşırdım - doğrusal arama birkaç düzine ürüne kadar geçerli gibi görünüyor ve ikili aramaların bu boyutlar için daha iyi olduğu bir durum bulamadım. Belki gcc's STL iyi ayarlanmamış? Ama sonra - ne aramanın bu her iki türdeki uygulamak için kullanabileceğiniz -) Herkes benim fena halde zamanlama bozulacağı saçma şey yaptıysanız görebilirsiniz Yani burada, benim kod ...:?

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <stdlib.h> 

int data[] = {98, 50, 54, 43, 39, 91, 17, 85, 42, 84, 23, 7, 70, 72, 74, 65, 66, 47, 20, 27, 61, 62, 22, 75, 24, 6, 2, 68, 45, 77, 82, 29, 59, 97, 95, 94, 40, 80, 86, 9, 78, 69, 15, 51, 14, 36, 76, 18, 48, 73, 79, 25, 11, 38, 71, 1, 57, 3, 26, 37, 19, 67, 35, 87, 60, 34, 5, 88, 52, 96, 31, 30, 81, 4, 92, 21, 33, 44, 63, 83, 56, 0, 12, 8, 93, 49, 41, 58, 89, 10, 28, 55, 46, 13, 64, 53, 32, 16, 90 
      }; 

int tosearch[] = {53, 5, 40, 71, 37, 14, 52, 28, 25, 11, 23, 13, 70, 81, 77, 10, 17, 26, 56, 15, 94, 42, 18, 39, 50, 78, 93, 19, 87, 43, 63, 67, 79, 4, 64, 6, 38, 45, 91, 86, 20, 30, 58, 68, 33, 12, 97, 95, 9, 89, 32, 72, 74, 1, 2, 34, 62, 57, 29, 21, 49, 69, 0, 31, 3, 27, 60, 59, 24, 41, 80, 7, 51, 8, 47, 54, 90, 36, 76, 22, 44, 84, 48, 73, 65, 96, 83, 66, 61, 16, 88, 92, 98, 85, 75, 82, 55, 35, 46 
       }; 

bool binsearch(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end) { 
    return std::binary_search(begin, end, i); 
} 

bool linsearch(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end) { 
    return std::find(begin, end, i) != end; 
} 

int main(int argc, char *argv[]) 
{ 
    int n = 6; 
    if (argc < 2) { 
    std::cerr << "need at least 1 arg (l or b!)" << std::endl; 
    return 1; 
    } 
    char algo = argv[1][0]; 
    if (algo != 'b' && algo != 'l') { 
    std::cerr << "algo must be l or b, not '" << algo << "'" << std::endl; 
    return 1; 
    } 
    if (argc > 2) { 
    n = atoi(argv[2]); 
    } 
    std::vector<int> vv; 
    for (int i=0; i<n; ++i) { 
    if(data[i]==-1) break; 
    vv.push_back(data[i]); 
    } 
    if (algo=='b') { 
    std::sort(vv.begin(), vv.end()); 
    } 
    bool (*search)(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end); 
    if (algo=='b') search = binsearch; 
    else search = linsearch; 
    int nf = 0; 
    int ns = 0; 
    for(int k=0; k<10000; ++k) { 
    for (int j=0; tosearch[j] >= 0; ++j) { 
     ++ns; 
     if (search(tosearch[j], vv.begin(), vv.end())) 
     ++nf; 
    } 
    } 
    std::cout << nf <<'/'<< ns << std::endl; 

    return 0; 
} 

ve bir çekirdek ikilisi benim zamanlamaları benim bir çift:

AmAir:stko aleax$ time ./a.out b 93 
1910000/2030000 

real 0m0.230s 
user 0m0.224s 
sys 0m0.005s 

AmAir:stko aleax$ time ./a.out l 93 
1910000/2030000 

real 0m0.169s 
user 0m0.164s 
sys 0m0.005s 

Bunlar oldukça tekrarlanabilir konum zaten ...

OP diyor ki: Alex, sadece 1 ile diziyi doldurmak için programınızı düzenlenmiş .. n, std :: sort komutunu çalıştırmayın ve yaklaşık 10 milyon (mod integer bölümü) arama yapın. İkili arama, bir Pentium 4'te n = 150'deki doğrusal aramayı çekmeye başlar. Grafik renkleri için üzgünüm.

binary vs linear search http://spreadsheets.google.com/pub?key=tzWXX9Qmmu3_COpTYkTqsOA&oid=1&output=image

Answer 2

İstediğiniz soruyu ele alan bu article adresine bir göz atmak isteyebilirsiniz.

Answer 3

Pek fazla değil ama tam olarak kıyaslamadan söylemek zor.

Şahsen ikili aramayı tercih etme eğilimindeyim çünkü iki yıl içinde, başka biri küçük dizinizin boyutunu dört katına çıkardığında, çok fazla performans kaybetmediniz. Özellikle şu an bir darboğaz olduğunu ve sürece olabildiğince hızlı olmamız gerektiğini biliyordum.

Bunu söyledikten sonra, hash tablolarının da olduğunu unutmayın; Onlar hakkında ikili soruya benzer bir soru sorabilirsiniz.

Answer 4

Şube tahmininin önemli olması gerektiğine inanıyorum çünkü doğrusal bir aramanın da dalları vardır. Ve bilgime göre sizin için doğrusal arama yapabilen bir SIMD yoktur.

yararlı bir model ikili arama her bir adımı, bir çarpan ekonomik C

C log n = n

Böylece olduğunu varsayalım olacaktır Having Bu konuda gerçekten kıyaslama yapmadan, C için bir tahminde bulunursunuz ve bir sonraki tam sayıya yuvarlarsınız. Örneğin, C = 3'ü tahmin ederseniz, n = 11'de ikili arama kullanmak daha hızlı olacaktır.

Answer 5

ben ayrıntılı olarak bu soruyu inceledik bir Bulgularımı in this blog post özetledik.