Ottimizzazione dell'algoritmo - AsyncTask o thread paralleli?

Question

Attualmente ho un singolo AsyncTask che attualmente confronta le immagini usando la tecnica bubble sort usando OpenCV. Dire, devo confrontare le immagini 400 l'un l'altro. Ciò significherebbe i confronti 400*401/2=80,200. Supponiamo che un confronto impieghi 1 secondo. Quindi, questo è 80,200 sec che è di circa 22.27 hours che è incredibilmente lungo. Quindi, ho sviluppato un algoritmo di questo tipo:

Divide le immagini 400 in gruppi di 5. Quindi ci sono le immagini 80 in ciascun gruppo.

La prima parte dell'algoritmo sono le immagini che si confrontano all'interno dei membri del gruppo.

Quindi, image1 si confronterà con image2-80, il che significa che ci sono i confronti 79. image2 avrà confronti 78 e così via. Il che rende i confronti 3,160. O 3,160 sec. Allo stesso modo, image81 si confronterà con image82-160 e così via. Quindi tutti i "confronti di gruppo" sono finiti in 3,160 sec perché sono eseguiti in parallelo.

La seconda parte dell'algoritmo confronterà group 1 elementi con elementi group 2, group 2 con group 3, group 3 con group 4 e così via. Ciò significherebbe che image1 verrà confrontato con image81-160, ovvero confronti 80 e quindi i confronti totali tra group 1 e group 2 corrisponderanno a 80*80=6400 confronti. È possibile confrontare ogni immagine in parallelo con i confronti di gruppo? Cioè se image1 si confronta con image81-160 quindi image2 dovrebbe fare lo stesso e così via, mentre gli altri gruppi stanno facendo lo stesso. Quindi, questa parte dovrebbe prendere solo 6400 sec.

Ora, group1 saranno confrontati con group3, group2 con group4, group3 con group5. ->6400 sec

Dopo di che, group1 will be compared with group4 e group2 con group5. ->6400 sec

Quindi tutti i gruppi vengono confrontati.

Tempo totale = 3160+6400+6400+6400=22,360sec. Capisco più i gruppi, più tempo ci vorrebbe. Quindi, dovrei aumentare le dimensioni del gruppo per ridurre l'aumento nel tempo. Ad ogni modo, riduce il tempo a quasi 1/4th è il tempo reale.

Questo algoritmo non è realistico? Se è così, perché? Quali sono i suoi difetti? Come lo risolverei? Esiste un algoritmo migliore per confrontare più rapidamente un elenco di immagini? Ovviamente no quick sort, non riesco a organizzare le immagini in ordine ascendente o discendente. O posso?

Se questo algoritmo è possibile? Quale sarebbe il modo migliore per implementarlo? Thread o AsyncTask?

Answer 1

Questo è un algoritmo realistico, ma idealmente si vorrà essere in grado di utilizzare lo stesso numero di thread di lavoro in tutto il programma. Per questo dovrai usare un numero pari di thread, ad esempio 8.

In Pass1, Filettatura1 elabora immagini 1-50, Thread2 processi immagini 51-100, ecc

In Pass2, Filettatura1 e Thread2 entrambe le immagini di processo 1-100. Thread1 elabora le immagini 1-25 e 50-75, Thread2 elabora le immagini 26-50 e le immagini 76-100. Quindi Thread1 elabora le immagini 1-25 e 76-100 e Thread2 elabora le immagini 26-75.

I passaggi da 3 a 8 seguono lo stesso schema: i due thread assegnati ai due gruppi in elaborazione dividono i gruppi tra di loro. In questo modo tieni impegnati tutti i tuoi thread. Tuttavia, per semplificare il partizionamento dei gruppi è necessario un numero pari di thread.

Codice di esempio per 4 thread

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);