0

我的问题如下：

我必须遍历 95 个元素的所有可能性（0 或 1）。

例如，如果有 2 个元素，则可能性为：00、01、10、11

总可能性的数量是 2^n，所以它增长得非常快。2^95 = 39614081257132168796771975168

我将如何有效地从 0 迭代到 2^95？

PS 编程语言的选择并不重要，但我猜 C 或 C++ 应该是最快的选择。

PPS 我认为 BigInt 实现似乎比原始类型慢得多，将数字拆分为 X 个原始类型可能是个好主意。到目前为止，我没有运气。

PPS 我有一个函数可以通过提供一个从 0 到 2^95 的数字来产生可能性

4

4 回答 4

8

Modern CPUs run at a few GigaHertz, so you might be able to iterate over one billion values per second (if you're not doing much else).

At one billion iterations per second, it would take you over 1.2 trillion years to reach 295 iterations.

You need to find a different way to do whatever you're doing.

于 2013-10-26T18:33:57.907 回答
2

除非你有一台量子计算机，否则你无法逃避整个范围的迭代。最简单的方法是将 95 位拆分为一组原语。例如，如果您的系统使用 64 位数字运行，您可以取其中的 2 个。伪代码将是这样的：

lowBound <-- 2^64-1
highBound <-- 2^31-1
for highIdx = 0 up to highBound
    for lowIdx = 0 up to lowBound
         ; Do your thing here, if you need the actual index,
         ; it's combinable from lowIdx and highIdx

最快的方法是Assembly与特定于体系结构的指令一起使用，以更好地利用系统资源来加速进程（寄存器、缓存等）。您还可以考虑使用 GPU——它们非常适合并行化任务，因此如果每次迭代的操作都相似，则它可以具有良好的性能。

但是，所有这些都毫无用处，您应该为正在做的事情设计一个更好的算法，而不是迭代，就像@KeithThompson 的回答中指出的那样。

于 2013-10-26T18:38:02.780 回答
2

理论上，这就是你要做的：

int exp = 95;

UInt64 hmax = 2 ^ (exp - 64);
UInt64 lmax = 2 ^ 63 + (2 ^ 63 - 1);

for (UInt64 high = 0; high < hmax; high++) {
    for (UInt64 low = 0; low <= lmax; low++) {

        // do stuff

    }
}

现在循环控制high保存高位字，循环控制low保存低位字。现在您可以执行以下操作：

// where UInt128 is your big integer type
// cast the high word to prevent overflow

UInt128 word = (UInt128)high << 64 | low;

或者将它们连接为字符串。

循环模式如下所示（使用字节表示）：

00000000 00000000
00000000 00000001
00000000 00000010

and eventually you get to

00000000 11111111

inner loop completes and it goes to

00000001 00000000
00000001 00000001
于 2013-10-26T18:41:00.877 回答
1

我的猜测是您将需要量子位 ( http://en.wikipedia.org/wiki/Qubit ) 来进行计算，但由于它们本质上是理论上的，也许最好现在开始迭代，看看是否会更快，否则量子计算会很快得到你的答案。

使用量子计算，您将能够一次测试所有组合。

从这里开始阅读，它可能无法解决您的问题，但它确实很有趣： http: //physics.about.com/od/physicsqtot/g/quantumparallel.htm

于 2013-10-26T20:58:31.570 回答