array puzzle load balance
What do you mean by "difference if end with every position" . I didn't understand. Can you pls explain
if end with the first position:because average value is 1,the sum should be 1*1=1.but in fact the sum is 0,so the difference is 0-1=-1;
if end with the second position:because average value is 1,the sum should be 1*2=2.but in fact the sum is 0,so the difference is 0-2=-2;
if end with the third position:because average value is 1,the sum should be 1*3=3.but in fact the sum is 10,so the difference is 10-3=7;
The first question about this problem in my mind is that each server should share load with left, right, or both? I come up with the average value and the sum of previous, so that this question is solved.
Then I want to simulate each second,but it's too complex to realize it.At the same time,a sudden inspiration is coming and I test it.
Consider an example 6 nodes => 0 0 0 A 0 0. Here A has at least 2 0’s on either side. Thus as long as these 0’s have not reached the max load per node, the load on A will continue to drop by 2 every second.
0 0 0 12 0 0
0 0 1 10 1 0 // A’s load size decreases by 2
0 1 1 8 1 1 // A’s load size decreases by 2
1 1 1 7 1 1 // A’s load size decreases by 1. From here A’s load size will decrease by 1 every second.
Thus to calculate the seconds to distribute load evenly will be
second per transfer * max load on each node * symmetrical number of 0’s on either side of A + second per transfer * max load on each node * (total number of nodes - (2*symmetrical number of 0’s + 1 ))
In the above case:
symmetrical 0’s on either side of A are 2.
Max load on each node = A/no of node = 12 / 6 = 2
total seconds = 2*2 + 2*1 = 6 sec
Example 2: 0 0 15 0 0
total seconds = 3*2 = 0 = 6 seconds
Example 3: 0 0 0 0 7 0 0
total seconds = 2*1 + 1*2 = 4 seconds
public class LoadBalancing {
public static void main(String[] args) {
int [] a = {0,0,0,12,0,0,0};
System.out.println(loadBalance(a, 3));
}
public static int loadBalance(int [] a, int x){
// x is the index of A (node which will initiate load balancing)
int len = a.length-1;
int mid = len/2;
int sym0=-1;
if (x == mid)
sym0 = mid;
else if (x < mid)
sym0 = x;
else
sym0 = len - x;
int nsym0 = len-sym0*2;
int maxNodeLoad = a[x]/len;
return maxNodeLoad * sym0 + nsym0 * maxNodeLoad;
}
}
Consider an example 6 nodes => 0 0 0 A 0 0. Here A has at least 2 0’s on either side. Thus as long as these 0’s have not reached the max load per node, the load on A will continue to drop by 2 every second.
0 0 0 12 0 0
0 0 1 10 1 0 // A’s load size decreases by 2
0 1 1 8 1 1 // A’s load size decreases by 2
1 1 1 7 1 1 // A’s load size decreases by 1. From here A’s load size will decrease by 1 every second.
Thus to calculate the seconds to distribute load evenly will be
second per transfer * max load on each node * symmetrical number of 0’s on either side of A + second per transfer * max load on each node * (total number of nodes - (2*symmetrical number of 0’s + 1 ))
In the above case:
symmetrical 0’s on either side of A are 2.
Max load on each node = A/no of node = 12 / 6 = 2
total seconds = 2*2 + 2*1 = 6 sec
Example 2: 0 0 15 0 0
total seconds = 3*2 = 0 = 6 seconds
Example 3: 0 0 0 0 7 0 0
total seconds = 2*1 + 1*2 = 4 seconds
public class LoadBalancing {
public static void main(String[] args) {
int [] a = {0,0,0,12,0,0,0};
System.out.println(loadBalance(a, 3));
}
public static int loadBalance(int [] a, int x){
// x is the index of A (node which will initiate load balancing)
int len = a.length-1;
int mid = len/2;
int sym0=-1;
if (x == mid)
sym0 = mid;
else if (x < mid)
sym0 = x;
else
sym0 = len - x;
int nsym0 = len-sym0*2;
int maxNodeLoad = a[x]/len;
return maxNodeLoad * sym0 + nsym0 * maxNodeLoad;
}
}
public class LoadBalancing {
public static void main(String[] args) {
int [] a = {0,0,0,12,0,0,0};
System.out.println(loadBalance(a));
}
public static int loadBalance(int [] a){
int avg = 0;
int sum = 0;
for (int i =0 ; i < a.length-1;;i++){
sum = sum + a[i];
}
avg = sum/a.length;
int maxDiff = 0;
sum = 0;
for(int j = 0 ; j< a.length;j++ ){
sum += a[j];
int diff = sum - ( avg * (j+1));
if(diff <0) diff = diff * (-1);
if(maxDiff < diff){maxDiff = diff}
}
return maxDiff;
}
}
firstly: calculate the average value to judge whether the result should be 0.
- wuyuliang8 February 23, 2014secondly: scan the array and calculate the difference if end with every position based on average value.
for example:0,0,10,0,0,0,0,0,0,0.the average value is 1,so the difference if end with every position is -1,-2,7,6,5,4,3,2,1,0.
finally: the result is the max absolute value of the difference.