在编程过程中,我还没有看到数组比另一种形式的数组更适合存储信息的实例。我确实认为,编程语言中添加的“特性”已经在此基础上进行了改进,并取代了它们。我现在明白了,它们并没有被取代,而是被赋予了新的生命。

那么,使用数组的意义是什么呢?

这并不是我们为什么要从计算机的角度使用数组,而是我们为什么要从编程的角度使用数组(一个微妙的区别)。计算机对数组做什么并不是问题的重点。


对于O(1)随机存取,这是不可战胜的。


是时候回到过去上课了。虽然我们在今天的高级托管语言中没有过多地考虑这些事情,但它们都建立在相同的基础上,因此让我们看看在C中如何管理内存。

在我深入研究之前,先快速解释一下术语“指针”的含义。指针只是一个变量,它“指向”内存中的某个位置。它不包含这个内存区域的实际值,它包含它的内存地址。把一块内存看作一个邮箱。指针将是该邮箱的地址。

在C语言中,数组只是一个带偏移量的指针,偏移量指定在内存中查找的距离。这提供了O(1)访问时间。

  MyArray   [5]
     ^       ^
  Pointer  Offset

所有其他数据结构要么建立在此基础上,要么不使用相邻内存进行存储,从而导致较差的随机访问查找时间(尽管不使用顺序内存还有其他好处)。

例如,假设我们有一个数组,其中有6个数字(6,4,2,3,1,5),在内存中它看起来是这样的:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

在数组中,我们知道每个元素在内存中彼此相邻。一个C数组(这里称为MyArray)只是一个指向第一个元素的指针:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

如果我们想要查找MyArray[4],内部会像这样访问它:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

因为我们可以通过给指针加上偏移量来直接访问数组中的任何元素,所以不管数组的大小如何,我们都可以在相同的时间内查找到任何元素。这意味着获取MyArray[1000]将花费与获取MyArray[5]相同的时间。

另一种数据结构是链表。这是一个指针的线性列表,每个指针指向下一个节点

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

注意,我将每个“节点”放入自己的块中。这是因为它们在内存中不保证是相邻的(而且很可能不会)。

如果我想访问P3,我不能直接访问它,因为我不知道它在内存中的位置。我所知道的只是根(P1)在哪里,所以我必须从P1开始,并跟随每个指针指向所需的节点。

这是一个O(N)查找时间(随着每个元素的添加,查找成本也会增加)。与P4相比,P1000的成本要高得多。

更高级别的数据结构,如哈希表、堆栈和队列,都可以在内部使用一个数组(或多个数组),而链表和二叉树通常使用节点和指针。

您可能想知道为什么有人会使用需要线性遍历的数据结构来查找值,而不只是使用数组,但它们有自己的用途。

再看我们的数组。这一次,我想找到包含值为'5'的数组元素。

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

在这种情况下,我不知道要给指针加上什么偏移量才能找到它,所以我必须从0开始,一直到找到它。这意味着我要进行6次检查。

因此,在数组中搜索一个值被认为是O(N)。随着数组变大,搜索成本也会增加。

还记得上面我说过有时使用非顺序数据结构有优势吗?搜索数据是这些优点之一,其中一个最好的例子是二叉树。

二叉树是一种类似于链表的数据结构,但不是链接到单个节点,而是每个节点可以链接到两个子节点。

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

当数据被插入到二叉树中时,它会使用一些规则来决定在哪里放置新节点。基本概念是,如果新值大于父值,则将其插入左侧,如果小于父值,则将其插入右侧。

这意味着二叉树中的值可能是这样的:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

当在二叉树中搜索值为75时,我们只需要访问3个节点(O(log N)),因为这样的结构:

75比100小吗?看右节点 75比50大吗?查看左节点 有75个!

尽管我们的树中有5个节点,但我们不需要查看剩下的两个节点,因为我们知道它们(及其子节点)不可能包含我们正在寻找的值。这给了我们一个搜索时间,在最坏的情况下意味着我们必须访问每个节点,但在最好的情况下,我们只需要访问节点的一小部分。

这就是数组被击败的地方,它们提供了一个线性的O(N)搜索时间,尽管有O(1)访问时间。

这是对内存中数据结构的一个非常高级的概述,跳过了许多细节,但希望它说明了与其他数据结构相比,数组的优点和缺点。


不是所有的程序都做同样的事情或在相同的硬件上运行。

这就是为什么存在各种语言特性的原因。数组是计算机科学的一个核心概念。将数组替换为列表/矩阵/向量/任何高级数据结构将严重影响性能,并且在许多系统中是完全不可行的。在许多情况下,由于所讨论的程序,应该使用其中一个“高级”数据收集对象。

在商业编程中(我们大多数人都做),我们可以瞄准相对强大的硬件。在这些情况下,使用c#中的List或Java中的Vector是正确的选择,因为这些结构允许开发人员更快地完成目标,从而使这类软件更具特色。

在编写嵌入式软件或操作系统时,数组通常是更好的选择。虽然数组提供的功能较少,但它占用的RAM较少,而且编译器可以更有效地优化代码以查找数组。

我确信我遗漏了这些情况下的一些好处,但我希望你能明白这一点。


查看数组优势的一种方法是查看数组的O(1)访问能力在哪里是必需的,因此大写:

在应用程序的查找表中(用于访问特定分类响应的静态数组) 记忆(已经计算过复杂函数的结果,这样你就不用再计算函数值了,比如log x) 需要图像处理的高速计算机视觉应用(https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing)