Algorithm optimization - parallel AsyncTasks or threads?

Question

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

It divides the 400 images into groups of 5. So there are 80 images in each group.

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 3,160 comparisons. Or 3,160 sec. Similarly, image81 will compare itself with image82-160 and so on. So all the "group comparisons" are finished in 3,160 sec because they're run in parallel.

The second part of the algorithm will compare group 1 elements with group 2 elements, group 2 with group 3, group 3 with group 4 and so on. This would mean image1 will be compared with image81-160, which is 80 comparisons and so total comparisons between group 1 and group 2 would be 80*80=6400 comparisons. Is it possible to have each image comparison in parallel with group comparisons? That is if image1 is comparing itself with image81-160 then image2 should do the same and so on, while the other groups are doing the same. So, this part should take only 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 realize the more the groups, more time it'd take. So, I'd have to increase group size to reduce the increase in time. Either way, it cuts down the time to almost 1/4th it's actual time.

Is this algorithm unrealistic? If so, why? What are it's flaws? How would I fix it? Is there a better algorithm to compare a list of images faster? Obviously not quick sort, I can't arrange the images in an 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'll want to be able to use the same number of worker threads throughout the program. For this you'll need to use an even number of threads, say 8.

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

On Pass2, Thread1 and Thread2 both process images 1-100. 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.

Passes 3 through 8 follow the same pattern - the two threads assigned to the two groups being processed split up the groups between them. This way you keep all of your threads busy. However, you'll need an even number of threads for this in order to simplify group partitioning.

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