用 Project Euler 学习 D

D 是一种系统编程语言。它的重点是将 C 和 C++ 的强大功能和高性能与 Ruby 和 Python 等现代语言的程序员生产力相结合。特别关注质量保证、文档、管理、可移植性和可靠性的需求。^[1]

Project Euler 是一个致力于一系列数学问题的网站，这些问题旨在通过计算机程序解决。每个问题都是根据“一分钟规则”设计的，这意味着有效的实现将允许在性能适中的计算机上在一分钟内获得解决方案。^[2]

在这篇文章中，我选择了一些问题，并向您展示如何用 D 语言解决它们。

• 我只选择最简单的，因为已发布的解决方案可能会破坏问题。
  
• 目的是展示 D 语言的功能和强大之处，因此下面的代码可能不是解决这些问题的最佳方式。

开始之前

首先，我们需要一个 D 编译器。
下面所有的例子都使用 dmd 2.0.32，您可以从官方网站下载它。
从 zip 文件中解压编译器并尝试编译“Hello World”程序

//helloworld.d import std.stdio; void main() { writeln("Hello, world!"); }

如果您使用的是 Windows，只需运行类似以下内容

C:\dmd2\windows\bin\dmd.exe helloworld.d
helloworld.exe

问题 1

让我们从问题 1开始

If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

这非常容易，答案是

$\sum _{i=1}^{\left\lfloor {\frac {999}{3}}\right\rfloor }3i+\sum _{i=1}^{\left\lfloor {\frac {999}{5}}\right\rfloor }5i-\sum _{i=1}^{\left\lfloor {\frac {999}{15}}\right\rfloor }15i$

这个方程可以用铅笔和纸来解决。呃……等等。我们在讨论编程语言，对吧？
也许从每个人在第一次尝试时使用的常见方法开始会更好

//problem1_a.d import std.stdio; void main() { int sum = 0; for (int i = 1; i < 1000; ++i) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

是的，当我解决第一个问题时，我就是这样做的。
如果我当时对 D 语言更熟悉，它看起来会像这样

//problem1_b.d import std.stdio; void main() { int sum; foreach (i; 1..1000) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

与第一个版本有两个区别

1. foreach 语句不仅更简洁，而且更快。

   这里速度可以忽略不计，但是您会发现当用 1×10⁸ 代替 1000 进行测试时，它可以节省大约 10% 的时间

2. 在 D 语言中，int sum 默认情况下被初始化为 0。

   如果您真的、真的不想初始化它，请使用 int sum = void;

D2 的标准库 Probos 还提供了一个强大的算法模块，可以让你用一行代码来实现它。

//problem1_c.d import std.stdio, std.algorithm, std.range; void main() { writeln( reduce!("a + b")(0, filter!("a % 3 == 0 || a % 5 == 0")(iota(1, 1000, 1))) ); }

它不如第二个版本（problem1_b.d）快，但它比用其他语言（如python 或haskell）编写的相应程序快。
如果您不知道这些函数是什么意思，这里有一个简要的解释

• !( ... )

  模板参数用 !(...) 而不是 <...> 括起来。Foo!(int) 在 D 语言中等于 C++ 中的 Foo<int>。

• reduce!("a + b")(0, range);

  对 range 中的元素进行求和并返回一个数字。

• filter!("a % 3 == 0 || a % 5 == 0")(range);

  找到 range 中满足要求的所有元素并返回一个新的 range。

• iota(begin, end, step);

  构造一个 range，它遍历 begin、begin + step、begin + 2 * step、...，直到但不包括 end。

给这些函数起别名会使代码更易读。

auto numbers = iota(1, 1000, 1); alias filter!("a % 3 == 0 || a % 5 == 0", typeof(numbers)) filter1; alias reduce!("a + b") sum; writeln( sum(0, filter1(numbers)) );

请查看官方网站上的这些页面以获取更多信息。
算法，模板，D 语言和 C++ 之间的模板比较

问题 2

问题 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

这个单行函数式解决方案被拆分为多行，以便我可以在其中添加一些注释

//problem2_a.d import std.stdio; import std.algorithm; import std.range; void main() { writeln( reduce!("a + b")( // the sum of all filter!("(a&1) == 0")( // the even-valued terms until!("a >= 4000000")( // which do not exceed four million recurrence!("a[n-1] + a[n-2]")(1, 2) // a Fibonacci sequence starting with 1 and 2 ) ) ) ); }

用直接递归来计算斐波那契数列是一个不好的做法^[3]，而当递归也被用来对数列求和时，情况就更糟了。

//problem2_b.d import std.stdio; int fib(int n) { if (n < 3) { return n; } else { return fib(n - 2) + fib(n - 1); } } int sumFib(int bound, int n = 1) { if (fib(n) > bound) { return 0; } else if (fib(n) & 1) { return sumFib(bound, n + 1); } else { return sumFib(bound, n + 1) + fib(n); } } void main() { writeln(sumFib(4_000_000)); }

如果您运行此程序，fib() 将在得到结果之前被调用 35563510 次。
这个数字是完全不可接受的，因为在 4,000,000 以下的数列中只有 32 个元素。

但令人惊讶的是，当改为模板递归时，程序可以得到极大的改进。

//problem2_c.d import std.stdio; import std.metastrings; template fib(int n) { static if (n < 3) { const fib = n; } else { const fib = fib!(n - 2) + fib!(n - 1); } } template sumFib(int bound, int n = 1) { static if (fib!(n) > bound) { const sumFib = 0; } else static if (fib!(n) & 1) { const sumFib = sumFib!(bound, n + 1); } else { const sumFib = sumFib!(bound, n + 1) + fib!(n); } } pragma (msg, ToString!( sumFib!(4_000_000) )); void main(){}

算法完全相同。但是这些更改使所有内容都在编译时完成。

• if -> static if
• return -> const
• writeln(...) -> pragma (msg, ...)

它比原始版本好得多，因为编译器只编译一次每个 fib!(n)（1 ≤ n ≤ 33）。
编译器直接输出结果，根本不需要运行程序。

问题 22

问题 22 被选中是因为它是第一个需要文件和字符串操作的问题

Using names.txt, a 46K text file containing over five-thousand first names, 
begin by sorting it into alphabetical order. Then working out the alphabetical 
value for each name, multiply this value by its alphabetical position in the 
list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is 
worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list.
So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

import std.stdio, std.string, std.algorithm; void main() { string input = cast(string)std.file.read("names.txt"); auto words = split(input, ","); sort(words); int score(string s) { // a nested function return reduce!("a + b - 64")(0, s[1..length-1]); // remove quotation marks and calculate the alphabetical value } long sum; foreach (i; 0..words.length) { sum += (i + 1) * score(words[i]); } writeln(sum); }