Algorithm Optimization - Parallel AsyncTasks or Threads?

Question

I currently have one AsyncTask that currently compares images using the bubble sort method using OpenCV. Let's say I have to compare 400 images with each other. This would mean comparisons of 400*401/2=80,200 . Suppose one comparison takes 1 second. So, 80,200 sec , which is around 22.27 hours , which is ridiculously long. So, I developed an algorithm of this type:

It divides 400 images into groups of 5 . Thus, in each group there are 80 images.

The first part of the algorithm is the images comparing themselves within the group members.

So, image1 will compare itself with image2-80 , which means there are 79 comparisons. image2 will have 78 comparisons and so on. Which makes comparisons 3,160 . Or 3,160 sec . Similarly, image81 will compare itself with image82-160 and so on. So, all the "group comparisons" were completed in 3,160 sec , because they are executed in parallel.

The second part of the algorithm will compare the elements of group 1 with the elements of group 2 , group 2 with group 3 , group 3 with group 4 and so on. This would mean that image1 would be compared with image81-160 , which corresponds to 80 , and therefore the general comparison between group 1 and group 2 would be 80*80=6400 comparisons. Is it possible that each image comparison is in parallel with group comparisons? That is, if image1 compares itself with image81-160 , then image2 should do the same and so on, while other groups do the same. So this part should only take 6400 sec .

Now group1 will be compared with group3 , group2 with group4 , group3 with group5 . → 6400 sec

After which group1 will be compared with group4 and group2 with group5 . → 6400 sec

So, all groups are compared.

Total time = 3160+6400+6400+6400=22,360sec . I understand that the more groups, the more time it will take. Therefore, I would have to increase the size of the group to reduce the time. In any case, this reduces the time to almost 1/4th actual time.

Is this algorithm unrealistic? If so, why? What are the disadvantages? How can i fix this? Is there a better algorithm for comparing a list of images faster? Obviously not quick sort , I cannot sort the images in ascending or descending order. Or can I?

If this algorithm is possible? What would be the best way to implement it? Thread or AsyncTask ?

Answer 1

This is a realistic algorithm, but ideally you want to use as many workflows throughout the program. For this you need to use an even number of threads, for example 8.

In Pass1, Thread1 processes images 1-50, Thread2 processes images 51-100, etc.

On Pass2, Thread1 and Thread2, images 1-100 are processed. Thread1 processes images 1-25 and 50-75, Thread2 processes images 26-50 and images 76-100. Then Thread1 processes images 1-25 and 76-100, and Thread2 processes images 26-75.

Passages from 3 to 8 follow the same pattern - two threads assigned to two processed groups divide the groups between them. This way you keep all your threads busy. However, to simplify group splitting, you need an even number of threads.

Sample code for 4 threads

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