为什么不能扩展数组？

当我们创建一个数组时，我们不能改变它的大小;它是固定的。好吧，看起来不错，我们可以创建一个新的更大的数组，然后逐个复制这些数值，这个速度有点慢。它的技术背景是什么？为什么不能扩展数组？

来源

2010-05-10 Mustafa

你在用什么语言？ – 2010-05-10 18:15:19

您将需要指定您正在讨论的编程语言。 – Kzqai 2010-05-10 18:15:39

这是一个非常广泛的问题。要真正了解你必须知道计算机的内部工作原理。 – ChaosPandion 2010-05-10 18:15:49

这个问题没有提到一种语言，所以我要选择“C”阵列作为我的答案。

将数组分配为一块内存。增长数组是有问题的，因为唯一正确使用它的方法是在最后增加数组。对于N的增长，在下一个分配的地址之前，在数组末尾必须至少有N个空闲字节。

支持这种类型的分配需要将分配分散到虚拟地址空间。这既消除了将内存分配彼此靠近并用于增加分段的好处。这在大多数试图将内存打包在一起并减少碎片的内存管理器面前飞来飞去。

在内存空间足够的地方分配一个新阵列并复制数组根本没有一个选项作为一个通用的解决方案。之所以这样，是因为消费者通过指针可以看到数组的前一个位置。

int* array = malloc(int*someSize); 
int* pointer1 = &(arr[2]); 
growArray(&array, 12); // Can't move because pointer1 knows the address of the array

来源

2010-05-10 18:22:09 JaredPar

我觉得你很好，直到最后一段。它*是*可能的，你只需要小心，你不要留下任何悬挂的指针。无论如何，他都将此视为Java。 – mpen 2010-05-10 18:25:25

@Mark，我将它改为在文中包含“作为一般解决方案”，以便更清楚地说明这一点。 – JaredPar 2010-05-10 18:29:08

+1很好的答案。 – helpermethod 2010-05-10 20:45:55

从根处开始的数组是一个连续的“数组”。其他数据可以占用此区域内存之前和之后的数据，因此如果不分配适合新的更大容量的新的，不同区域的内存，将无法动态调整其大小。

来源

2010-05-10 18:16:04

这取决于语言。

在C语言（以及类似Java的类似语言）中，当您声明一个像int ary[10]这样的数组时，系统留出足够的内存来保存10个整数。扩展它并不容易，因为系统没有留出任何额外的空间（因为它不知道你是否想要扩展它或多少），并且可能正在使用阵列后出现的内存通过别的东西。所以，获得更大数组的唯一方法是放置一个新的内存块，它将容纳扩展数组，然后复制旧内容并添加新项。

你是对的，这可能会很慢。解决它的一个办法是声明你的阵列比你需要的大，以便给你增长空间。特别是在较旧的电脑上，这可能会导致程序耗尽大量从未使用过的内存。

另一种解决方法是使用具有可扩展数组的高级语言。例如，Ruby允许您将更多项添加到数组中，而无需声明内存或复制数组内容。

来源

2010-05-10 18:19:41 bta

但是，您应该意识到，在具有可变大小数组的语言中，数组可能仍会由固定大小的存储支持，并在必要时进行扩展和复制。（或者它被实现为一个链表，它避免了复制的需要，但是在访问任意索引方面还有其他缺点。） – 2010-05-10 18:23:44

Ruby只是为你做内存分配和数据拷贝。硬件层面没有办法解决这个问题。或者也许它使用的访问时间较慢的数据结构，但实际上可以在不重新分配的情况下变大。 – phkahler 2010-05-10 18:26:51

@JS Bangs，phkahler-两个好点。我的主要观点是你不必担心自己做这件事。 – bta 2010-05-10 22:40:22

取决于您的语言，但通常阵列排列为内存中的一系列连续空间。这样，您不必为数组中的每个点存储内存位置，只需存储一个内存位置（数组的开始），然后添加一个偏移量（偏移量将是每个项的大小乘以索引你想要）找出某个特定条目在内存中的位置。

这也是为什么数组通常只包含一种类型，否则无法进行如此简单的计算。确实允许存储多种类型的语言实际上是创建一个普通数组，并将指针指向数组中的每个条目 - 所有指针的大小通常相同。这种间接成本的水平，这就是为什么“简单”的语言往往慢一点。

无论如何，当你分配更多的内存时，你想把新的内存放在数组的末尾 - 否则你会用一个洞来分割你的内存 - 你为什么要这样做？

所以你不能只是扩展阵列而不用物理移动它。

计算机已经这么做了很多年了，所以大多数语言都有一些方法来分配新的内存块，然后告诉CPU将所有条目都块复制到新块中，并更改指针来反映这一点，但通常（C，Java，...）他们把这个留给程序员用特定的命令来复制数组而不是为你做（可能只是为了让你知道扩展数组不是“免费”的）

可以在数组末尾添加一个指针，以跳转到要添加到数组末尾的新内存块，但是现在您的数组查找速度已经变得相当缓慢了。

许多语言只是将数组作为允许这种功能的集合来包装。例如，Java Vector/ArrayList将自动为您重新分配内存。链接列表实际上只是每次分配一个元素，并指向下一个元素。添加元素的速度非常快，但是元素5000非常慢（您必须读取每个元素，而读取元素1的数组与元素5000一样快）

来源

2010-05-10 18:19:51

一般而言，编程语言有地方，分配的内存一个固定部分的东西的抽象。然后，从这种抽象出发，可以创建其他抽象，隐藏内存管理的复杂性，可能通过移动/复制数据。

大多数时候，array是固定的 - 一个（不知）低级别的抽象 - 而lists或collections被建立在阵列的顶部，并知道如何动态调整自己。

有时候这样的低级抽象可以实现有效算法/优化。但是在大多数代码中，您可以使用列表和集合，而不必担心性能问题。

来源

2010-05-10 18:22:31 ewernli

是否可以更改数组的大小取决于您使用的是哪种语言。在那些不能增加数组大小的语言中，原因是数组布局在内存中的连续位置，编译器无法保证数组末尾的位置可以添加到数组中。许多编程语言都支持可扩展的数组类型，但这些语言只是简单地为您处理底层内存的重新分配和复制。

例如，在Curl编程语言中，存在具有大小和最大大小的FastArray类型。 max-size指定数组的最大大小，并确定将为该数组分配多少内存。还有一种更通用的Array类型，它使用FastArray作为它的底层实现，并且如果数组需要扩展超出底层FastArray的最大大小，它将替换FastArray实例。

来源

2010-05-10 18:24:31

回到汇编语言，我们有义务声明变量所需的内存空间。这是数据段（DS）注册表中的保留内存。

所以，大致看上去就像这样（Borland的涡轮汇编）：

.DATA 
    myStringVariable DB "Hello world!", 13, 10 
    myArrayVariable DW "     " 'Reserving 20 bytes in memory (in a row) 

.CODE 

    MOV AX, @DATA 
    MOV DS, AX 
    ' ...

然后，一旦。数据段被分隔，它不能被改变，因为.CODE段（CS）在稍后的几个字节处开始。

因此，如果阵列本来可扩展的，像集合在.NET，数据会覆盖的代码，从而导致程序崩溃等

C/C++（3.0），帕斯卡（ 7.0），QBasic，PowerBasic和COM调试程序基于这种架构，并且可以做得比Assembler允许的更好。现在，我们现在可以用更灵活的技术根据需要随时分配内存地址，并且只用一个变量来保存对它们的引用，这样数组就可以通过集合进行扩展。但是在某些情况下，您需要精确的字节数量，比如网络数据包等，例如数组仍然有用。另一个例子是将图像存储在数据库中。你完全知道割大字节是一个图像，所以你可以将它存储在一个字节数组中（Byte []）。

也许我在这里错过了一些精度，我写了我记忆中的旧我最喜欢的编程语言。也许一些人会提出一些更详细的东西。

希望这会有所帮助！ =）

来源

2010-05-10 18:39:17

为什么不能扩展数组？

回答

相关问题