Увеличьте скорость функции JavaScript

Question

У меня есть задача, которую я нашел на CodeWars, и мне удалось ее решить, однако после отправки отображается:

Истекло время выполнения: (12000 мс)

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

const ls = [0, 1, 3, 6, 10]

const partsSums = (ls) => {
    const sum = []
    for(let i = 0, len = ls.length; i < len + 1; i++) {
        let result = ls.slice(i).reduce( (accumulator, currentValue) => accumulator + currentValue, 0)
        sum.push(result)
    }
    return sum
}

Вот инструкции:

Рассмотрим этот пример (массив, записанный в общем формате):

ls = [0, 1, 3, 6, 10]

Его следующие части:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

Соответствующие суммы (объединены в список): [20, 20, 19, 16, 10, 0]

Функция parts_sums (или ее варианты на других языках) будет принимать в качестве параметра список ls и возвращать список сумм его частей, как определено выше.

Answer 1

• 1000 1004 *

Этот подход принимает 1 oop и использует индекс для получения значения данного массива и принимает последнюю сумму нового массива.

Некоторые тесты скорости на Codewars : Суммы частей :

• 5621 мс с разреженным массивом sum = []; sum[i] = 0; (первая версия этого ответа),
• 3452 мс с Array(i + 1).fill(0) и без sum[i] = 0;,
• 1261 мс с Array(i + 1) и sum[i] = 0; (см. ниже),
• 3733 мс с Icepickle первая попытка .

const
    partsSums = (ls) => {
        let i = ls.length;
        const sum = Array(i + 1);

        sum[i] = 0;
        while (i--) sum[i] = sum[i + 1] + ls[i];

        return sum;
    },
    ls = [0, 1, 3, 6, 10];

console.log(...partsSums(ls));

Answer 2

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

Вот идея - поскольку вы пытаетесь суммировать все элементы, затем суммируете все, кроме первого, затем суммируйте все, кроме второго, et c., математически эквивалентно получению суммы с последующим вычитанием из нее каждого числа по порядку и сохранением суммы.

[sum([41, 42, 43]), sum([42, 43]), sum([43]), sum([])]

то же самое, что:

total = sum([41, 42, 43])
[total - 0, total - 0 - 41, total - 0 - 41 - 42, total - 0 - 41 - 42- 43]

совпадает с:

total = sum([41, 42, 43])
[total -= 0, total -= 41, total -= 42, total -= 43]

В обобщенном виде это выглядит так:

total = sum([a1, a2, ..., aN])
[total -= 0, total -= a1, total -= a2, ..., total -= aN]

Используя надежный Array#reduce, мы можем получить сумма один раз. Затем мы можем получить новый массив, используя Array.map, используя ls.map(num => total -= num).

Единственная проблема здесь в том, что мы получаем на один элемент меньше - мы не вычисляем начальное total -= 0 который должен существовать для всех предметов. Один из способов сделать это - добавить его в начало. [0].concat(ls) создаст правильный массив для сопоставления. Однако, поскольку мы уже знаем, какое будет значение, мы можем пропустить этот шаг и напрямую заменить его на total (ведь результат total -= 0 равен total и оставляет total без изменений). Итак, мы можем напрямую использовать [total].concat(ls.map(num => total -= num)), чтобы начать с total и добавить остальные элементы. до конца.

const ls = [0, 1, 3, 6, 10]

const partsSums = (ls) => {
    let total = ls.reduce((a, b) => a + b, 0);
    
    return [total]
      .concat(
        ls.map(num => total -= num)
      );
}

console.log(partsSums(ls));

Answer 3

Лично я бы просто использовал предыдущую сумму для вычисления следующей, я не вижу необходимости повторять все предыдущие суммы, поэтому я бы, вероятно, go для базиса c l oop а затем переверните результаты, например,

function partsSums(ls) {
  const result = [0];
  if (ls.length === 0) {
    return result;
  }
  for (let i = ls.length, q = 0; i--; q++) {
    result.push(result[q] + ls[i]);
  }
  return result.reverse();
}

или, без реверсирования, больше похоже на решение Нины (за исключением предопределения длины массива)

function partsSums(ls) {
  const len = ls.length;
  const result = new Array(len+1);
  result[len] = 0;
  for (let i = len; i--;) {
    result[i] = result[i+1] + ls[i];
  }  
  return result;
}

Оба также кажутся работать быстрее, чем у Нины на движке codewars nodejs, в первой части, вероятно, из-за pu sh, во второй, вероятно, потому что длина массива определена с самого начала, для получения дополнительной информации см. этот вопрос

Answer 4

const partsSums = (ls, sum = 0) =>
   [...ls, 0].reverse().map(x => sum = x + sum).reverse();

Занимает около 1100 мс , когда я запускаю его на CodeWars , что немного быстрее, чем другие ответы.

Answer 5

Решение, использующее стандарт для l oop во время выполнения.

var arr = [0, 1, 3, 6, 10];


function giveList(array){
    
    var sum=0;
    for(let i=0;i<array.length;i++){
       sum=sum+array[i];
    }

    var result = [];
    result.push(sum);
    var temp;
    for(let i=0;i<array.length;i++){
       temp=sum-array[i];
       result.push(temp); 
       sum=sum-array[i];
        
     }
 return result;
}

console.time();
console.log(giveList(arr));
console.timeEnd();

Answer 6

Повторная операция - это слишком много. например: когда вы вычисляете сумму [3, 6, 10], шаг вверх [1, 3, 6, 10] уже вычисляется。 Таким образом, вы можете думать в другом направлении, назад до конца вычислить сумму массива

const ls = [0, 1, 3, 6, 10];

function partSums(ls) {
   const len = ls.length;
   const dp = [];

   if(len === 0) { return [0] }
   dp[len] = 0;
   dp[len - 1] = ls[len - 1];
   for (let i = len - 2; i >= 0; i--) {
     dp[i] = dp[i + 1] + ls[i];
   }

   return dp;
}