Как оптимизировать этот JS код?

Question

[dmitriyivvvv]

Добрый день! Решаю задачи на JS на одном сайте и попалась мне такая задачка:
Дается массив целых чисел (первый параметр) и сумма (второй параметр).
Пример: sum_pairs([11, 3, 7, 5], 10);
Необходимо найти в массиве два числа сумма которых равна 10 в данном случае(второму параметру).
Если таких пар несколько, то возвращается та пара у которой индекс второго числа меньше, например:
Слева на право.

sum_pairs([10, 5, 2, 3, 7, 5], 10)
#              ^-----------^   5 + 5 = 10, индексы: 1, 5
#                    ^--^      3 + 7 = 10, индексы: 3, 4 *
#  * пара находится раньше в массиве, и поэтому это правильный ответ
=> [3, 7]

У меня получилось следующее:

var sum_pairs=function(ints, s){
  var arr = [];
  ints.forEach(function(curr, ind) {
    for (var i = 0; i < ints.length; i++) {
      if (i <= ind) continue;
      if (curr + ints[i] == s) {
        arr.push([curr, ints[i], i]);
        ints.splice(i);
      }
    }
  });
  arr.sort((a, b) => a[2] - b[2]);
  return arr.length == 0 ? undefined : arr[0].slice(0, 2);
}

Так же в массиве могут быть одинаковые числа и отрицательные числа, если такой суммы в массиве не найдено, то возвращается undefined, а если найдена то возвращается эта пара чисел, например [3, 7];
Все работает, но проблема в том, что в задании будут массивы длиной до 10,000,000, и в моем случае если сумма(второй параметр) будет например 19999997 и все числа в массиве будут уникальными, то придется перебрать весь массив, что не эффективно и очень долго.
Я не прошу решать задачу за меня, просто подскажите в каком направлении копать.

Comments

[Vitaliy]

Я не прошу решать задачу за меня, просто подскажите в каком направлении копать.

Вам уже прокопали направление, делайте вывод на основании того, что было и что получилось

Answer 1

[dmitriyivvvv]

Вообщем после дня мучений я сдался и посмотрел ответ:

var sum_pairs=function(ints, s){
  var seen = {}
  for (var i = 0; i < ints.length; ++i) {
    if (seen[s - ints[i]]) return [s - ints[i], ints[i]];
    seen[ints[i]] = true
  }
}

Мы наполняем объект числами и каждый раз проверяем есть ли в объекте нужный нам остаток от суммы минус текущее число в массиве. Работает гораздо быстрее чем n2

Answer 2

[Андрей]

Вот это

for (var i = 0; i < ints.length; i++) {
      if (i <= ind) continue;

Следует записать так
for (var i = ind+1; i < ints.length; i++) {
Этим вы сразу уберете миллионы итераций на больших массивах

Если таких пар несколько, то возвращается та пара у которой индекс второго числа меньше

После нахождения первой пары нужно проверить все пары до второго числа пары. После нахождения каждой следующей пары у которой индекс второго числа меньше, нужно смещать верхнюю границу поиска. Так вы избавитесь от массива куда засовываете результат. и значительно увеличите скорость работы.

Comments

[dmitriyivvvv]

Спасибо за for (var i = ind+1; i < ints.length; i++)
Насчет

После нахождения первой пары нужно проверить все пары до второго числа пары. После нахождения каждой следующей пары у которой индекс второго числа меньше, нужно смещать верхнюю границу поиска. Так вы избавитесь от массива куда засовываете результат. и значительно увеличите скорость работы.

У меня есть ints.splice(i); который обрезает исходный массив сразу после того, как была найдена первая пара(или более короткая), потому как нет смысла искать пару дальше чем индекс второго числа первой пары, т.к. она будет "позже" первой найденной.

[dmitriyivvvv]

Даже несмотря на эти изменения, код не успевает выполняться за 12 секунд (это макс время до Timed Out). Видимо проблема в самом алгоритме поиска суммы, надо придумать что-то другое.

[Андрей]

dmitriyivvvv, обрезание массива работает медленнее чем хранение границы массива в переменной.
arr.push([curr, ints[i], i]);
Пуш данных в массив работает значительно медленнее, чем хранение индексов в массиве.
Массив результатов вам не нужен, сортировка соответственно тоже

[Вася]

Андрей, даже если фокус сплайс работает чтоб прервать два цикла, явный бряк был бы нагляднее.

[dmitriyivvvv]

Вообщем получилось следующее, работает заметно быстрее, но все равно очень медленно с большими массивами:

var sum_pairs=function(ints, s){
  var arr = [];
  var end = ints.length;
  ints.forEach(function(curr, ind) {
    for (var i = ind + 1; i < end; i++) {
      if (curr + ints[i] == s) {
        arr[0] = [curr, ints[i]];
        end = i;
      }
    }
  });
  return arr[0];
}

[Андрей]

dmitriyivvvv, замените foreach на for, и так же используйте верхнюю границу массива в нём. Так вы уменьшите число итераций, в некоторых случаях - значительно

[Андрей]

Замена
arr[0] = [curr, ints[i]];
на

x = curr;
y = ints[i];

уменьшит затраты на эту строчку на 70%;

[dmitriyivvvv]

Андрей,

var sum_pairs=function(ints, s){
  var x, y;
  var end = ints.length;
  for (var j = 0; j < end; j++) {
    for (var i = j + 1; i < end; i++) {
      if (ints[j] + ints[i] == s) {
        x = ints[j];
        y = ints[i];
        end = i;
      }
    }
  }
  return x == undefined ? x : [x, y];
}

Спасибо за помощь, но даже с массивом в 100,000 элементов выполнение занимает ~ 15сек не говоря уже о 10 миллионах которые требуются :( Дело в самом алгоритме поиска суммы, надо думать в другом направлении

[Андрей]

dmitriyivvvv, каким образом вы измеряете? У меня на 10 миллионах случайных чисел получается 1мс

https://jsfiddle.net/3sgm6510/14/

[dmitriyivvvv]

Андрей, вы попробуйте так

var a = [];
for (var i = 0; i < 10000000; i++) {
  a.push[i];
}
sum_pairs(a, 20000000)

[Андрей]

dmitriyivvvv, вот еще пара идей:
1. Лишний раз не делать в цикле

x = ints[j];
        y = ints[i];

заменить на

x = j;
y = i;

Получать элементы по этим индексам в момент return

2. Не складывать в цикле
if (ints[j] + ints[i] == s) {
Вместо этого заранее просчитать подходящее число и сравнивать с ним

for (var j = 0; j < end; j++) {
    var t = s - ints[j];
    ...
    if (t = ints[i]) {

[Андрей]

dmitriyivvvv, с этими правками у меня теперь работает за 1мс на массиве размером в 10 миллионов при полном переборе массива

[dmitriyivvvv]

Андрей, Можете показать ваш результат? Только что попробовал с правками, стало быстрее но ни о какой 1мс не идет и речи, мб я что-то не так сделал.

[dmitriyivvvv]

Андрей, мб из-за того, что у вас ошибка здесь var t = s - ints[j];, присваивание вместо сравнения)
Вот мой код:

var sum_pairs=function(ints, s){
  var x, y;
  var end = ints.length;
  for (var i = 0; i < end; i++) {
    var z = s - ints[i];
    for (var j = i + 1; j < end; j++) {
      if (z == ints[j]) {
        x = i;
        y = j;
        end = j;
      }
    }
  }
  return x == undefined ? x : [ints[x], ints[y]];
}

[Андрей]

dmitriyivvvv, ошибка не здесь, но она была. За миллисекунду не считает, но быстрее чем было

Answer 3

[Vitaliy]

Алгоритм следующий: для каждого элемента массива вычислять сумму с каждым из предыдущих элементов до тех пор, пока сумма не будет равна указанной. Таким образом ответ будет получен ранее, чем за NxN, так как нужно получить только первую пару (зависит от того, как близко к началу расположены эти элементы)

function sum_pairs(arr, sum){
 for(var i=1; i<arr.length;i++){
   for(var n=0;n<i;n++){
		if(arr[n]+arr[i]===sum) return [arr[n], arr[i]];
    }
 }
}

Тест быстродействия:

var a = [...new Array(10000).fill(0).map(_ => Math.round(Math.random()*8)), 14, 16];
var a1 = a.slice();
var a2 = a.slice();

console.time('1');
console.log(sum_pairs1(a1,30))
console.timeEnd('1');

console.time('2');
console.log(sum_pairs2(a2,30))
console.timeEnd('2');

В моем случае результаты следующие:
функция из вопроса отработала за 350 мс
функция из текущего ответа - 110 мс

К тому же, было специально добавлено два числа в конец массива и сумму равную 30, чтобы sum_pairs2 проделал максимально возможное количество итераций. И еще, sum_pairs1, она же функция из вопроса, мутируем массив, что нехорошо

Comments

[Андрей]

Идея очень интересная, но реализация очень медленная.

[Vitaliy]

Андрей, то есть? Есть варианты более быстрой реализации? Разве что на С++, но не на JS

[Андрей]

Виталий Столяров,

var sum_pairs=function(ints, s){
console.time('mark')
  var x, y;
  var end = ints.length;
  for (var j = 0; j < end; j++) {
  var t = s - ints[j]; 
  
    for (var i = j + 1; i < end; i++) {
      if (t == ints[i]) {
        x = j;
        y = i;
        end = i;
      }
    }
  }
	console.timeEnd('mark') 
  return x == undefined ? x : [ints[x], ints[y]];
}

На тех данных, на которых вы тестировали получается в несколько раз быстрее

[Vitaliy]

Андрей, где это у вас так получается? Проверил на

var a = [...new Array(50000).fill(0).map(_ => Math.round(Math.random()*8)), 14, 16];

Результаты:
4790.5478515625ms - моя реализация
8015.795166015625ms - ваша

[Vitaliy]

function sum_pairs1(arr, sum){
 for(var i=1; i<arr.length;i++){
   for(var n=0;n<i;n++){
    if(arr[n]+arr[i]===sum) return [arr[n], arr[i]];
    }
 }
}

var sum_pairs2=function(ints, s){
  var x, y;
  var end = ints.length;
  for (var j = 0; j < end; j++) {
  var t = s - ints[j]; 
  
    for (var i = j + 1; i < end; i++) {
      if (t == ints[i]) {
        x = j;
        y = i;
        end = i;
      }
    }
  }
  return x == undefined ? x : [ints[x], ints[y]];
}

var a = [...new Array(50000).fill(0).map(_ => Math.round(Math.random()*8)), 14, 16];
var a1 = a.slice();
var a2 = a.slice();

console.time('1');
console.log(sum_pairs1(a1,30))
console.timeEnd('1');

console.time('2');
console.log(sum_pairs2(a2,30))
console.timeEnd('2');

[Андрей]

Виталий Столяров, у меня получаются данные ровно наоборот
https://jsfiddle.net/mzbv0k14/1/

[dmitriyivvvv]

Виталий Столяров, попробуйте так

var a = [];
for (var i = 0; i < 10000000; i++) {
  a.push[i];
}
sum_pairs(a, 20000000)

[Vitaliy]

Андрей, в каком браузере запускали и на каком железе?

[Андрей]

Виталий Столяров, Firefox, I7-7700

[Vitaliy]

[dmitriyivvvv]

Все равно, не успевает, я так понял есть решение с одним циклом, на форуме того сайта подсказали, буду думать.

f you have two nested while loops, your solution will time out. This kata is a test of your ability to optimize the problem into a single loop.

[Андрей]

Виталий Столяров, а у вас то какое железо?

[Vitaliy]

Андрей, i5-5200U, WebKit последний

[Vitaliy]

В Firebox следущюие результаты:
1186.6мс
против
967.27м

Answer 4

[ar5]

Можно сделать одним проходом. Взять сумму и вычитать по циклу каждое число и через indexOf проверять есть ли этот остаток в массиве. И запоминать если он меньше предыдущего. И у вас получится за один проход проверить все комбинации.

Comments

[Андрей]

Вы думаете, что indexOf это не перебор массива?)

[ar5]

Андрей, конечно перебор, просто более простой, т.к. это браузерная реализация без необходимости городить сложность n2