Почему мы используем массивы вместо других структур данных?
Когда я программировал, я не встречал случая, когда массив лучше для хранения информации, чем его другая форма. Я действительно полагал, что добавленные «функции» в языках программирования улучшили это и тем самым заменили их. Теперь я вижу, что их не заменяют, а дают новую жизнь, так сказать.
Итак, в чем вообще смысл использования массивов?
Это не столько то, почему мы используем массивы с компьютерной точки зрения, сколько то, почему мы должны использовать массивы с точки зрения программирования (тонкая разница). Вопрос не в том, что делает компьютер с массивом.
Что вы имеете в виду под "другие структуры данных" или "другая форма"? А с какой целью?
Ответы 3
За O (1) произвольный доступ, который невозможно обыграть.
Не могли бы вы уточнить, пожалуйста?
В какой момент? Что такое O (1)? Что такое произвольный доступ? Почему его нельзя победить? Еще один момент?
O (1) произвольный доступ, это O (N), как описано в ответе Холланда?
O (1) означает постоянное время, например, если вы хотите получить элемент массива n-esim, вы просто обращаетесь к нему напрямую через его индексатор (array [n-1]), например, со связанным списком, у вас есть чтобы найти головку, а затем перейти к следующему узлу последовательно n-1 раз, что составляет O (n), линейное время.
Обозначение Big-O описывает, как скорость алгоритма зависит от размера его входных данных. Алгоритм O (n) займет вдвое больше времени, чтобы работать с вдвое большим количеством элементов, и в 8 раз дольше, чтобы работать с 8-кратным количеством элементов. Другими словами, скорость алгоритма O (n) зависит от [продолжение ...]
размер его ввода. O (1) означает, что размер ввода ('n') не влияет на скорость алгоритма, это постоянная скорость независимо от размера ввода.
O (1) произвольный доступ означает, что для любого k требуется постоянное количество времени для доступа к k-му элементу массива, независимо от длины N массива. Когда Холланд ссылается на O (N), он имеет в виду время, необходимое для поиска определенного элемента в массиве, предполагая, что он находится в случайном порядке.
мне нравится ваш ответ, так как он просто объясняет, о чем просили :)
Я вижу ваш O (1) и поднимаю вам O (0).
Я ценю ответы, которые удовлетворяют исходный вопрос с наименьшим количеством слов. Но, если я правильно понимаю, мы говорим о массивах C, а не векторах C++ или Java ArrayLists. Поэтому вы должны добавить, что их размер постоянен и указывается во время компиляции.
Я имею в виду, что есть типы массивов, которые растут динамически, но это совершенно другой вид зверя, чем массивы C. В массивах C нет тех непонятных дорогостоящих операций в фоновом режиме, о которых вы не подозреваете, какими бы редкими они ни были.
Массивы C по сравнению с динамически растущими массивами просто блокируют вас от дорогостоящего неявного роста. Динамические массивы имеют преимущества во всех остальных отношениях, но иногда они могут быть дорогостоящими при вставке, если вы не знаете о функции неявного роста.
@Jason: Доступ к произвольному массиву в лучшем случае физически равен O (log N). Вы можете рассматривать его как O (1), только если вы игнорируете уровень абстракции.
Не все программы делают одно и то же или работают на одном оборудовании.
Обычно это ответ, почему существуют различные языковые функции. Массивы - это основная концепция информатики. Замена массивов списками / матрицами / векторами / любой другой расширенной структурой данных может серьезно повлиять на производительность и быть совершенно невыполнимой в ряде систем. Существует множество случаев, когда использование одного из этих «продвинутых» объектов сбора данных должно использоваться из-за рассматриваемой программы.
В бизнес-программировании (которым занимается большинство из нас) мы можем ориентироваться на относительно мощное оборудование. Использование списка в C# или вектора в Java - правильный выбор в этих ситуациях, потому что эти структуры позволяют разработчику быстрее достигать целей, что, в свою очередь, позволяет сделать этот тип программного обеспечения более функциональным.
При написании встроенного программного обеспечения или операционной системы массив часто может быть лучшим выбором. Хотя массив предлагает меньше функций, он занимает меньше оперативной памяти, и компилятор может более эффективно оптимизировать код для поиска в массивах.
Я уверен, что опускаю ряд преимуществ для этих случаев, но надеюсь, что вы уловили суть.
Как ни странно, в Java вы должны использовать ArrayList (или LinkedList) вместо Vector. Это связано с синхронизацией вектора, что обычно не требует дополнительных затрат.
Чтобы увидеть преимущества массивов, нужно увидеть, где требуется возможность доступа O (1) к массивам и, следовательно, с заглавной буквы:
В справочных таблицах вашего приложения (статический массив для доступа к определенным категориальным ответам)
Мемоизация (уже вычисленные результаты сложной функции, чтобы вы не вычисляли значение функции снова, скажем, log x)
Приложения высокоскоростного компьютерного зрения, требующие обработки изображений (https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing)
Почему бы не подумать о том, что делает компьютер с массивом? У нас есть система нумерации домов, потому что у нас есть улицы ПРЯМОЙ. То же самое и с массивами.