Optymalizacja algorytmu - równoległe AsyncTasks lub wątki?

Question

Obecnie mam jedno AsyncTask które obecnie porównuje zdjęć przy użyciu bubble sort technika przy użyciu OpenCV. Powiedz, że muszę porównywać ze sobą obrazy 400. Oznaczałoby to porównania 400*401/2=80,200. Załóżmy, że jedno porównanie trwa 1 sekundę. To jest 80,200 sec, który jest około 22.27 hours, który jest absurdalnie długi. Opracowałem więc algorytm tego typu:

Dzieli on obrazy 400 na grupy 5. Tak więc w każdej grupie znajduje się 80 obrazów.

Pierwsza część algorytmu jest obrazy porównując się w ciągu członków grupy.

Więc, image1 będzie porównywać się z image2-80, co oznacza, że ​​są porównania 79. image2 będzie mieć porównania 78 i tak dalej. Co czyni porównania 3,160. Lub 3,160 sec. Podobnie, image81 będzie porównywać się z image82-160 i tak dalej. Tak więc wszystkie "porównania grup" są zakończone w 3,160 sec, ponieważ są prowadzone równolegle.

Druga część algorytmu porówna group 1 elementy z group 2 elementów, group 2 z group 3, group 3 z group 4 i tak dalej. Oznaczałoby to, że image1 zostanie porównane z image81-160, co stanowi porównanie 80, a więc całkowite porównania między group 1 i group 2 byłyby porównaniami 80*80=6400. Czy możliwe jest porównywanie każdego obrazu równolegle z porównywaniem grup? To znaczy, jeśli image1 porównuje się z image81-160, wtedy image2 powinno zrobić to samo i tak dalej, podczas gdy inne grupy robią to samo. Tak więc ta część powinna zająć tylko 6400 sec.

Teraz group1 zostaną porównane z group3, group2 z group4, group3 z group5. ->6400 sec

Po tym, group1 will be compared with group4 i group2 z group5. ->6400 sec

więc wszystkie grupy są porównywane.

Łączny czas = 3160+6400+6400+6400=22,360sec. Zdaję sobie sprawę, że im więcej grup, tym więcej czasu zajmie. Musiałbym zwiększyć rozmiar grupy, aby skrócić czas. Tak czy inaczej, skraca czas prawie do 1/4th to jest faktyczny czas.

Czy ten algorytm jest nierealistyczny? Jeśli tak, dlaczego? Jakie to wady? Jak to naprawić? Czy istnieje lepszy algorytm do szybszego porównywania listy obrazów? Oczywiście nie mogę quick sort, nie mogę uporządkować zdjęć w porządku rosnącym lub malejącym. Czy mogę?

Jeśli ten algorytm jest możliwy? Jaki byłby najlepszy sposób na jego wdrożenie? Thread lub AsyncTask?

Answer 1

Jest to realistyczny algorytm, ale idealnie będziemy chcieli, aby móc korzystać z tej samej liczby wątków roboczych w całym programie. W tym celu musisz użyć parzystej liczby wątków, powiedzmy 8.

Na Pass1, thread1 przetwarza obrazy 1-50, thread2 przetwarza obrazy 51-100 itp

On Pass2, thread1 i thread2 zarówno obrazy procesu 1-100. Wątek1 przetwarza obrazy 1-25 i 50-75, wątek2 przetwarza obrazy 26-50 i obrazy 76-100. Następnie wątek1 przetwarza obrazy 1-25 i 76-100, a wątek2 przetwarza obrazy 26-75.

Przepustki od 3 do 8 mają ten sam wzór - dwa wątki przypisane do dwóch przetwarzanych grup dzielą grupy między nimi. W ten sposób wszystkie wątki będą zajęte. Do tego celu potrzebna jest parzysta liczba wątków, aby uprościć partycjonowanie grupowe.

Przykładowy kod dla 4 Odpowiedź

class ImageGroup { 
    final int index1; 
    final int index2; 
} 

class ImageComparer implements Runnable { 
    final Image[] images; 
    ImageGroup group1; 
    ImageGroup group2; 

    public ImageComparer(Image[] images, ImageGroup group1, ImageGroup group2) { 
     ... 
    } 

    public void run() { 
     if(group2 == null) { // Compare images within a single group 
      for(int i = group1.index1; i < group1.index2; i++) { 
       for(int j = i + 1; j < group1.inex2; j++) { 
        compare(images[i], images[j]); 
       } 
      } 
     } else { // Compare images between two groups 
      for(int i = group1.index1; i < group1.index2; i++) { 
       for(int j = group2.index1; j < group2.index2; j++) { 
        compare(images[i], images[j]); 
       } 
      } 
     } 
    } 
} 

ExecutorService executor = new ThreadPoolExecutor(); // use a corePoolSize equal to the number of target threads 
// for 4 threads we need 8 image groups 
ImageGroup group1 = new ImageGroup(0, 50); 
ImageGroup group2 = new ImageGroup(50, 100); 
... 
ImageGroup group8 = new ImageGroup(450, 500); 

ImageComparer comparer1 = new ImageComparer(images, group1, null); 
ImageComparer comparer2 = new ImageComparer(images, group3, null); 
... 
ImageComparer comparer4 = new ImageComparer(images, group7, null); 

// submit comparers to executor service 
Future future1 = executor.submit(comparer1); 
Future future2 = executor.submit(comparer2); 
Future future3 = executor.submit(comparer3); 
Future future4 = executor.submit(comparer4); 

// wait for threads to finish 
future1.get(); 
future2.get(); 
future3.get(); 
future4.get(); 

comparer1 = new ImageComparer(images, group2, null); 
... 
comparer4 = new ImageComparer(images, group8, null); 

// submit to executor, wait to finish 

comparer1 = new ImageComparer(images, group1, group3); 
... 
comparer4 = new ImageComparer(images, group7, group6); 

// submit to executor, wait to finish 

comparer1 = new ImageComparer(images, group1, group4); 
... 
comparer4 = new ImageComparer(images, group7, group5);