Как повысить производительность js-кода?

Question

[Максим Ко]

Доброго времени суток, хабровчане!
Недавно начал заниматься на codewars и возникла проблема со скоростью выполнения кода.
Есть код:

function partsSums(ls) {
  ls.reverse();
  let a = 0;
  arr = [];
  let s = ls.length;
  for(let i = s; i--;){
    for(let j = ls.length; j--;){
      a += ls[j];
    }
    arr.push(a);
    ls.pop();
    a = 0;
  }
  arr.push(0);
  return ls ? arr : [0];
}

При глобальном тесте он выполняется более 12 секунд. Как мне уменьшить время выполнения кода? Какие приёмы оптимизации здесь нужно применить?
https://www.codewars.com/kata/5ce399e0047a45001c85... - ссылка на кату

Comments

[Robur]

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

[Lynn «Кофеман»]

Убрать второй цикл и изменение массива

[xmoonlight]

Максим Ко, самый быстрый код - в моём ответе.

Answer 1

[RAX7]

возникла проблема со скоростью выполнения кода

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

решение

function partsSums(ls) {
  const result = new Array(ls.length + 1);
  result[ls.length] = 0;

  for (let i = ls.length - 1; i > -1; i--) {
    result[i] = result[i + 1] + ls[i];
  }

  return result;
}

Comments

[Дмитрий Беляев]

for (let i = ls.length; i--;)будет итерировать аналогично Вашему, но читается в разы проще
но это так, придирка к KISS, решение O(n) действительно значительно обгонит O(n²) у автора.

[Lynn «Кофеман»]

А я, кстати, проверил что тут важно создать массив заранее (new Array), потому что при использовани .push/.unshift тесты сразу вылетают по времени. Переаллокация большого массива видимо очень дорогая операция

[RAX7]

Дмитрий Беляев, да, можно и такой вариант использовать, но мне он не нравится по причине того, что придется каждый раз из i вычитать единицу чтобы получить индекс массива.
UPD. Всё же вы правы, оно действительно работает без вычета единицы. Спасибо, в будущем пригодится =)
Lynn «Кофеман», там есть решения от других людей с использованием и push/unshift, и map/reduce. Народ развлекается как может. Хотя возможно раньше тесты были поменьше и такие решения проскакивали.

[WbICHA]

Интересно, что топовое решение, несмотря на двойной проход через массив, в 2-3 раза быстрее, чем данное крайне простое решение через фор.

spoiler

function partsSums(ls) {
    ls.unshift(0);
    let sum = ls.reduce((p, c) => p + c, 0);
    return ls.map(v => sum = sum - v);
}

Есть мутация, конечно, но это решаемой вопрос.

[RAX7]

WbICHA, нет, я проверил, это решение проходит тесты за ~4000ms, а моё за ~3000ms ¯\_(ツ)_/¯

[Дмитрий Беляев]

да, можно и такой вариант использовать, но мне он не нравится по причине того, что придется каждый раз из i вычитать единицу чтобы получить индекс массива.
UPD. Всё же вы правы, оно действительно работает без вычета единицы. Спасибо, в будущем пригодится =)

RAX7, тут весь прикол в особенностях работы постинкремента/постдекремента (когда ++ или -- идут после переменной а не до), он сначала отдает свой результат в выражение, а лишь потом вычисляется сам, по этому я и инициализирую i с длины массива, так как i все равно уменьшится после вычисления условия.

WbICHA, в этом решении на самом деле 3 прохода, так как unshift вынужден сдвинуть все индексы в массиве на количество вставляемых элементов, но сложность при этом все равно остается O(n). А быстрее оно лишь по тому, что v8 гораздо лучше умеет оптимизировать более предсказуемые reduce и map чем обычный цикл for, в котором можно творить любую дичь.

[xmoonlight]

Дмитрий Беляев, RAX7, WbICHA - гляньте моё решение и скажите косяки.
Выполняется быстро, но уверен, что далеко до идеала.

Answer 2

[xmoonlight]

Я вот так сделал:

function partsSums(ls) {
    if(ls.length==0) return [0];
    result=ls;
    result[i=result.length]=0;
    i--;
    while(i!==-1)
      result[i] = result[i+1]+ls[i--];
    return result;
}

Test Results:
partsSums
Basic tests
Random tests
Completed in 2070ms

линк

PS:

RAX7, ... а моё за ~3000ms ¯\_(ツ)_/¯

выжмешь ещё круче?)

PS2: RAX7, Кстати, там лучший результат - это тоже мутация, но работает за 927.29ms (наши же - менее 100ms).

function partsSums(ls) {
    ls.unshift(0);
    let sum = ls.reduce((p, c) => p + c, 0);
    return ls.map(v => sum = sum - v);
}

Comments

[WbICHA]

А в чём отличие от решения РАКСа? Кроме того, что некрасиво написано.

[xmoonlight]

WbICHA, минимум: в коде и в скорости исполнения.

[Дмитрий Беляев]

xmoonlight, а если преаллокацию всего массива делать не быстрее будет?
То есть вместо: const result=[];
Написать: const result = new Array(ls.length + 1);

[xmoonlight]

Дмитрий Беляев, дольше работает...

[Дмитрий Беляев]

xmoonlight, хм, думал количество realloc сократит, но кажись v8 как-то оптимизирует

[WbICHA]

xmoonlight, проверил в фф на 10 000 000 массиве, скорость в среднем +- та же.

[WbICHA]

xmoonlight, не знаю как ты тестил, но в ноде вообще без шансов:

$ node test.js
first for: 141.143ms
----------------------
second for: 1.455s

Массив тот же.

spoiler

(() => {
  function partsSums1(ls) {
    const result = new Array(ls.length + 1);
    result[ls.length] = 0;

    for (let i = ls.length - 1; i > -1; i--) {
      result[i] = result[i + 1] + ls[i];
    }

    return result;
  }
  function partsSums2(ls) {
    if(ls.length==0) return [0];
    const result=[];
    result[ls.length] = 0;
    let i=ls.length-1;
    while(i!=-1)
      result[i] = result[i+1]+ls[i--];
    return result;
  }
  
  const testArr = [];
  for(let i = 0; i < 10_000_000; i++) {
    testArr.push(~~(Math.random() * 100));
  }
  
  console.time('first for');
  partsSums1(testArr);
  console.timeEnd('first for');
  
  console.log('----------------------')
  
  console.time('second for');
  partsSums2(testArr);
  console.timeEnd('second for');
})()

Дмитрий Беляев, исходя из моих тестов, как раз первый вариант (РАКСа) НАМНОГО быстрее в ноде.

[xmoonlight]

WbICHA, Да. В хроме - такой же дикий! разрыв. На FF - одинаково почти.

[Дмитрий Беляев]

WbICHA, разница в 10 раз выглядит мега странно, но тем не менее:

win10, node 12.13.0, v8 7.7.299.13-node.12, AMD Ryzen 5 3600

first for: 78.940ms
----------------------
second for: 1536.180ms

вообще в 20 раз вышло

Debian 10, linux 4.19.0-5-amd64, node 14.4.0, v8 8.1.307.31-node.33, Intel Pentium G4560

first for: 108.457ms
----------------------
second for: 1.829s

где-то в 1.5 раза...

[xmoonlight]

WbICHA, Дмитрий Беляев, Вот для этого и запостил код.. Везде странно.
Интересно, это while или что так лагает?

[WbICHA]

xmoonlight, Дмитрий Беляев, добавил всего 1 строчку и код стал столь же быстр, как и первый:
result.length = ls.length + 1;

[WbICHA]

Причём строка должна быть ПЕРЕД вот этой:

result.length = ls.length + 1;
result[ls.length] = 0;

Поменяешь местами и опять гигантская разница.

[Дмитрий Беляев]

WbICHA, меня именно эта строка и смущала, так как менять размеры массива через установку элементов не очень хорошая идея в плане производительности

[xmoonlight]

Дмитрий Беляев, WbICHA, обновил код. Результат стал намного лучше.
first for: 138.420166015625 ms
second for: 65.930908203125 ms
(это в хроме: Версия 85.0.4183.133 (Официальная сборка), (64 бит))

[WbICHA]

xmoonlight, ты лучше несколько проходов сделай и увиличь входной массив на порядок. А то при таких результатах любой затуп, не связанный с кодом, хорошо заметен.

[xmoonlight]

WbICHA, несколько - это как именно? твоим тестом делал, гонял запуск несколько раз. Результаты (их отношение к друг-другу) - особо не прыгают.

[WbICHA]

xmoonlight, сорян, не сразу заметил. Конечно он будет быстрее, ты же мутируешь массив, а это не очень хорошо.

[xmoonlight]

WbICHA,

ты же мутируешь массив, а это не очень хорошо.

можешь пояснить для 2-х разных случаев (без привязки к коду):
1. Чем именно это плохо, если я его более нигде не использую?
2. Чем именно это плохо, если я его мутирую именно внутри функции?
(хотелось бы тоже для себя понять...)

[WbICHA]

xmoonlight,
1. Ничем. Только вот ты не можешь быть уверенным на 100%, что тебе не понадобиться этот массив в будущем. А если ещё и асинхронные функции используются, то вообще может быть весело, если одновременно 2+ функции будут обращаться к этому массиву.
Короче, если ты на 146% уверен, что ни сейчас, ни потом, тебе этот массив не пригодиться, то можно, а так лучше не стоит.
И ещё, либо в названии функции, либо хотя бы в жсдоке укажи, что она мутирует массив.

2. В этом-то и проблема, что ты его мутируешь НЕ внутри. Ты скопировал ссылку на массив, а не сам массив.

= [...arr]; // copy array values
= arr; // copy array address

[xmoonlight]

WbICHA, 1.

Короче, если ты на 146% уверен, что ни сейчас, ни потом, тебе этот массив не пригодиться, то можно, а так лучше не стоит.

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

Со всем согласен, но очень не люблю копировать лишний раз (и тратить время+оперативу) тогда, когда использование входных данных - одноразовое/однократное. :)

[RAX7]

xmoonlight, ну если не мутировать входной массив, то можно немного разогнать за счет использования типизированного массива

function partsSums(ls) {
  const result = new Int32Array(ls.length + 1);

  for (let i = ls.length - 1; i > -1; i--) {
    result[i] = result[i + 1] + ls[i];
  }

  return result;
}

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

[WbICHA]

Я слежу всегда за этим, разумеется.

Сейчас следишь, а через полгода, когда тебя попросят добавить новый функционал / изменить текущий? Опять всё вспоминать что, где и как?

2. Я оптимизировал скорость в ущерб целостности входных данных (вх.массив), т.к. мне больше и не требуется для данной задачи: нужно пройти все тесты за минимально возможное время.

В рамках данного задания это нормально, но вообще в нормальных задачках мутации запрещены.

Со всем согласен, но очень не люблю копировать лишний раз (и тратить время+оперативу) тогда, когда использование входных данных - одноразовое/однократное. :)

Это с какими же объёмами данных ты привык работать, что копирование массива реально сэкономит память и даст хоть сколько-то заметный выигрыш в скорости?

[xmoonlight]

RAX7, О! Спасибо. Буду держать в голове этот вариант. А намного даёт выигрыш (в %)?

[RAX7]

xmoonlight, у меня вышло примерно в 2 раза.

[xmoonlight]

WbICHA,

В рамках данного задания это нормально, но вообще в нормальных задачках мутации запрещены.

Кем?)

Это с какими же объёмами данных ты привык работать

Это не привычка, а необходимость (это не веб-разработка).

[xmoonlight]

RAX7, Неплохо. Правда не всегда такой разрядности может хватить...

[WbICHA]

Кем?)

Автором задачи, естественно.)

Это не привычка, а необходимость (это не веб-разработка).

Ну дык и я не фронтёр.) Просто я слабо себе представляю зачем брать ноду для обработки огромного количества данных одним куском. Да и то это скорее частные случае, во всяком случае лично я ни с чем настолько объёмным я пока не сталкивался.

[xmoonlight]

WbICHA, Экономнее брать готовые копии входных данных, если объём результата не превышает объёма входных данных, а промежуточного хранения - удаётся избежать.

[xmoonlight]

RAX7,

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

Тогда пусть ловят мутации)))

[xmoonlight]

RAX7, WbICHA Такой вот средний результат с использованием Int32Array в первом тесте от RAX7:

first for: 82.85107421875 ms
second for: 71.656005859375 ms

В любом случае мутация выигрывает в скорости даже против типизации, хотя уже и ненамного...