有没有一种有效的双循环方式? [英] Can there be an efficient way for the dual loops?

问题描述

我在考试中遇到一个问题，给我一个数组 a

I got a question in exam where I was given an array a

a = [9,8,10,2]

我需要做的是交叉迭代数组本身，并获取所有可能元素的串联，即 a * a

what I need to do is cross iterate the array on itself and get the concatenation of all the possible elements i.e a*a

一旦所有元素都按该顺序串联起来，那么我需要对它们进行总结.我的代码在代码段中:

Once all elements are concatenated in that order, then I need to sum them up. My code is in the snippet:

也在PHP中尝试过

function sumIt($a) {
  $totalSum = 0;
  $len1 = count($a);
  for($i = 0; $i < $len1; $i++){
    for($ii = 0; $ii < $len1; $ii++) {
      $totalSum += $a[$i].''.$a[$ii];
    }
  }
  return $totalSum;
}

输入数组 a 可以具有以下值约束:

The input array a can have the following value constraints:

1. 数组的最大长度为10 ^ 5
2. 单个项目的值不能超过10 ^ 6

我的代码在大多数情况下都能正常工作，但是在数组 a 的更高端值上，我开始花费的时间超过了 MAX 4秒的错误.我尝试了 while & foreach 循环无效.由于代码非常简单，我想知道是否有人可以提供有关提高性能和减少执行时间的提示.

My code works fine mostly, but on higher end values for array a I start getting time exceed errors which is MAX 4 seconds. I tried with while & foreach loops with no effect. As the code is quite simple, I was wondering if anyone can provide hints on increasing the performance and reducing the execution time.

PS:如果有人知道，我也在for循环中尝试了--i东西，在这方面也没有区别.

PS: I tried the --i thing in for loop as well if anyone knows, no difference in that regard as well.

a = [10, 23, 4857, 3, 49, 293, 1, 394,85, 392, 484, 392, 30, 4849,48, 20, 3948, 2493, 84, 3492, 384,92, 384,38, 49, 45, 489, 53,40,9875, 84,9,572,3958, 346,456,45, 56,4564, 6,7867,8, 78,9789, 234,234, 435,34,6, 45,345, 4564,5, 657,45, 45, 345, 667, 5,6756, 877,68, 6765,4, 34, 6, 54, 3, 654, 6, 5, 8776, 43, 32, 67, 89, 876,543,2,34,5, 654, 35, 6, 4, 345, 678, 9, 8, 765, 467,878,9, 4352, 5, 6743, 4, 47, 57,65, 345, 78, 765, 645,63, 56, 5786, 676, 4564,5, 42, 46, 786, 97, 896,567,86, 3777, 65, 6, 877, 65, 67, 2039757584,5348];

function sumIt(a) {
  totalSum = 0;
  const len1 = a.length;
  for(let i = 0; i < len1; i++){
    for(let ii = 0; ii < len1; ii++) {
      totalSum += +(a[i]+''+a[ii]);
    }
  }
  return totalSum;
}

currentTime = new Date().getTime();
console.log(sumIt(a));
console.log(new Date().getTime() - currentTime);


function sumIt2(a) {
  totalSum = 0;
  const len1 = a.length;
  for(let i = 0; i < len1; i++){
    first = Math.pow(10, Math.ceil(Math.log(a[i] + 1)));
    for(let j = 0; j < len1; j++) {
     totalSum += (first + a[j])
    }
  }
  return totalSum;
}

currentTime = new Date().getTime();
console.log(sumIt2(a));
console.log(new Date().getTime() - currentTime);

推荐答案

以下算法(基于@ user3386109的思想)更加快捷:

The following algorithm (based on @user3386109's idea) is way quicker:

// Generate random array
let a = [];

for (let i = 0; i < 100; i++) {
  a.push(Math.floor(Math.random() * 1e6));
}

function sumIt(a) {
  totalSum = 0;
  const len1 = a.length;
  for(let i = 0; i < len1; i++){
    for(let ii = 0; ii < len1; ii++) {
      totalSum += +(a[i]+''+a[ii]);
    }
  }
  return totalSum;
}

function sumIt2(a) {
  let total = 0;
  let aLen = a.length;
  
  for (let i = 0; i < aLen; i++) {
    for (let j = 0; j < aLen; j++) {
        var subtotal = a[i] * Math.pow(10, Math.ceil(Math.log10(a[j] + 1))) + a[j];
        total += subtotal;
    }
  }
  
  return total;
}

function sumIt3(a) {
  let subtotal    = 0;
  let multiplier  = 0;
  let digitCounts = [a.length, 0, 0, 0, 0, 0, 0];
  
  for (let i = 0; i < a.length; i++) {
    subtotal += a[i];
    digitCounts[Math.ceil(Math.log10(a[i] + 1))]++;
  }
  
  for (let i = 0; i < digitCounts.length; i++) {
    multiplier += Math.pow(10, i) * digitCounts[i];
  }
  
  return subtotal * multiplier;
}

console.clear();

performance.mark("start");
console.log(sumIt(a));
performance.mark("sumIt");
console.log(sumIt2(a));
performance.mark("sumIt2");
console.log(sumIt3(a));
performance.mark("sumIt3");

performance.measure("sumIt",  "start",  "sumIt");
performance.measure("sumIt2", "sumIt",  "sumIt2");
performance.measure("sumIt3", "sumIt2", "sumIt3");

console.log(performance.getEntriesByType("measure").map(p => p.duration));

但是，对于更大的阵列大小(大约140以上)，结果开始出现分歧.我认为这更多是与JS的 Number 类型的精度有关，而不是算法中的潜在问题.

However, with larger array sizes (above about 140), the results start to diverge. I think that is more to do with the precision of JS's Number type rather than an underlying problem in the algorithm.

这篇关于有没有一种有效的双循环方式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！