在编程过程中,我还没有看到数组比另一种形式的数组更适合存储信息的实例。我确实认为,编程语言中添加的“特性”已经在此基础上进行了改进,并取代了它们。我现在明白了,它们并没有被取代,而是被赋予了新的生命。
那么,使用数组的意义是什么呢?
这并不是我们为什么要从计算机的角度使用数组,而是我们为什么要从编程的角度使用数组(一个微妙的区别)。计算机对数组做什么并不是问题的重点。
在编程过程中,我还没有看到数组比另一种形式的数组更适合存储信息的实例。我确实认为,编程语言中添加的“特性”已经在此基础上进行了改进,并取代了它们。我现在明白了,它们并没有被取代,而是被赋予了新的生命。
那么,使用数组的意义是什么呢?
这并不是我们为什么要从计算机的角度使用数组,而是我们为什么要从编程的角度使用数组(一个微妙的区别)。计算机对数组做什么并不是问题的重点。
是时候回到过去上课了。虽然我们在今天的高级托管语言中没有过多地考虑这些事情,但它们都建立在相同的基础上,因此让我们看看在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)