@dmitriyivvvv

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

Добрый день! Решаю задачи на 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 и все числа в массиве будут уникальными, то придется перебрать весь массив, что не эффективно и очень долго.
Я не прошу решать задачу за меня, просто подскажите в каком направлении копать.
  • Вопрос задан
  • 559 просмотров
Решения вопроса 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
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
byte916
@byte916
Вот это
for (var i = 0; i < ints.length; i++) {
      if (i <= ind) continue;

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

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

После нахождения первой пары нужно проверить все пары до второго числа пары. После нахождения каждой следующей пары у которой индекс второго числа меньше, нужно смещать верхнюю границу поиска. Так вы избавитесь от массива куда засовываете результат. и значительно увеличите скорость работы.
Ответ написан
Ni55aN
@Ni55aN
Алгоритм следующий: для каждого элемента массива вычислять сумму с каждым из предыдущих элементов до тех пор, пока сумма не будет равна указанной. Таким образом ответ будет получен ранее, чем за 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, она же функция из вопроса, мутируем массив, что нехорошо
Ответ написан
@ar5
Можно сделать одним проходом. Взять сумму и вычитать по циклу каждое число и через indexOf проверять есть ли этот остаток в массиве. И запоминать если он меньше предыдущего. И у вас получится за один проход проверить все комбинации.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы