Как найти сумму определенных элементов массива

TL;DR

If you care about performance, define a function that uses a for-loop.

function sum(arr) {
    var res = 0;
    for (var x of arr) {
        res += x;
    }
    return res;
}

Benchmark

I benchmarked a selection of implementations using benchmark.js (typescript version):

const arr = Array.from({ length: 100 }, () => Math.random());
const reducer = function (p: number, a: number) {
    return p + a;
};
const recursion = function (arr: number[], i: number) {
    if(i > 0) return arr[i] + recursion(arr, i - 1)
    else return 0
};
const recursion2 = function (arr: number[], i: number, len: number) {
    if(i < len) return arr[i] +  recursion2(arr, i + 1, len)
    else return 0
};
const recursion3 = function (arr: number[], i: number) {
    if(i < arr.length) return arr[i] + recursion3(arr, i + 1)
    else return 0
};
new Benchmark.Suite()
    .add("jquery", () => {
        let res = 0;
        $.each(arr, (_, x) => (res += x));
    })
    .add("lodash", ()=>_.sum(arr))
    .add("forEach", () => {
        let res = 0;
        arr.forEach((x) => (res += x));
    })
    .add("reduce", () => arr.reduce((p, a) => p + a, 0))
    .add("predefined reduce", () => arr.reduce(reducer, 0))
    .add("eval", () => eval(arr.join("+")))
    .add("recursion", () => recursion(arr, arr.length - 1))
    .add("recursion2", () => recursion2(arr, 0, arr.length))
    .add("recursion3", () => recursion3(arr, 0))
    .add("naive", () => (
        arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+arr[5]+arr[6]+arr[7]+arr[8]+arr[9]+
        arr[10]+arr[11]+arr[12]+arr[13]+arr[14]+arr[15]+arr[16]+arr[17]+arr[18]+arr[19]+
        arr[20]+arr[21]+arr[22]+arr[23]+arr[24]+arr[25]+arr[26]+arr[27]+arr[28]+arr[29]+
        arr[30]+arr[31]+arr[32]+arr[33]+arr[34]+arr[35]+arr[36]+arr[37]+arr[38]+arr[39]+
        arr[40]+arr[41]+arr[42]+arr[43]+arr[44]+arr[45]+arr[46]+arr[47]+arr[48]+arr[49]+
        arr[50]+arr[51]+arr[52]+arr[53]+arr[54]+arr[55]+arr[56]+arr[57]+arr[58]+arr[59]+
        arr[60]+arr[61]+arr[62]+arr[63]+arr[64]+arr[65]+arr[66]+arr[67]+arr[68]+arr[69]+
        arr[70]+arr[71]+arr[72]+arr[73]+arr[74]+arr[75]+arr[76]+arr[77]+arr[78]+arr[79]+
        arr[80]+arr[81]+arr[82]+arr[83]+arr[84]+arr[85]+arr[86]+arr[87]+arr[88]+arr[89]+
        arr[90]+arr[91]+arr[92]+arr[93]+arr[94]+arr[95]+arr[96]+arr[97]+arr[98]+arr[99]))
    .add("loop with iterator", () => {
        let res = 0;
        for (const x of arr) res += x;
    })
    .add("traditional for loop", () => {
        let res = 0;
        // cache the length in case the browser can't do it automatically
        const len = arr.length;
        for (let i = 0; i < len; i++) res += arr[i];
    })
    .add("while loop", () => {
        let res = 0;
        let i = arr.length;
        while (i--) res += arr[i];
    })
    .add("loop in a function ", () => sum(arr))
    .on("cycle", (event) => console.log(String(event.target)))
    .run();

In chrome 104, the for-loop-based implementations are the fastest:

jquery               x  1,832,472 ops/sec ±1.35% (61 runs sampled)
lodash               x  2,079,009 ops/sec ±1.11% (68 runs sampled)
forEach              x  4,887,484 ops/sec ±2.35% (67 runs sampled)
reduce               x 21,762,391 ops/sec ±0.46% (69 runs sampled)
predefined reduce    x  2,026,411 ops/sec ±0.50% (68 runs sampled)
eval                 x     33,381 ops/sec ±2.54% (66 runs sampled)
recursion            x  2,252,353 ops/sec ±2.13% (62 runs sampled)
recursion2           x  2,301,516 ops/sec ±1.15% (65 runs sampled)
recursion3           x  2,395,563 ops/sec ±1.65% (66 runs sampled)
naive                x 31,244,240 ops/sec ±0.76% (66 runs sampled)
loop with iterator   x 29,554,762 ops/sec ±1.07% (66 runs sampled)
traditional for loop x 30,052,685 ops/sec ±0.67% (66 runs sampled)
while loop           x 18,624,045 ops/sec ±0.17% (69 runs sampled)
loop in a function   x 29,437,954 ops/sec ±0.54% (66 runs sampled)

Firefox 104 shows similar behaviour:

jquery               x  1,461,578 ops/sec ±1.58% (64 runs sampled)
lodash               x  4,931,619 ops/sec ±0.80% (66 runs sampled)
forEach              x  5,594,013 ops/sec ±0.51% (68 runs sampled)
reduce               x  3,731,232 ops/sec ±0.53% (66 runs sampled)
predefined reduce    x  2,633,652 ops/sec ±0.54% (66 runs sampled)
eval                 x    105,003 ops/sec ±0.88% (66 runs sampled)
recursion            x  1,194,551 ops/sec ±0.24% (67 runs sampled)
recursion2           x  1,186,138 ops/sec ±0.20% (68 runs sampled)
recursion3           x  1,191,921 ops/sec ±0.24% (68 runs sampled)
naive                x 21,610,416 ops/sec ±0.66% (66 runs sampled)
loop with iterator   x 15,311,298 ops/sec ±0.43% (67 runs sampled)
traditional for loop x 15,406,772 ops/sec ±0.59% (67 runs sampled)
while loop           x 11,513,234 ops/sec ±0.60% (67 runs sampled)
loop in a function   x 15,417,944 ops/sec ±0.32% (68 runs sampled)

Discussion

Implementations defining an anonymous function are generally slower because creating an anonymous function is a significant overhead. When running the benchmark with a large array, e.g., with length 1000 instead of 100, the difference between reduce and the for-loop-based implementations becomes insignificant in chrome.

Chrome’s V8 engine knows how to inline simple anonymous functions in reduce since the reduce test case is much faster than the predefined reduce test case. Firefox seems to try something similar but is less efficient in doing so. Non-inlined function calls are pretty slow in js since the call stack is less efficient than the call stack in compiled software.

Similar to reduce, the forEach— and jquery-based implementations use anonymous functions and are relatively slow. lodash has a specialized sum implementation, but it is (as of v4.0.0) implemented as a special case of sumBy, which is relatively inefficient.

eval is the by far slowest test case. This makes sense since constructing the string using concatenations might cause several dynamic allocations (which are slow). Next, the parser has to be invoked and only then can the code be finally executed.

I’ve included some recursive implementations because some people on the internet claim that recursion is faster than loops in js. I can’t reproduce their example — using benchmark.js, recursion is very slow, and when using console.time with a loop, both functions take the same time. When calculating the sum, as expected, recursion is much slower than loops, probably due to intense usage of the js call stack.

The naive implementation would be manually adding all 100 elements of the array. While being quite inconvenient, this is the fastest implementation. But, luckily, for-loops come very close. Adding a single function call around the loop doesn’t harm the performance. Therefore, you can feel free to use the utility function from above.

I have no explanation why the while loop is slower than the for loop. Iterating the array in reverse doesn’t seem to be the problem here.

В этом посте мы обсудим, как найти сумму элементов в массиве C++.

1. Использование STL accumulate() функция

Стандартным решением является использование std::accumulate предоставляется стандартной библиотекой. Он определен в заголовочном файле numeric. Операция по умолчанию заключается в добавлении элементов до но, чтобы сделать контекст более понятным. Мы также можем передать функцию в необязательном четвертом параметре, которая выполняет операцию сложения двух чисел и возвращает результат.

Скачать  Выполнить код

2. Использование Boost accumulate() функция

Еще одна хорошая альтернатива — использовать boost accumulate() функция, которая определена в заголовочном файле boost/range/numeric.hpp.

Скачать код

3. Использование STL for_each() функция

Мы также можем написать логику суммирования в предикате для std::for_each стандартный алгоритм. Это показано ниже с использованием лямбда-выражений:

Скачать  Выполнить код

4. Цикл for/цикл for на основе диапазона

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

⮚ Для цикла

Скачать  Выполнить код

⮚ Цикл for на основе диапазона

Скачать  Выполнить код

5. Использование valarray sum() функция

Если valarray используется вместо стандартного массива, операция суммирования может быть применена непосредственно к valarray объект, вызвав его функцию-член sum().

Скачать  Выполнить код

6. C++17 — Свернуть выражения

С C++17 мы можем использовать складывать выражения, как показано ниже:

Выполнить код

Это все, что касается нахождения суммы элементов в массиве C++.