c-Sum(i..j)-是否有更有效/更优雅的解决方案

Question

我们被赋予了一项简单的任务，即想出最有效的方法，分别使用递归和迭代对起点和终点（"from"one_answers"to"）之间的所有数字求和，而不使用显而易见的公式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

---

更新

在我的实现中，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

我不确定这是否可以被视为公式的一种变体。无论如何，这对我来说都是一个有趣的练习

将范围（从零到上限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)

我不会为它编写代码，但这是一种会直接随着任务中核心数量而扩展的东西。

将范围划分为多个任务，并启动一个线程来对范围的每个小节求和，这将把你选择的任何实现所需的时间除以核心的数量（给予或接受）。

您还可以使用SIMD扩展，通过提前在内存中写入数据来促进加法（矢量加法）。将其推向另一个极端，你实际上可以使用GPU来计算子范围的添加（但你必须有足够大的范围才能使其值得开销），使其变得愚蠢而快速；因为这个问题非常简单，指令之间没有任何依赖关系。

您可以使用分段树来获取从i到j的分段的和。此结构具有O（log n）查找时间。

函数：

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

使用参数调用：（19999999）返回49999995000000，与求和公式n（n+1）/2一致，并在核心二人组上运行以下配置文件：

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

可能值得检查一下你的函数，我看不出它们会返回这个结果——数学选项是一个非常好的解决方案；）