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

我没有CS背景，所以我为我认为是一个基本问题而道歉。但出于好奇，如果我对[3,2,1]和[3e100，2e100，1e100]进行排序，是否存在速度差(即使是分钟)？

可能有也可能没有；"计算机科学"；，这与数学理论和原理有关；软件工程；或"；编程"；，这与制作实际软件有关。

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

在软件工程/编程/开发/无论你想怎么称呼它，它在某种程度上取决于情况。根据一般经验，排序[2, 1, 3]和排序[200, 1, 30000]可能平均花费相似(如果不相等)的时间。然而，对[2, 1, 3]进行排序和对[2000000000, 1, 300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]进行排序可能会在速度上看到有意义的差异。

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

以一个32位整数为例。使用32位(在某些情况下，64位，但32位更常见)来存储数字是非常常见的。例如，如果我们对任何非负整数都有32位，那么我们现在的数字将在0到4294967295之间。这就是该范围内的几个数字将如何存储在计算机中：

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和4294967295各占用相同的空间量。基本上说，计算机对这些数字中的任何一个进行算术运算所经历的麻烦与对其他数字进行算术运算一样多。它们在概念上可能更大或更小，但在计算机中，它们都需要存储相同数量的信息。

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

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

好吧，见鬼，30000000000000000000000000000000000000000000000000000000000000000000000比4294967295大很多，429496729已经是32位存储的最大数字了。

那么，我们的64位选项呢？可以容纳的最大整数是18446744073709551616，这仍然比上面列出的巨大数字小很多。因此，完全直接的、普通的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之类的东西，而不是Assembly之类的东西)来说，没有程序员必须经常关心的区别。大多数时候，我们至少假装根本不存在差异。至少有时，它可能真的不存在
然而，可能在硬件级别上存在差异。但当我们处理像JavaScript这样的高级语言，而不是像Assembly和C++这样的中低级别语言时，我们通常不必担心。实际上，即使是C++程序员也可能不必经常担心它
但是，如果我们要处理的是科学软件或其他类似软件中可能出现的超巨大数字，那么第4条的例外情况绝对是100%存在的

如果你处理的是任意大小的数字，那么很明显，处理任何涉及用更多字节表示的大数字的事情都需要更多的时间。

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

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

另一个例子是，如果你正在进行基于比较的排序，那么在串行和顺序比较位的硬件上，比较1和2³²-1(与最高有效位的差异明显)可能比比较2和3(直到最低有效位才有差异)略快。在实践中，尤其是在现代硬件上，不太可能有任何明显的差异。

从计算机科学的角度来看，这些都不是很有趣。它取决于硬件，任何差异都只是运行时复杂性的一个恒定因素。所关心的是运行时复杂性相对于输入大小的增长。对于具有固定大小表示的数字，输入大小的这一方面是恒定的，因此输入大小意味着要排序的项目数

相关内容

最新更新

热门标签：