Multi Threading Java

Question

In my program I essentially have a method similar to:

for (int x=0; x<numberofimagesinmyfolder; x++){
    for(int y=0; y<numberofimagesinmyfolder; y++){
        compare(imagex,imagey);
        if(match==true){
            System.out.println("image x matches image y");
        }
    }
}

So basically I have a folder of images and I compare all combinations of images...so compare image 1 against all images then image 2...and so on. My problem is when searching to see what images match, it takes a long time. I am trying to multithread this process. Does anyone have any idea of how to do this?

Are you comparing by some parameters or two images must be equal in general? — Autocrab
– Autocrab, Commented Jan 27, 2014 at 5:05

Chris Pitman · Accepted Answer · 2014-01-27 05:08:56Z

8

Instead of comparing the images every time, hash the images, save the hash, and then compare the hashes of each pair of messages. Since a hash is far smaller you can fit more into memory and cache, which should significantly speed up comparisons.

There is probably a better way to do the search for equality as well, but one option would be to stick all the hashes into an array then sort them by hash value. Then iterate over the list looking for adjacent entries that are equal. This should be O(n*log(n)) instead of O(n^2) like your current version.

answered Jan 27, 2014 at 5:08

Chris Pitman

13.1k3 gold badges44 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Voo Over a year ago

Depending on which hash you use you may want to actually compare for equality (with SHA-256 or similar that chance will be negligible though). Also just use a HashMap<Hash, List<String>> to make it O(n). For most situations most probably not even worth multithreading this further apart from separating the IO from the hash computation.

user2684301 · Accepted Answer · 2014-01-27 05:12:36Z

inner loop should start at y=x+1 to take advantage of symmetry.
load all images into memory first. don't do all compares from disk.
Use a Java ExecutorService (basically a thread pool). Queue tasks for all index combinations. Let threads pull index combinations out of a task queue and execute comparisons.

Here is some general code to do the multi threading:

public static class CompareTask implements Runnable {
    CountDownLatch completion;
    Object imgA;
    Object imgB;

    public CompareTask(CountDownLatch completion, Object imgA, Object imgB) {
        this.completion = completion;
        this.imgA = imgA;
        this.imgB = imgB;
    }

    @Override
    public void run() {
        // TODO: Do computation...

        try {
            System.out.println("Thread simulating task start.");
            Thread.sleep(500);
            System.out.println("Thread simulating task done.");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        completion.countDown();
    }
}

public static void main(String[] args) throws Exception {
    Object[] images = new Object[10];

    ExecutorService es = Executors.newFixedThreadPool(5);

    CountDownLatch completion = new CountDownLatch(images.length * (images.length - 1) / 2);

    for (int i = 0; i < images.length; i++) {
        for (int j = i + 1; j < images.length; j++) {
            es.submit(new CompareTask(completion, images[i], images[j]));
        }
    }

    System.out.println("Submitted tasks. Waiting...");
    completion.await();
    System.out.println("Done");

    es.shutdown();
}

Collectives™ on Stack Overflow

Multi Threading Java

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related