Ответ 1
Время возвращаться во времени для урока. Хотя мы не слишком много думаем об этих вещах в наших фантастических управляемых языках, они построены на одном фундаменте, поэтому давайте посмотрим, как управляется память в C.
Прежде чем я погружусь, быстро объясните, что означает термин "указатель". Указатель - это просто переменная, которая "указывает" на местоположение в памяти. Он не содержит фактического значения в этой области памяти, он содержит адрес памяти. Подумайте о блоке памяти как почтовом ящике. Указателем будет адрес этого почтового ящика.
В C массив - это просто указатель со смещением, смещение указывает, как далеко в памяти смотреть. Это обеспечивает время доступа O (1).
MyArray [5]
^ ^
Pointer Offset
Все остальные структуры данных либо основываются на этом, либо не используют смежную память для хранения, что приводит к ухудшению времени поиска в произвольном доступе (хотя есть и другие преимущества, чтобы не использовать последовательную память).
Например, допустим, у нас есть массив с 6 номерами (6,4,2,3,1,5), в памяти он будет выглядеть так:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
В массиве мы знаем, что каждый элемент находится рядом друг с другом в памяти. AC array (Called 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) (затраты на поиск увеличиваются по мере добавления каждого элемента). Гораздо дороже добраться до P1000 по сравнению с получением P4.
Структуры данных более высокого уровня, такие как hashtables, стеки и очереди, могут использовать массив (или несколько массивов) внутри, а Linked Lists и Binary Trees обычно используют узлы и указатели.
Вы можете задаться вопросом, почему кто-то будет использовать структуру данных, которая требует линейного обхода для поиска значения вместо того, чтобы просто использовать массив, но они используют их.
Возьмите наш массив снова. На этот раз я хочу найти элемент массива, который содержит значение "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).
Это невероятно высокий уровень обзора структур данных в памяти, пропуская множество деталей, но, надеюсь, он иллюстрирует силу и слабость массива по сравнению с другими структурами данных.