Почему мы используем массивы вместо других структур данных?

Когда я программировал, я не видел ни одного случая, когда массив лучше хранить информацию, чем другая его форма. Я действительно полагал, что добавленные "особенности" в языках программирования улучшили это и тем самым заменили их. Теперь я вижу, что их не заменяют, а дают новую жизнь, так сказать.

В общем, какой смысл использовать массивы?

Это не так много, почему мы используем массивы с точки зрения компьютера, а скорее почему мы будем использовать массивы с точки зрения программирования (небольшая разница). То, что компьютер делает с массивом, не было вопросом вопроса.

Время возвращаться во времени для урока. Хотя мы сегодня не очень много думаем об этих вещах в наших модных управляемых языках, они построены на одной основе, поэтому давайте посмотрим, как управляется память в C.

Прежде чем я углублюсь, коротко объясню, что означает термин « указатель ». Указатель - это просто переменная, которая «указывает» на место в памяти. Он не содержит фактического значения в этой области памяти, он содержит адрес памяти для него. Думайте о блоке памяти как о почтовом ящике. Указатель будет адресом этого почтового ящика.

В C массив - это просто указатель со смещением, смещение указывает, как далеко в памяти искать. Это обеспечивает O (1) время доступа.

  MyArray   [5]
     ^       ^
  Pointer  Offset

Все остальные структуры данных либо основаны на этом, либо не используют смежную память для хранения, что приводит к плохому времени поиска в произвольном доступе (хотя есть и другие преимущества не использования последовательной памяти).

Например, допустим, у нас есть массив с 6 числами (6,4,2,3,1,5), в памяти он будет выглядеть так:

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

В массиве мы знаем, что каждый элемент находится рядом друг с другом в памяти. Массив AC (называемый 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) время доступа.

Это невероятно общий обзор структур данных в памяти, пропускающий множество деталей, но, надеюсь, он иллюстрирует силу и слабость массива по сравнению с другими структурами данных.

Для O (1) произвольный доступ, который не может быть побежден.

Не все программы делают одно и то же или работают на одном и том же оборудовании.

Обычно это ответ, почему существуют различные языковые функции. Массивы являются основной концепцией информатики. Замена массивов списками / матрицами / векторами / любой другой продвинутой структурой данных может серьезно повлиять на производительность и будет практически невыполнима в ряде систем. Существует множество случаев, когда использование одного из этих «продвинутых» объектов сбора данных следует использовать из-за рассматриваемой программы.

В бизнес-программировании (что делает большинство из нас) мы можем ориентироваться на относительно мощное оборудование. Использование List в C # или Vector в Java - правильный выбор в этих ситуациях, потому что эти структуры позволяют разработчику быстрее достигать поставленных целей, что, в свою очередь, делает этот тип программного обеспечения более функциональным.

При написании встроенного программного обеспечения или операционной системы массив часто может быть лучшим выбором. В то время как массив предлагает меньше функциональности, он занимает меньше оперативной памяти, и компилятор может более эффективно оптимизировать код для поиска в массивах.

Я уверен, что упускаю ряд преимуществ для этих случаев, но я надеюсь, что вы поняли суть.

Чтобы взглянуть на преимущества массивов, нужно посмотреть, где требуется возможность доступа к массивам O (1) и, следовательно, с большой буквы:

1. В справочных таблицах вашего приложения (статический массив для доступа к определенным категориальным ответам)

2. Заметка (уже вычислены результаты сложных функций, чтобы вы не вычисляли значение функции снова, скажем, log x)

3. Высокоскоростные приложения для компьютерного зрения, требующие обработки изображений ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )