[Java Code Snippet] The least amount of differences between two integer arrays of same size.

[tom_mai78101]

package main;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
 
public class Test {
   
    public static void main(String[] arg) {
        Random random = new Random();
        ArrayList<Integer> list1 = new ArrayList<Integer>();
       
        int temp;
        int listSize = random.nextInt(100);
        if (listSize % 2 != 0)
            listSize++;
       
        System.out.print("串列: ");
        for (int i = 0; i < listSize; i++) {
            temp = random.nextInt(10);
            if (temp < 0)
                temp *= -1;
            list1.add(temp);
            System.out.print(temp + " ");
        }
        System.out.println();
       
        Collections.sort(list1, new Comparator<Integer>() {
           
            @Override
            public int compare(Integer a, Integer b) {
                if (a > b)
                    return 1;
                if (a < b)
                    return -1;
                return 0;
            }
           
        });
       
        System.out.print("串列小到大: ");
        for (int i : list1) {
            System.out.print(i + " ");
        }
        System.out.println();
       
        int size = list1.size() / 2;
        ArrayList<Integer> sub1 = new ArrayList<Integer>();
        ArrayList<Integer> sub2 = new ArrayList<Integer>();
       
        int head = 0;
        int tail = list1.size() - 1;
        boolean flag = true;
       
        for (int i = 0; i < size; i++) {
            if (flag) {
                sub1.add(list1.get(head));
                sub1.add(list1.get(tail));
            }
            else {
                sub2.add(list1.get(head));
                sub2.add(list1.get(tail));
            }
            head++;
            tail--;
            flag = !flag;
        }
       
        int sum1 = 0;
        int sum2 = 0;
       
        System.out.print("A 串列: ");
        for (int i : sub1) {
            sum1 += i;
            System.out.print(i + " ");
        }
        System.out.println();
       
        System.out.print("B 串列: ");
        for (int i : sub2) {
            sum2 += i;
            System.out.print(i + " ");
        }
        System.out.println();
       
        System.out.println("A 串列: " + sum1 + "      B 串列: " + sum2);
        System.out.println("互減: " + (sum1 - sum2));
    }
}

 

[Accname]

Is there any kind of question?
By the way, the (i guess) chinese letters make it kinda hard to read, lol.

 

[tom_mai78101]

Is there any kind of question?
By the way, the (i guess) chinese letters make it kinda hard to read, lol.

This code snippet was recycled from Facebook, where our class group is doing a routine cleaning. Since we're graduated, our group is being moved/merged with a larger group where us graduated students with Bachelor's degrees are all in.

The question, translated, involves two integer arrays, Array A and Array B, of size N. N must be an even number. The elements of both arrays are randomized integers. Find an algorithm that shows the smallest difference of the sum of Array A's elements and the sum of Array B's elements. If the difference is positive, Array A's sum is larger. And vice versa.

For example:

Array A: 0, 1, 2, 3
Array B: -1, 0, 1, 2

Sum of Array A: 6
Sum of Array B: 2

The smallest difference between Array A and Array B is 4. Try to obtain the lowest absolute value for this answer. Put a positive sign if Array A is larger, and put a negative sign if Array B is larger.

 

[Accname]

"smallest" difference? I would say the difference is constant and nonambiguous.
Can you have like a "bigger" difference between 2 values?

 

[tom_mai78101]

"smallest" difference? I would say the difference is constant and nonambiguous.
Can you have like a "bigger" difference between 2 values?

Since both of the values are random, yes you can/may/might get it.

The point of the question is about creating an algorithm out from the results given. It didn't say how well your algorithm should be or anything else that may restrict it.

You can also try out the code snippet in Eclipse, after refactoring a few things, and just focus on the numbers.

 

[s3rius]

I have no clue what this is.

Do you actually have a question about this code? Or did you post it for others to use?

And anyway, a difference is always greater or equal to 0. If sum2 > sum1 then the difference is negative. So you have to call Math.abs(sum1 - sum2) to get a 100% correct value.

And the code is pretty confusing. Not only because of Chinese letters, but the code itself has some issues imo.

1) Don't call your variable 'size' when it's not holding the size of a container. Call it something like 'halfSize' in your case.

2)

for (int i = 0; i < size; i++) {
    if (flag) {
        ...
    }
    else {
        ...
    }
    flag = !flag;
}

I'd be careful with this, you might end up killing your CPU's branch prediction with the alternation of the if's condition. Why not use 2 loops?

 

[tom_mai78101]

Well, I suck at translating the question into English. And I forgot some of the contexts behind all of this.

Especially the meaning of "difference". I thought difference means "subtraction", and it sounded better...

I'd be careful with this, you might end up killing your CPU's branch prediction with the alternation of the if's condition. Why not use 2 loops?

This is interesting, I've never heard of this before. It causes damage??

 

[Siretu]

def arrdiff(a, b):
  return sum(a) - sum(b)

Do I win?

 

[s3rius]

This is interesting, I've never heard of this before. It causes damage??

It doesn't damage your hardware.

But it could slow down your program.

The CPU is very good in executing a lot of stuff in a row. But when you have branching (like an if-statement) the CPU can't know beforehand whether it needs to run the then-part of the else-part of the if-statement.
So the CPU has to evaluate the if-statement before it can continue running.

That is what can make if-statements very slow. To optimize that, CPUs can "remember" the result of if-statements.
If you have an if-statement that is 'true' most of the time, the CPU will optimize for that case. You have faster program execution in the 'true' case and slower executing in the 'false' case.
But your if-statement alternates between 'true' and 'false' all the time, which can cause the prediction to fail a lot.

 

[tom_mai78101]

I don't know how to revise the code around then.

How do you insert 2 elements into array A, then another 2 (different) elements into Array B, and repeat until all elements have been exhausted from a large array, without killing the branch prediction?

 

[s3rius]

If you only want 2 arrays with N random numbers, you can just do:

Random r = new Random();
ArrayList<Integer> sub1 = new ArrayList<>();
ArrayList<Integer> sub2 = new ArrayList<>();
 
int n = r.nextInt(50) * 2; //Multiplying by 2 is an easy way to only get even numbers.
 
for(int i=0; i<n; ++i){
    sub1.add( r.nextInt(10) );
    sub2.add( r.nextInt(10) );
}

Because I really don't get why you:
1) Create list1 and add integers to it
2) Sort list1
3) Add elements of list1 to sub1 and sub2
if you can just add random ints into sub1/sub2 immediately.

But if you have a reason why distribute the elements from list1 exactly why you did, this one should do the same:

int head = 0;
int tail = list1.size() - 1;
for (int i = 0; i < size; i++) {
    sub1.add(list1.get(head));
    sub1.add(list1.get(tail));
    head++;
    tail++;
    sub2.add(list1.get(head));
    sub2.add(list1.get(tail));
    head++;
    tail++;
}

But I still don't get why you sort the list, and then add the head and tail elements to other lists..

 

[tom_mai78101]

//Tails should be decrementing.
tail--;

But yeah, I didn't think straight when I was doing my job helping another classmate at 4AM... That completely blew my mind that I didn't think of this.

Wow...

 

[s3rius]

You can make the summing easier too:

int sum1=0;
int sum2=0;
for(int i=0; i<n; ++i){
    sum1 += sub1.get(i);
    sum2 += sub2.get(i);
}

Or, if you don't care about the invidual sums, you can get the total sum easily:

int sum=0;
for(int i=0; i<n; ++i){
    sum += sub1.get(i) - sub2.get(i);
}

 

[tom_mai78101]

The fact is that you need to find the algorithm that makes the sums of both Array A and Array B so that when subtracted, the result should be as close to 0 as possible, and that both arrays must have randomized integer elements, is enough for me.

 

[Accname]

Tom, I think what you mean is:
You are given a set of integer values;
find 2 subsets of the original set so that the sums of both subsets become equal (or as close to being equal then possible).
The partition problem if I remember correctly.

http://en.wikipedia.org/wiki/Partition_problem

The problem is NP complete.

 

[tom_mai78101]

Yes, I believed.