Comment ajouter 100 000 valeurs int plus efficacement ?
Je collectais des questions d'entretien aujourd'hui et j'ai vu cette question qui avait été posée auparavant.
Réfléchir en vain
Tout le monde est invité à discuter !
Je l'ai essayé hier sur la base de la réponse de fonxian et j'ai constaté qu'il n'y avait aucune différence ! Quelque chose ne va pas avec ma mise en œuvre ?
L'algorithme utilisant les threads peut être plus lent car les threads nécessitent une surcharge supplémentaire.
Si vous utilisez la carte, ignorez-la. La version de la carte a été modifiée plusieurs fois mais ne parvient toujours pas à obtenir l'effet souhaité. Il semble que la carte soit très chère.
Il n'y a aucune différence entre le calcul séparé et le calcul combiné. Les avantages du calcul séparé ne sont pas du tout évidents~~~~
2017-5-10
Merci à thomastao pour le rappel, j'ai réorganisé la méthode, et on voit qu'il y a un indice. Mon niveau est limité donc je ne vais pas le résumer. Jette un coup d'oeil!
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;
}
}
Utilisez les idées MapReduce ou le multithread pour le résoudre. Mappez 10w entiers en n groupes (par exemple, 10 groupes). Chaque groupe n'a besoin que de calculer la somme de 1w nombres, puis de réduire et d'ajouter 10 sommes.
De manière générale, vérifiez d'abord à l'œil nu s'il y a des modèles. S'il y a des modèles, utilisez la formule pour calculer. S'il n'y a pas de modèles, ajoutez-les simplement un par un. . .