Sum (i ... j) - есть ли более эффективное/элегантное решение для этого?

Question

Нам была дана простая задача - найти наиболее эффективный способ суммирования всех чисел между начальной и конечной точкой (от «и» до «)» с использованием рекурсии и итерации соответственно без использования очевидной формулы, которая будет O (1).

Там нет приложения для этого, я просто любопытно, и вызов, чтобы увидеть, если мое решение может быть улучшено/полированная больше, чем уже есть:

/* recursion */ 
unsigned int sum1(unsigned int from, unsigned int to) { 
    if (to - from < 2) 
     return from + (from == to ? 0 : to); 
    else 
     return from + to + sum1(from + 1, to - 1); 
} 

/* iteration */ 
unsigned int sum2(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int i, s, n = p/2; 
    if (p % 2 == 0) s = n + from; 
    else { 
     s = 0; 
     n++; 
    } 
    for (i = 0; i < n; i++) { 
     s += from++ + to--; 
    } 
    return s; 
} 

Answer 1

Я попытался улучшения итеративной версии:

unsigned int sum2_improved(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int x = to + from; 
    int s = 0; 
    int i; 
    for (i = p >> 1; i > 0; i--) 
    { 
     s += x; 
    } 
    s += (p % 2 == 0) ? x >> 1 : x; 
    return s; 
} 

Я тестировал версию с:

for (i = 0; i < 9999999; i++) sum2(1,999); 

Это то, что я вижу:

$ time ./addm 
real 0m18.315s 
user 0m18.220s 
sys  0m0.015s 

Я пробовал свою реализацию с таким же количеством циклов. Вот как улучшенная функция выполняется:

$ time ./addm 
real 0m14.196s 
user 0m14.070s 
sys  0m0.015s 

---

UPDATE

В моей реализации x = to + from является сумма первого и последнего числа в последовательности. Если вы рассматриваете любую последовательную последовательность целых чисел и суммируете первый и последний, второй и предпоследний и т. Д. ... все эти суммы совпадают с одним и тем же значением. Например, в (1 ... 6), 1 + 6 = 2 + 5 = 3 + 4 = 7. Однако с последовательностью, содержащей нечетное число элементов, вы остаетесь с средним числом, которое вам необходимо будет добавить к суммарной сумме (это то, что делало назначение после цикла for.

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

unsigned int sum0(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int x = to + from; 
    int s = 0; 

    s += (x * (p >> 1)); 

    s += (p % 2 == 0) ? x >> 1 : x; 

    return s; 
} 

Я побежал это с тем же числом петель, как и в предыдущих опытах Вот что я видел:

$ time ./addm 

real 0m0.158s 
user 0m0.093s 
sys  0m0.047s 

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

Answer 2

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

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

Вы также можете использовать расширения SIMD для облегчения добавления (добавления векторов) путем записи данных в память перед началом работы. Принимая это в другой крайности, вы могли бы фактически использовать графический процессор для вычисления добавления поддиапазонов (но вам нужно было бы иметь достаточно большой диапазон, чтобы сделать его полезным накладные расходы), что делает его глупо быстрым; поскольку этот вопрос так же прост, как вы можете получить без каких-либо зависимостей между инструкциями.

Answer 3

Разделить диапазон (от нуля до верхнего предела n) в нижней и верхней половине. Для каждого значения в нижней половине есть значение в верхней половине, которое больше n/2; их n/2, поэтому сумма верхней половины равна сумме нижней половины + (n/2)^2.

В Python, который был бы:

def sum1(lower, upper): 
    if upper <= 0: 
     return 0 
    m, r = divmod(upper, 2) 
    return sum1(0, m) * 2 + m * m + r * upper - sum1(0, lower - 1) 

Answer 4

Вы можете использовать segment tree, чтобы получить сумму на segement из г в у. Эта структура имеет время поиска O (log n).

Answer 5

Функция:

long sum(long lower, long upper) { 
    long s = 0; 
    s = ((upper * (upper + 1)) - (lower - 1) * (lower))/2; 
    return s; 
} 

вызывается с параметрами: (1,9999999) возвращает 49999995000000 что согласуется с формулой суммирования N (N + 1)/2, и работает со следующим профилем на Core Duo:

real 0m0.005s 
user 0m0.002s 
sys  0m0.003s 

это может быть стоит проверить свои функции, я не могу видеть их возвращать результат - математический вариант намного превосходит решение;)