Wie kann man 100.000 int-Werte effizienter hinzufügen?
Ich habe heute Interviewfragen gesammelt und diese Frage gesehen, die zuvor gestellt wurde.
Vergebliches Nachdenken
Jeder ist herzlich eingeladen, darüber zu diskutieren!
Ich habe es gestern anhand der Antwort von Fonxian ausprobiert und festgestellt, dass es keinen Unterschied gibt! Stimmt etwas mit meiner Implementierung nicht?
Der Algorithmus, der Threads verwendet, ist möglicherweise langsamer, da Threads zusätzlichen Overhead erfordern.
Für diejenigen, die eine Karte verwenden, ignorieren Sie sie einfach. Die Kartenversion wurde viele Male geändert, kann aber immer noch nicht den gewünschten Effekt erzielen. Es scheint, dass die Karte sehr teuer ist.
Es gibt keinen Unterschied zwischen getrennter Berechnung und kombinierter Berechnung. Die Vorteile der getrennten Berechnung liegen überhaupt nicht auf der Hand.~~~~
2017-5-10
Danke an thomastao für die Erinnerung, ich habe die Methode neu geordnet und es ist ersichtlich, dass es einen Hinweis gibt. Mein Niveau ist begrenzt, daher werde ich es nicht zusammenfassen. Mal schauen!
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;
}
}
用MapReduce的思想或者多线程解决。10w个整数map成n组（例如10组），每组只需要计算1w的数的sum，然后reduce归约，10个sum相加。
一般来说先肉眼看有没有规律，有规律了用公式算，没规律了就老老实实的一个一个加吧。。。