Время вернуться к уроку. Хотя сегодня мы не слишком много думаем об этих вещах в наших модных управляемых языках, они построены на той же основе, поэтому давайте посмотрим, как управляется память в 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) (стоимость поиска увеличивается при добавлении каждого элемента). Добраться до P1000 намного дороже, чем до P4.
Структуры данных более высокого уровня, такие как хеш-таблицы, стеки и очереди, могут все использовать внутренний массив (или несколько массивов), в то время как связанные списки и двоичные деревья обычно используют узлы и указатели.
Вы можете задаться вопросом, почему кто-то использует структуру данных, которая требует линейного обхода, чтобы искать значение, а не просто использовать массив, но у них есть свои применения.
Возьми наш массив снова. На этот раз я хочу найти элемент массива, который содержит значение «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) время доступа.
Это невероятно общий обзор структур данных в памяти, пропускающий множество деталей, но, надеюсь, он демонстрирует силу и слабость массива по сравнению с другими структурами данных.