Почему мы используем массивы вместо других структур данных?
Когда я программировал, я не видел ни одного случая, когда массив лучше хранить информацию, чем другая его форма. Я действительно полагал, что добавленные "особенности" в языках программирования улучшили это и тем самым заменили их. Теперь я вижу, что их не заменяют, а дают новую жизнь, так сказать.
Итак, какой смысл использовать массивы?
Это не так много, почему мы используем массивы с точки зрения компьютера, а скорее почему мы будем использовать массивы с точки зрения программирования (небольшая разница). То, что компьютер делает с массивом, не было вопросом вопроса.
4 ответа
Время возвращаться во времени для урока. Хотя сегодня мы не слишком много думаем об этих вещах в наших модных управляемых языках, они построены на одной основе, поэтому давайте посмотрим, как управляется память в C.
Прежде чем я углублюсь, коротко объясню, что означает термин "указатель". Указатель - это просто переменная, которая "указывает" на место в памяти. Он не содержит фактического значения в этой области памяти, он содержит адрес памяти для него. Думайте о блоке памяти как о почтовом ящике. Указатель будет адресом этого почтового ящика.
В C массив - это просто указатель со смещением, смещение указывает, как далеко в памяти искать. Это обеспечивает O(1) время доступа.
MyArray [5]
^ ^
Pointer Offset
Все остальные структуры данных либо основаны на этом, либо не используют смежную память для хранения, что приводит к плохому времени поиска в произвольном доступе (хотя есть и другие преимущества не использования последовательной памяти).
Например, допустим, у нас есть массив с 6 числами (6,4,2,3,1,5), в памяти он будет выглядеть так:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
В массиве мы знаем, что каждый элемент находится рядом друг с другом в памяти. Массив A 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 узлов, нам не нужно было смотреть на оставшиеся два, потому что мы знали, что они (и их дочерние элементы) не могут содержать искомое значение. Это дает нам время поиска, которое в худшем случае означает, что мы должны посетить каждый узел, но в лучшем случае нам нужно посетить только небольшую часть узлов.
That is where arrays get beat, they provide a linear O(N) search time, despite O(1) access time.
This is an incredibly high level overview on data structures in memory, skipping over a lot of details, but hopefully it illustrates an array's strength and weakness compared to other data structures.
Для O(1) произвольный доступ, который не может быть побежден.
Не все программы делают одно и то же или работают на одном и том же оборудовании.
Обычно это ответ, почему существуют различные языковые функции. Массивы являются основной концепцией информатики. Замена массивов списками / матрицами / векторами / любой другой продвинутой структурой данных может серьезно повлиять на производительность и будет практически невыполнима в ряде систем. Существует множество случаев, когда использование одного из этих "продвинутых" объектов сбора данных следует использовать из-за рассматриваемой программы.
В бизнес-программировании (что делает большинство из нас) мы можем ориентироваться на относительно мощное оборудование. Использование List в C# или Vector в Java - правильный выбор в этих ситуациях, потому что эти структуры позволяют разработчику быстрее достигать поставленных целей, что, в свою очередь, делает этот тип программного обеспечения более функциональным.
При написании встроенного программного обеспечения или операционной системы массив часто может быть лучшим выбором. В то время как массив предлагает меньше функциональности, он занимает меньше оперативной памяти, и компилятор может более эффективно оптимизировать код для поиска в массивах.
Я уверен, что упускаю ряд преимуществ для этих случаев, но я надеюсь, что вы поняли суть.
Чтобы взглянуть на преимущества массивов, нужно посмотреть, где требуется возможность доступа к массивам O(1) и, следовательно, с большой буквы:
В справочных таблицах вашего приложения (статический массив для доступа к определенным категориальным ответам)
Заметка (уже вычислены результаты комплексной функции, чтобы вы не вычисляли значение функции снова, скажем, log x)
Высокоскоростные приложения для компьютерного зрения, требующие обработки изображений ( https://en.wikipedia.org/wiki/Lookup_table)