How to add 100,000 int values more efficiently.
Today I was sorting out the interview questions and saw this question that had been asked before.
Thinking to no avail
Welcome everyone to discuss!
I tried it yesterday based on fonxian’s answer and found that there was no difference! Something wrong with my implementation?
The algorithm using threads may be slower because threads require additional overhead.
Ignore those who use map. The map version has been changed many times but still cannot achieve the desired effect. It seems that map is very expensive.
There is no difference between separate calculation and combined calculation. The benefits of separate calculation are not obvious at all~~~~
2017-5-10
Thanks to thomastao for the reminder, I have rearranged the method, and it can be seen that there is a clue. My level is limited so I won’t summarize it. Just take a look!
public static void main(String[] args) {
IntSumTest t = new IntSumTest(10000000);
Long startDate1 = new Date().getTime();
//方法注释后的数值为执行时间(毫秒)
//先用map去重,然后相乘。最后将结果相加
t.mapCount(); //7255 8251 8002 7355
//开启多个线程相加,结果记录到sum数组中。最后将sum数组相加。
// t.threadCount(); //5 5 4 4 5 4 5 4 4 4
//一个线程相加分10次相加,结果记录到sum数组中。最后将sum数组相加。
// t.reduceCount(); //4 2 3 3 3 3 4 3 2 3
//直接相加
// t.count(); //11 10 10 10 10 10 12 13 11 11
//使用计数方法
// t.countSum(); //14 15 14 16 12 13 11 12 12 13
Long endDate1 = new Date().getTime();
System.out.println(endDate1- startDate1 );
}
public class IntSumTest {
int[] valueNum = new int[10000000];//1000w个数
public IntSumTest(int maxNum){
Random r = new Random();
for(int i=0;i<valueNum.length;i++){
valueNum[i] = r.nextInt(maxNum);
}
}
/**
* 直接计算
* @return
*/
public long count(){
long sum = 0;
for(int i=0;i<valueNum.length;i++){
sum+= valueNum[i];
}
return sum;
}
/**
* 使用计数方法计算
* 理论上的好处在于java栈内的管理方式是所有成员变量都会记录
* @return
*/
public long countSum(){
long sum = 0;
for(int i=0;i<valueNum.length;i++){
sum = sum( sum,valueNum[i]);
}
return sum;
}
public long sum(long sum ,int num){
return sum+num;
}
/**
* 使用数组计数,然后在各个数字相乘,得到结果
* 该方法的好处在于可以释放大量对象
* 缺点在于,如果数字的分布范围太大,效果就不明显
*/
public long mapCount(){
long sum = 0;
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<valueNum.length;i++){
map.put(valueNum[i],map.get(valueNum[i])==null?0:map.get(valueNum[i])+1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
sum+= entry.getKey()*entry.getValue();
}
return sum;
}
/**
* 多线程计算,分10组计算,分别汇总结果
*/
public long threadCount(){
long sum = 0;
long[] sumNum = new long[10];
for (int i = 0; i < 10; i++) {
MyThread my = new MyThread(sumNum,valueNum,i);
my.run();
}
for (int i = 0; i < 10; i++) {
sum += sumNum[i];
}
return sum;
}
/**
* 分10组计算,分别汇总结果
*/
public long reduceCount(){
long sum = 0;
long[] sumNum = new long[10];
for (int i = 0; i < 10; i++) {
int temp = i*10000;
long max = temp+10000;
for (int j = temp; j < max; j++) {
sumNum[i]+= valueNum[j];
}
}
for (int i = 0; i < 10; i++) {
sum += sumNum[i];
}
return sum;
}
}
Use MapReduce ideas or multi-threading to solve it. Map 10w integers into n groups (for example, 10 groups). Each group only needs to calculate the sum of 1w numbers, then reduce and add 10 sums.
Generally speaking, first check with the naked eye whether there are any patterns. If there are patterns, use the formula to calculate. If there are no patterns, just add them one by one. . .