Kann man über unsortierte Datenstrukturen (wie Array, Baum) iterieren, wobei mehrere Threads die Iteration beschleunigen?

Question

Kann die Iteration über unsortierte Datenstruktur wie Array, Baum mit mehreren Threads schneller machen?

Zum Beispiel habe ich große Array mit unsortierten Daten.

int array[1000]; 

Ich suche array[i] == 8 Kann laufen:

Gewinde 1:

for(auto i = 0; i < 500; i++) 
{ 
    if(array[i] == 8) 
     std::cout << "found" << std::endl; 
} 

Thema 2:

for(auto i = 500; i < 1000; i++) 
{ 
    if(array[i] == 8) 
     std::cout << "found" << std::endl; 
} 

schneller t han normale Iteration?

@update

Ich habe einfach geschrieben Test Hexe Problem besser beschreiben: Für int* array = new int[100000000]; Suche und Wiederholen es 1000 mal ich das Ergebnis bekam:

a 
Number of threads = 2 
End of multithread iteration 
End of normal iteration 
Time with 2 threads 73581 
Time with 1 thread 154070 
Bool values:0 
0 
0 

Process returned 0 (0x0) execution time : 256.216 s 
Press any key to continue. 

Was mehr ist, wenn Programm lief mit 2 Threads CPU-Auslastung des Prozesses war ~ 90% und beim Iterieren mit 1 Thread war es nie mehr als 50%.

Also Smeeheey und erip sind richtig, dass es Iteration schneller machen kann. Natürlich kann es schwieriger für nicht so triviale Probleme sein.

Und wie ich von diesem Test gelernt habe, ist, dass der Compiler Hauptthread optimieren kann (wenn ich nicht Boolean Speichern von Ergebnissen der Suchschleife im Hauptthread wurde ignoriert), aber es wird das nicht für andere Threads tun.

Dies ist Code, den ich verwendet habe:

#include<cstdlib> 
#include<thread> 
#include<ctime> 
#include<iostream> 
#define SIZE_OF_ARRAY 100000000 
#define REPEAT 1000 
inline bool threadSearch(int* array){ 
    for(auto i = 0; i < SIZE_OF_ARRAY/2; i++) 
     if(array[i] == 101) // there is no array[i]==101 
      return true; 
     return false; 
} 
int main(){ 
    int i; 
    std::cin >> i; // stops program enabling to set real time priority of the process 
    clock_t with_multi_thread; 
    clock_t normal; 
    srand(time(NULL)); 
    std::cout << "Number of threads = " 
       << std::thread::hardware_concurrency() << std::endl; 
    int* array = new int[SIZE_OF_ARRAY]; 
    bool true_if_found_t1 =false; 
    bool true_if_found_t2 =false; 
    bool true_if_found_normal =false; 
    for(auto i = 0; i < SIZE_OF_ARRAY; i++) 
     array[i] = rand()%100; 
    with_multi_thread=clock(); 
    for(auto j=0; j<REPEAT; j++){ 
     std::thread t([&](){ 
      if(threadSearch(array)) 
       true_if_found_t1=true; 
     }); 
     std::thread u([&](){ 
      if(threadSearch(array+SIZE_OF_ARRAY/2)) 
       true_if_found_t2=true; 
     }); 
     if(t.joinable()) 
      t.join(); 
     if(u.joinable()) 
      u.join(); 

    } 
    with_multi_thread=(clock()-with_multi_thread); 
    std::cout << "End of multithread iteration" << std::endl; 
    for(auto i = 0; i < SIZE_OF_ARRAY; i++) 
     array[i] = rand()%100; 
    normal=clock(); 
    for(auto j=0; j<REPEAT; j++) 
     for(auto i = 0; i < SIZE_OF_ARRAY; i++) 
      if(array[i] == 101) // there is no array[i]==101 
       true_if_found_normal=true; 
    normal=(clock()-normal); 
    std::cout << "End of normal iteration" << std::endl; 
    std::cout << "Time with 2 threads " << with_multi_thread<<std::endl; 
    std::cout << "Time with 1 thread " << normal<<std::endl; 
    std::cout << "Bool values:" << true_if_found_t1<<std::endl 
       << true_if_found_t2<<std::endl 
       <<true_if_found_normal<<std::endl;// showing bool values to prevent compiler from optimization 
    return 0; 
} 

Answer 1

Die Antwort ist ja, es kann es schneller machen - aber nicht unbedingt. In Ihrem Fall, wenn Sie über ziemlich kleine Arrays iterieren, ist es wahrscheinlich, dass der Overhead beim Starten eines neuen Threads viel höher ist als der gewonnene Nutzen. Wenn Ihr Array viel größer wäre, würde dies als Anteil der Gesamtlaufzeit reduziert werden und sich letztendlich lohnen. Beachten Sie, dass Sie nur dann schneller werden, wenn Ihr System über mehr als einen physischen Kern verfügt.

Darüber hinaus sollten Sie beachten, dass während der Code, der das Array in Ihrem Fall liest, absolut Thread-sicher ist, nicht zu std :: cout schreiben (Sie werden sehr seltsam aussehende Ausgabe, wenn Sie dies versuchen). Stattdessen sollte Ihr Thread etwas wie einen Integer-Typ zurückgeben, der die Anzahl der gefundenen Instanzen angibt.