java - 在 1 GHz 处理器上运行 10-100 千万亿步的算法需要多长时间？

Question

这是我关于 SO 的第一个问题，如果它不合适/偏离主题，请告诉我。我已经把上面的问题提得相当笼统，但我遇到的具体问题如下:

我想编写一段 Java 代码，生成一个列表，列出所有可能导致选举人团平局的州组合。最短的可能列表将包含 12 个州，最长的可能列表将包含 38 个州。我做了一些(非常)粗略的计算，所有可能的组合都达到了(也许)10 千万亿。我仍处于算法的规划阶段，但假设 10 千万亿是所需步数的绝对下限，我想实际数字会高得多。

我对编程还很陌生，想知道是否值得编写这段代码 - 粗略计算表明该算法大约需要 30 年才能完成 (!)。但是，我的计算基于维基百科建议的 MIP(每秒百万条指令)值，我不知道它到底有多准确(或者实际上，对于这些目的，什么才算作“指令”)。

非常感谢阅读和/或回答:)

Answer 1

1 GHz 处理器的时钟每秒滴答 10 亿次。时钟滴答用于允许信号流通过系统。因此，理论上可以执行的(任何类型的)最大操作数是每秒 10 亿次操作。要执行 10 千万亿次运算，理论上的最短时间是 10 千万亿次除以 10 亿，得到 1000 万(秒)。如果我的计算是正确的，那么大约需要 116 天。在实践中，您不会获得那么多的性能，但是使用现代流水线处理器您实际上应该做得很好，比如说至少 50% 的优化汇编程序。因此，对于单个现代 1 GHz 处理器，我认为 200 天对于整数运算(如您在组合学中所期望的那样)是一个非常合理的猜测。

现在，您的“步骤”可能是很多机器指令。对于任何足够复杂的“步骤”，这似乎都是可能的。如果单个“步骤”是 100 条机器指令(一个相当强大的“步骤”)，那么我们实际上谈论的更像是 20,000 天或 54 年。

现在，我们能做什么？好吧，生成组合非常适合并行编程。例如，如果您能够在 super 计算中心抽出一些时间并在 1000 个内核上运行这项工作，每个内核以 3 GHz 运行，则运行大约需要 7 天才能完成 - 考虑到非并行工作可能需要 10 天。

或者，如果您能想出一个聪明的算法来避免分支，您可以得到一些 NVIDIA GTX 980 并在家里运行它。每个显卡大约有 2,000 个内核，每个内核以 ~1 GHz 的速度运行，因此这些坏小子中的一些将极大地加快您的任务(同样，如果您可以以在显卡上高效的方式编写程序 - 即困难的部分)。

判决？可行，但代价高昂和/或困难 - 如果您不习惯编写大量并行程序来使您希望做的事情变得可行，则尤其困难。