Блог

Главная - Вопросы по программированию - Может ли быть эффективный способ для двойных циклов?

Может ли быть эффективный способ для двойных циклов?

#javascript #php #arrays #algorithm #loops

#javascript #php #массивы #алгоритм #циклы

Вопрос:

Я получил вопрос на экзамене, где мне был предоставлен массив a 

 a = [9,8,10,2]

что мне нужно сделать, это выполнить перекрестную итерацию массива над самим собой и получить конкатенацию всех возможных элементов, т.е a*a

Как только все элементы будут объединены в таком порядке, мне нужно их суммировать. Мой код находится во фрагменте:

Также пробовал в 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 может иметь следующие ограничения на значения:

  1. Длина массива может быть не более 10 ^ 5
  2. Значение отдельного элемента может быть до 10 ^ 6

В основном мой код работает нормально, но при более высоких конечных значениях для массива a я начинаю получать ошибки превышения времени, которые составляют МАКСИМУМ 4 секунды. Я пробовал с while amp; foreach циклами без эффекта. Поскольку код довольно прост, мне было интересно, может ли кто-нибудь дать подсказки по увеличению производительности и сокращению времени выполнения.

PS: Я также пробовал использовать —i в цикле for, если кто-нибудь знает, никакой разницы в этом отношении.

 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);

Комментарии:

1. (a[i] '' a[ii]) очень неэффективно. Все, что связано со строками, всегда является дорогостоящей операцией. Попытайтесь придумать способ, которым вы можете сделать это без использования строк. Кроме того, ваш цикл O(n^2) у меня в голове, я не могу придумать, как это обойти. (Ваша проблема кажется фундаментальной O(n^2) , хотя и рада быть исправленной.)

2. Немного меньше операций: как только у вас есть i , и ii вы можете добавить оба i , ii и ii , i. .

3. @StackSlave вопрос, упомянутый в начале, задается массив, для которого необходимо, чтобы все его элементы были перекрестно объединены с самим собой, а затем добавлены математически

4. Обратите внимание, что каждое число в массиве будет находиться с правой стороны конкатенации и с левой стороны. Вклад правой стороны — это просто сумма массива. Вклад левой стороны немного сложнее. Для примера ответ таков 9 8 10 2 90 80 20 2*9 2*8 2*2 . Это O (N * d), где d — количество уникальных цифр в массиве.

5. @user3386109 теперь это интересное направление, в котором я хотел бы подробнее разобраться

Ответ №1:

Следующий алгоритм (основанный на идее @user3386109) намного быстрее:

 // 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 , а не с основной проблемой в алгоритме.