4

I have to initialize a float[12000] via a for loop 12000 times. I then scan the array to look for values exceeding a certain threshold value. If the value exceeds the threshold, I manipulate an instance variable of a certain object.

Example:

Random random = new Random();
float[] x = new float[12000];

for (int i = 0; i < x.length; i++) {
  x[i] = random.nextFloat();
}

for (int i = 0; i < x.length; i++) {
  if (x[i] >= 0.75) {
  \\ do something interesting
  }
}

Basically, I have to change the values of the array and do this 12000 times on a new array each time of length 12000. The "something interesting" code is merely looking up that index in another data structure and calling a setter. From my System time calculations, it should take me about 13 hours. I have 8 processors on my machine.

How can I take advantage of java's multi-threading capabilities? I am specifically looking for thread solutions that partition up the initializing and scanning of the arrays. Source code using threads would be appreciated.

Brian
  • 7,098
  • 15
  • 56
  • 73
  • Do you have no experience at all with threads in Java? Have you ever used a Runnable or done anything with the Thread class? Curious as to your starting knowledge here. – Kon Jul 11 '13 at 03:24
  • 4
    13 hours? That something interesting method must be pretty interesting. – William Morrison Jul 11 '13 at 03:25
  • what do you mean by "do this 12000 times on a new array each time". How many iterations of 12000 you are taking. – veritas Jul 11 '13 at 03:27
  • I am curious of what @veritas asked too. Are you worried about time spent iterating or time spent doing something interesting? – William Morrison Jul 11 '13 at 03:28
  • 1
    The answer could vary quite a lot depending on the nature of "do something interesting". Can each thread, "do something interesting" for a subset of the array, without worrying about the other threads, or other parts of the array, or about its part of the array changing? – Keith Jul 11 '13 at 03:33
  • Improvements in algorithms are likely to yield a greater speed up than using threads, but since we don't know what problem you are trying to solve, we can't suggest them. – meriton Jul 11 '13 at 04:56
  • Do you need to keep the original values in x[]? If not, you don't even need x[], and you only need one loop. Pass the value of 'i' to the 'something interesting' function, let the function generate the random number, return if the condition is not met, else do the rest before returning. – Marichyasana Jul 11 '13 at 05:04
  • check [this](http://www.codeproject.com/Articles/616115/Java-Thread-Example#ai). –  Jul 11 '13 at 06:55

1 Answers1

8

You can divide this up among eight different threads doing something like this

public class Worker implements Runnable {
    final private int minIndex; // first index, inclusive
    final private int maxIndex; // last index, exclusive
    final private float[] data;

    public Worker(int minIndex, int maxIndex, float[] data) {
        this.minIndex = minIndex;
        this.maxIndex = maxIndex;
        this.data = data;
    }

    public void run() {
        for(int i = minIndex; i < maxIndex; i++) {
            if(data[i] >= 0.75) {
                // do something interesting
            }
        }
    }
}


// *** Main Thread ***
float[] data = new float[12000];
int increment = data.length / 8;
for(int i = 0; i < 8; i++) {
    new Thread(new Worker(i * increment, (i + 1) * increment, data)).start();
}

This divides up the array among the 8 different threads. Or, another option is this:

public class Worker implements Runnable {
    final private BlockingQueue<Integer> queue;
    final private float[] data;

    public Worker(BlockingQueue<Integer> queue) {
        this.queue = queue;
        this.data = data;
    }

    public void run() {
        while(true) {
            int i = queue.take();
            float f = data[i];
            // do something interesting to f
        }
    }
}


// *** Main Thread ***
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>();
float[] data = new float[12000];
for(int i = 0; i < 8; i++) {
    new Thread(new Worker(queue, data)).start();
}
for(int i = 0; i < data.length; i++) {
    if (data[i] >= 0.75) {
        queue.offer(i);
    }
}

This uses one thread to iterate through the array and find the interesting numbers, and then uses eight worker threads to do something interesting to the interesting numbers. I'd tend to prefer this approach, as it's possible with the first approach that one worker thread would wind up having to process a thousand interesting numbers while another worker thread only needs to process a few interesting numbers; this approach ensures that each thread needs to process approximately the same quantity of interesting numbers.

I'm omitting a lot of stuff, like how to use Executors and how to shut down your worker threads etc - here's a tutorial on that.

Edit To take your code and run it 12000 times on 8 threads, you would do the following:

public class Worker implements Runnable {
    private final int numberOfIterations;
    private final float[] x = new float[12000];

    public Worker(int numberOfIterations) {
        this.numberOfIterations = numberOfIterations;
    }

    public void run() {
        for(int i = 0; i < numberOfIterations; i++) {
            Random random = new Random();

            for (int i = 0; i < x.length; i++) {
                x[i] = random.nextFloat();
            }

            for (int i = 0; i < x.length; i++) {
                if (x[i] >= 0.75) {
                    \\ do something interesting
                }
            }
        }
    }
}


// *** Main Thread ***
Thread[] threads = new Thread[8];
for(int i = 0; i < 8; i++) {
    threads[i] = new Thread(new Worker(12000/8));
    threads[i].start();
}
for(int i = 0; i < 8; i++) {
    threads[i].join();
}

Each of the eight threads will run 1500 iterations of the "initialize float array, iterate through float array" code. The join method will then wait for the threads to finish. Be certain that the code in // do something interesting is thread-safe - you said that you're calling a setter, so be certain that multiple threads won't be calling the same setter, or else that the setter is synchronized, or else that you're using something like an AtomicInteger in the setter. Post the setter code if you have any doubts about it.

Community
  • 1
  • 1
Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69
  • In the second approach the workers don't have access to the original index of each float-- probably necessary information in many applications. – Keith Jul 11 '13 at 03:49
  • @Keith Good point, I've edited my answer accordingly – Zim-Zam O'Pootertoot Jul 11 '13 at 03:52
  • @Zim-Zam Thanks you. I suspect this will work great. However, the more expensive computation is initializing 12,000 different arrays and scanning them each time. The "something interesting" part was just looking up that index in another data structure and calling a setter. Can you change your answer where the threads partition the 12,000 created arrays instead of the 8 something interestings? – Brian Jul 11 '13 at 03:57
  • @Brian Vanover See the edit to my answer, and note my caution about the thread-safety of your code in `// do something interesting` – Zim-Zam O'Pootertoot Jul 11 '13 at 04:10