非常基本的 CS 问题 - 数字排序速度是否取决于整数大小？

Question

我没有 CS 背景，所以很抱歉我认为这是一个基本问题。但是出于好奇，如果我要对 [3,2,1] 与 [3e100, 2e100, 1e100] 进行排序，是否存在速度差异（即使是分钟）？

Answer 1

可能有也可能没有。与数学理论和原理有关的“计算机科学”与与制作实际软件有关的“软件工程”或“编程”之间存在差异。

在计算机科学中，像这样的细节在一般情况下并不重要。如果你在黑板上定义一个给定的场景，让它在速度上有这样的差异，它确实如此。您可以轻松地将黑板场景定义为 而不是 这样的速度差异。这取决于您和您正在处理的任何问题 space，但无论哪种方式，这主要是黑板上的数学问题，而不是真正的文字计算机器。

在软件工程/编程/开发/无论你想怎么称呼它，这取决于具体情况。作为 一般经验法则 ，排序 [2, 1, 3] 和排序 [200, 1, 30000] 可能需要相似（如果不相等）的数量平均时间。然而，排序 [2, 1, 3] 和排序 [2000000000, 1, 300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000] 可能会在速度上看到有意义的差异。

原因是它在很大程度上与用于存储数字的位数有关。它也可能与不同字节和内容存储在内存中的位置有关，但仅位大小的差异就足以证明一个不错的例子。

以32位整数为例。使用 32 位（或者在某些情况下，64 位，但 32 位更常见）来存储数字是非常常见的。例如，如果我们对任何非负整数有 32 位，我们现在将有一个介于 0 和 4,294,967,295 之间的数字。这个范围内的一些数字将如何存储在计算机中：

            0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
            1: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01
            2: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 10
            3: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11
            4: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00
            5: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 01
            6: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 10
            7: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 11
            8: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 10 00
                                     ...
           15: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 11
           16: 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00 00
                                     ...
4,294,967,295: 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11

如您所见，0、1、15 和 4,294,967,295 各取相同数量的 space。基本上来说，计算机对这些数字中的任何一个进行算术运算所遇到的麻烦与对其余任何数字进行算术运算的麻烦相同。它们在概念上可能更大或更小，但在计算机中，它们都需要相同数量的信息来存储。

（可能会有一点点差异，因为通常与硬件本身非常接近的原因；但是我个人不确定这会有多大差异，而且它超出了范围这个问题。软件和硬件是两个不同的领域。）

现在...现在，假设我们要存储上面提到的巨大的数字：即 3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000。

好吧，哎呀，3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000，大于4,294,967,295，并且与4,294,967,295和4,294,967,295是最大的数字，比32 = 222 = 222 = 222 = 222 =]

那么，我们的 64 位选项呢？可以容纳的最大整数是18,446,744,073,709,551,616，比上面列出的大数还小很多。这么直接，64位存储的运行也不行了。

因此运行超出了典型的内存大小，然后您开始将庞大的数字分解成更小的块。您不会将它们全部存储在一个 32 位或 64 位位置；相反，你将它存储在多个文件中。

这就是您看到速度差异的地方。对于较小的数字，每个数字都可以放入 32 位或 64 位（甚至 8 位或 16 位），计算机只需在一个小点中查找每个数字。对于庞大的数字，它必须查看潜在的多个。当它必须跨越多个点时，它会花费额外的时间 - 是的，绝对。

现在，综上所述，如果您真的愿意，您仍然可以在 32 位或 64 位中存储巨大的数字 (30000000...)。但是，您不能仅以基本方式存储它。您必须使用一种特殊格式，对所有这些 1 和 0 具有特殊含义。您可以按照 3 x 10^(89) 而不是 30000000000... 的方式排列它们。例如，你可以做这样的事情：

         89|                                  3
-----------|-----------------------------------
01 01 10 01|00 00 00 00 00 00 00 00 00 00 00 11

那将是 32 位，但它只使用前 8 位存储 10^(89) 部分，然后使用剩余的 24 位存储 3 部分。

这引入的问题是复杂化。它使程序员、QA 人员以及可能涉及的其他人员的工作复杂化。

然而，这也使计算机处理数字的方式变得复杂。 计算机本身不会理解上面的格式。您的代码 - 或者您的代码构建于其之上的某种工具，可能是实际的编程语言本身 - 将不得不翻译来回转换为计算机可以理解的格式或其他格式。即便如此，它还是会变得很大，以至于计算机一次只能处理一个。

总结一下，这里有几件事：

计算机科学和软件工程是两个不同的东西。
软件工程和硬件工程是两个不同的东西。
在黑板上，数字大小不会影响速度，基本上除非你想要它们或其他东西。
对于大多数日常的高级编程（像 JavaScript，而不是汇编），没有程序员经常需要关心的区别。大多数时候，我们至少假装根本不存在差异。至少有时候，它可能真的不存在。
然而，可能在硬件级别上有所不同。但是当我们处理像 JavaScript 这样的高级语言，而不是像 Assembly 和 C++ 这样的中低级语言时，我们通常不需要担心任何事情。事实上，即使是 C++ 程序员也可能不必担心很多次。
但如果我们处理的是超大数字，这可能会出现在科学软件或其他类似软件中，那么#4 的例外情况绝对存在，100% 存在。

Answer 2

如果您正在处理 numbers of arbitrary size，那么很明显，处理涉及用更多字节数表示的大数字的任何事情都会花费更多时间。

如果您要处理具有固定宽度表示的传统数字（例如 32 位整数、IEEE-754 双精度浮点数）：可能.

例如，对字节数组中的单个字节进行排序可能比对 32 位整数进行排序要慢，因为大多数硬件必须生成额外的屏蔽和移位指令来读取和写入单个字节。（另一方面，SIMD instructions 可以同时对较小的数据进行多次比较。）

再举一个例子，如果您正在进行基于比较的排序，比较 1 和 2³² - 1（从最高有效位看差异很明显）可能比在串行和按顺序比较位的硬件上比较 2 和 3（其中直到最低有效位没有区别）稍微快一些。在实践中，尤其是在现代硬件上，不太可能有任何明显的差异。

从计算机科学的角度来看，none 非常有趣。它依赖于硬件，任何差异都只是运行时复杂性中的一个常数因素。人们关心的是运行时复杂性如何随着输入的大小而增长。对于具有固定大小表示的数字，输入大小的这方面是恒定的，因此输入大小因此意味着要排序的项目数。

非常基本的 CS 问题 - 数字排序速度是否取决于整数大小？

Very basic CS question - does number sorting speed depend on integer size?

algorithm

computer-science