CODEWITHSUNDEEP
javaalgorithmlambdajava-streamarray-difference
Sarah
Sarah

Reputation: 88

Faster way to get the numerical difference between 2 byte[] arrays?

I'm working on a program where I have 2 byte arrays and need to calculate the difference between them. For example, if the first array was {1, 2, 3}, and the second array {2, 3, 4}, the difference would be 3.

My current method to do this looks like this:

public long calculateDifference(byte[] a, byte[] b) {
  long difference = 0;
  for(int i = 0; i < a.length; i++) {
    difference += Math.abs(a[i] - b[i]);
  }
  return difference;
}

However, the program will need to be able to process byte arrays that have up to around 5,000,000 elements, so using the current method would be too slow.

Because I have 16 threads, I've seen parallel streams as an option. But because there's no ByteStream, using the reduce and collect operations wouldn't be possible without unboxing and boxing.

Another option would be to use IntStream.range(0, byteArrayLength) to create a parallel stream and the access the index using the int. However, to do this a LongAdder or AtomicLong would be necessary, both of which are much slower in my benchmarks. (LongAdder seems to use an array internally then sum it up at the end)

Is there a more efficient way to achieve this? I don't mind adding external dependencies. Thanks!

Upvotes: 0

Views: 239

Answers (1)

Joni
Joni

Reputation: 111349

One thing you can try is divide the data into two or more regions that are each processed in separate threads. It may make enough of a difference for arrays of a billion items to make it worth it, but for as few as 5 million, probably not.

What follows is a very crude proof-of-concept you can use to evaluate if the idea has any merit at all.

Make a method that does the computation for a region:

public long calculateDifference(byte[] a, byte[] b, int start, int end) {
    long difference = 0;
    for(int i = start; i < end; i++) {
        difference += Math.abs(a[i] - b[i]);
    }
    return difference;
}

And call this method from several threads, and combine the results:

ExecutorService threadPool = Executors.newFixedThreadPool(2);

public long calculateDifference(byte[] a, byte[] b) throws Exception {
    Future<Long> diff1 = threadPool.submit(() -> calculateDifference2(a, b, 0, a.length / 2));
    Future<Long> diff2 = threadPool.submit(() -> calculateDifference2(a, b, a.length / 2, a.length));
    return diff1.get() + diff2.get();
}

Upvotes: 2

Related Questions