python - 优化 bigint 调用

Question

我目前正在使用“D 编程”这本书来学习 D。我试图解决一个求和从 1 到 10000000 的数字的平方的问题。我首先采用函数式方法来解决 map 和问题reduce 但随着数字变大，我必须将数字转换为 bigint 以获得正确的输出。

  long num = 10000001;
  BigInt result;
  result = iota(1,num).map!(a => to!BigInt(a * a)).reduce!((a,b) => (a + b));
  writeln("The sum is : ", result);

当使用 dmd -O 编译时，上面的代码需要 7 秒才能完成。我分析了程序，大部分时间都浪费在 BigInt 调用上。尽管数字的平方可以放入一个 long 中，但我必须将它们转换为 bigint，以便减少函数求和并返回适当的总和。 python 程序只需 3 秒即可完成。当 num = 100000000 时，D 程序需要 1 分 13 秒才能完成。有没有办法优化对 bigint 的调用。产品本身可以很长，但必须将它们类型转换为 bigint 对象，以便它们从 reduce 操作中给出正确的结果。我尝试将数字的平方插入 bigint 数组，但速度也较慢。我试图将所有数字转换为 Bigint

auto bigs_map_nums = iota(1,num).map!(a => to!BigInt(a)).array;
auto bigs_map = sum(bigs_map_nums.map!(a => (a * a)).array);

但是它也比较慢。我在 How to optimize this short factorial function in scala? (Creating 50000 BigInts) 阅读了答案. D 中较大整数的乘法实现是否也存在问题？有没有办法优化对 BigInt 的函数调用？

python 代码:

timeit.timeit('print sum(map(lambda num : num * num, range(1,10000000)))',number=1)
333333283333335000000
3.58552622795105

代码是在具有 2 GB RAM 的双核 64 位 Linux 笔记本电脑上执行的。 python :2.7.4dmd : DMD64 D 编译器 v2.066.1

Answer 1

没有范围冷却:foreach(x; 0 .. num) result += x * x;

范围很酷(？):

import std.functional: reverseArgs;
result = iota(1, num)
    .map!(a => a * a)
    .reverseArgs!(reduce!((a, b) => a + b))(BigInt(0) /* seed */);

当然，关键是要避免 BigInt 处理每个元素。

范围版本比非范围版本慢一点。两者都比 python 版本快得多。

编辑:哦!哦!使用 std.algorithm.sum 可以让它变得更加愉快:

result = iota(1, num)
    .map!(a => a * a)
    .sum(BigInt(0));