Массив (структура данных)
 | Эта статья нуждается в дополнительных цитатах для проверки . ( сентябрь 2008 г. ) |
В информатике массив состоящая — это структура данных, из набора элементов ( значений или переменных ) одинакового размера памяти, каждый из которых идентифицируется по крайней мере одним массива индексом или ключом . Массив хранится таким образом, что положение каждого элемента можно вычислить по его индексному кортежу с помощью математической формулы. [1] [2] [3] Самый простой тип структуры данных — это линейный массив, также называемый одномерным массивом.
Например, массив из десяти 32-битных (4-байтовых) целочисленных переменных с индексами от 0 до 9 может быть сохранен в виде десяти слов по адресам памяти 2000, 2004, 2008, ..., 2036 (в шестнадцатеричном формате : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) так, чтобы элемент с индексом i имел адрес 2000 + ( i × 4). [4] Адрес памяти первого элемента массива называется первым адресом, основным адресом или базовым адресом.
Поскольку математическую концепцию матрицы можно представить в виде двумерной сетки, двумерные массивы также иногда называют «матрицами». В некоторых случаях термин «вектор» используется в вычислениях для обозначения массива, хотя кортежи, а не векторы, являются более математически правильным эквивалентом. Таблицы часто реализуются в виде массивов, особенно таблиц поиска ; слово «таблица» иногда используется как синоним массива.
Массивы являются одними из старейших и наиболее важных структур данных и используются практически во всех программах. Они также используются для реализации многих других структур данных, таких как списки и строки . Они эффективно используют логику адресации компьютеров. В большинстве современных компьютеров и многих внешних запоминающих устройствах память представляет собой одномерный массив слов, индексами которого являются их адреса. Процессоры , особенно векторные , часто оптимизированы для операций с массивами.
Массивы полезны главным образом потому, что индексы элементов могут быть вычислены во время выполнения . Помимо прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольное количество элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и использовать одно и то же представление данных. Набор допустимых кортежей индексов и адреса элементов (и, следовательно, формула адресации элементов) обычно имеют вид: [3] [5] но не всегда, [2] исправлено, пока массив используется.
Термин «массив» может также относиться к типу данных массива , типу данных , предоставляемому большинством языков программирования высокого уровня , который состоит из набора значений или переменных, которые могут быть выбраны по одному или нескольким индексам, вычисляемым во время выполнения. . Типы массивов часто реализуются структурами массивов; однако в некоторых языках они могут быть реализованы с помощью хеш-таблиц , связанных списков , деревьев поиска или других структур данных.
Этот термин также используется, особенно при описании алгоритмов , для обозначения ассоциативного массива или «абстрактного массива», теоретической модели информатики ( абстрактного типа данных или ADT), предназначенной для отражения основных свойств массивов.
История
[ редактировать ]Первые цифровые компьютеры использовали машинное программирование для создания структур массивов и доступа к ним для таблиц данных, векторных и матричных вычислений и для многих других целей. Джон фон Нейман написал первую программу сортировки массивов ( сортировка слиянием ) в 1945 году, во время создания первого компьютера с хранимой программой . [6] Индексирование массивов первоначально выполнялось с помощью самомодифицирующегося кода , а позже с использованием индексных регистров и косвенной адресации . Некоторые мэйнфреймы, разработанные в 1960-х годах, такие как Burroughs B5000 и его преемники, использовали сегментацию памяти для аппаратной проверки границ индекса. [7]
Языки ассемблера обычно не имеют специальной поддержки массивов, кроме той, которую предоставляет сама машина. Самые ранние языки программирования высокого уровня, включая FORTRAN (1957 г.), Lisp (1958 г.), COBOL (1960 г.) и ALGOL 60 (1960 г.), поддерживали многомерные массивы, как и C (1972 г.). В C++ (1983) существуют шаблоны классов для многомерных массивов, размерность которых фиксируется во время выполнения. [3] [5] а также для гибких во время выполнения массивов. [2]
Приложения
[ редактировать ]Массивы используются для реализации математических векторов и матриц , а также других видов прямоугольных таблиц. Многие базы данных , как маленькие, так и большие, состоят из (или включают в себя) одномерные массивы, элементами которых являются записи .
Массивы используются для реализации других структур данных, таких как списки, кучи , хеш-таблицы , деки , очереди , стеки , строки и VLists. Реализации других структур данных на основе массивов часто просты и экономичны ( неявные структуры данных ), требуют небольших затрат на пространство , но могут иметь низкую сложность пространства, особенно при модификации, по сравнению с древовидными структурами данных (сравните отсортированный массив с дерево поиска ).
Один или несколько больших массивов иногда используются для эмуляции внутрипрограммного динамического распределения памяти , особенно выделения пула памяти . Исторически сложилось так, что иногда это был единственный способ портативного выделения «динамической памяти».
Массивы можно использовать для определения частичного или полного потока управления в программах как компактную альтернативу (в противном случае повторяющимся) множественным IF заявления. В этом контексте они известны как управляющие таблицы и используются вместе со специально созданным интерпретатором, поток управления которого изменяется в соответствии со значениями, содержащимися в массиве. Массив может содержать подпрограмм указатели (или относительные номера подпрограмм, на которые могут воздействовать операторы SWITCH ), которые определяют путь выполнения.
Идентификатор элемента и формулы адресации
[ редактировать ]Когда объекты данных хранятся в массиве, отдельные объекты выбираются по индексу, который обычно представляет собой неотрицательное скалярное целое число . Индексы также называются индексами. Индекс сопоставляет значение массива с хранимым объектом.
Индексировать элементы массива можно тремя способами:
- 0 ( индексация с нуля )
- Первый элемент массива индексируется индексом 0. [8]
- 1 ( индексация по единице )
- Первый элемент массива индексируется индексом 1.
- n ( индексация на основе n )
- Базовый индекс массива может выбираться свободно. Обычно языки программирования, допускающие индексацию на основе n, также допускают отрицательные значения индекса и другие скалярные типы данных, такие как перечисления , или символы, которые могут использоваться в качестве индекса массива.
Использование индексации с отсчетом от нуля является выбором многих влиятельных языков программирования, включая C , Java и Lisp . Это приводит к более простой реализации, где нижний индекс относится к смещению от начальной позиции массива, поэтому первый элемент имеет нулевое смещение.
Массивы могут иметь несколько измерений, поэтому нередко доступ к массиву осуществляется с использованием нескольких индексов. Например, двумерный массив A с тремя строками и четырьмя столбцами может обеспечить доступ к элементу во 2-й строке и 4-м столбце по выражению A[1][3] в случае системы индексации с отсчетом от нуля. Таким образом, для двумерного массива используются два индекса, для трехмерного массива — три, а -мерного массива — n для n .
Количество индексов, необходимых для указания элемента, называется размерностью, размерностью или рангом массива.
В стандартных массивах каждый индекс ограничен определенным диапазоном последовательных целых чисел (или последовательных значений некоторого перечислимого типа ), а адрес элемента вычисляется по «линейной» формуле для индексов.
Одномерные массивы
[ редактировать ]Одномерный массив (или одномерный массив) — это тип линейного массива. Доступ к его элементам включает один индекс, который может представлять индекс строки или столбца.
В качестве примера рассмотрим объявление C int anArrayName[10]; который объявляет одномерный массив из десяти целых чисел. Здесь массив может хранить десять элементов типа int . Этот массив имеет индексы от нуля до девяти. Например, выражения anArrayName[0] и anArrayName[9] являются первым и последним элементами соответственно.
Для вектора с линейной адресацией элемент с индексом i расположен по адресу B + c · i , где B — фиксированный базовый адрес , а c — фиксированная константа, иногда называемая приращением адреса или шагом .
Если действительные индексы элементов начинаются с 0, константа B — это просто адрес первого элемента массива. По этой причине язык программирования C определяет, что индексы массива всегда начинаются с 0; и многие программисты будут называть этот элемент « нулевым », а не «первым».
выбрав соответствующий базовый адрес B. Однако можно выбрать индекс первого элемента , Например, если массив имеет пять элементов, проиндексированных от 1 до 5, и базовый адрес B заменен на B + 30 c , то индексы тех же элементов будут от 31 до 35. Если нумерация не начинается с 0, константа B не может быть адресом какого-либо элемента.
Многомерные массивы
[ редактировать ]Для многомерного массива элемент с индексами i , j будет иметь адрес B + c · i + d · j , где коэффициенты c и d — это приращения адреса строки и столбца соответственно.
В более общем смысле, в k -мерном массиве адрес элемента с индексами i 1 , i 2 , ..., i k равен
- B + c 1 · я 1 + c 2 · я 2 + … + c k · я k .
Например: int a[2][3];
Это означает, что массив a имеет 2 строки и 3 столбца и имеет целочисленный тип. Здесь мы можем хранить 6 элементов, они будут храниться линейно, но начиная с линейной первой строки, а затем продолжая вторую строку. Приведенный выше массив будет сохранен как 11 , 12 , 13 , 21 , 22 , 23 .
Эта формула требует всего k умножений и k сложений для любого массива, который может поместиться в памяти. Более того, если какой-либо коэффициент представляет собой фиксированную степень 2, умножение можно заменить сдвигом битов .
Коэффициенты c k должны быть выбраны так, чтобы каждый допустимый кортеж индекса отображался в адрес отдельного элемента.
Если минимальное допустимое значение для каждого индекса равно 0, то B — это адрес элемента, все индексы которого равны нулю. в одномерном случае, индексы элементов можно изменить, изменив базовый адрес B. Как и Таким образом, если в двумерном массиве строки и столбцы пронумерованы от 1 до 10 и от 1 до 20 соответственно, то замена B на B + c 1 − 3 c 2 приведет к изменению их нумерации с 0 по 9 и с 4 по 23. , соответственно. Воспользовавшись этой функцией, некоторые языки (например, FORTRAN 77) указывают, что индексы массива начинаются с 1, как в математической традиции, в то время как другие языки (например, Fortran 90, Pascal и Algol) позволяют пользователю выбирать минимальное значение для каждого индекса.
Векторы допинга
[ редактировать ]Формула адресации полностью определяется размерностью d , базовым адресом B и приращениями c 1 , c 2 , ..., c k . Часто бывает полезно упаковать эти параметры в запись, называемую дескриптором массива, вектором шага или вектором допинга . [2] [3] Размер каждого элемента, а также минимальное и максимальное значения, разрешенные для каждого индекса, также могут быть включены в вектор привязки. Вектор допинга — это полный дескриптор массива и удобный способ передачи массивов в качестве аргументов процедурам . Многие полезные операции разрезания массива (например, выбор подмассива, замена индексов или изменение направления индексов на противоположное) могут быть выполнены очень эффективно, манипулируя вектором примеси. [2]
Компактные планировки
[ редактировать ]Часто коэффициенты выбираются так, чтобы элементы занимали непрерывную область памяти. Однако в этом нет необходимости. Даже если массивы всегда создаются из смежных элементов, некоторые операции разрезания массива могут создавать из них несмежные подмассивы.
Существует два систематических компактных макета двумерного массива. Например, рассмотрим матрицу
В макете порядка строк (принятом в C для статически объявленных массивов) элементы в каждой строке хранятся в последовательных позициях, и все элементы строки имеют меньший адрес, чем любой из элементов последовательной строки:
1 2 3 4 5 6 7 8 9
В порядке по столбцам (традиционно используемом в Фортране) элементы в каждом столбце расположены последовательно в памяти, и все элементы столбца имеют меньший адрес, чем любой из элементов последовательного столбца:
1 4 7 2 5 8 3 6 9
Для массивов с тремя или более индексами «основной порядок строк» помещает в последовательные позиции любые два элемента, индексные кортежи которых отличаются только на один в последнем индексе. «Основной порядок столбца» аналогичен первому индексу .
В системах, использующих кэш процессора или виртуальную память , сканирование массива происходит намного быстрее, если последовательные элементы хранятся в последовательных позициях в памяти, а не разбросаны по разбросу. Это известно как пространственная локальность, которая представляет собой тип локальности отсчета . Многие алгоритмы, использующие многомерные массивы, сканируют их в предсказуемом порядке. Программист (или сложный компилятор) может использовать эту информацию для выбора между расположением строк или столбцов для каждого массива. Например, при вычислении произведения A · B двух матриц было бы лучше хранить A в порядке строк, а B — в порядке столбцов.
Изменение размера
[ редактировать ]Статические массивы имеют размер, который фиксируется при их создании, и, следовательно, не позволяют вставлять или удалять элементы. Однако, выделив новый массив и скопировав в него содержимое старого массива, можно эффективно реализовать динамическую версию массива; см. динамический массив . Если эта операция выполняется нечасто, вставки в конец массива требуют только амортизированного постоянного времени.
Некоторые структуры данных массива не перераспределяют память, но сохраняют количество используемых элементов массива, называемое счетчиком или размером. Это фактически делает массив динамическим с фиксированным максимальным размером или емкостью; Строки Паскаля являются примером этого.
Нелинейные формулы
[ редактировать ]Иногда используются более сложные (нелинейные) формулы. Например, для компактного двумерного треугольного массива формулой адресации является полином второй степени.
Эффективность
[ редактировать ]И сохранение , и выбор занимают (в худшем детерминированном случае) постоянное время . Массивы занимают линейное ( O ( n )) пространство по количеству элементов n , которые они содержат.
В массиве с размером элемента k и на машине с размером строки кэша B байт итерация по массиву из n элементов требует минимального количества в кэше ( nk промахов /B), поскольку его элементы занимают смежные ячейки памяти. Это примерно в B/ k раз больше, чем количество промахов в кэше, необходимых для доступа к n элементам в случайных ячейках памяти. Как следствие, последовательная итерация по массиву на практике выполняется заметно быстрее, чем итерация по многим другим структурам данных, свойство, называемое локальностью ссылки (однако это не означает, что использование идеального хеша или тривиального хеша в одном и том же (локальном) массиве , не будет еще быстрее - и достижимо за постоянное время ). Библиотеки предоставляют низкоуровневые оптимизированные средства для копирования диапазонов памяти (например, memcpy ), которые можно использовать для перемещения смежных блоков элементов массива значительно быстрее, чем это может быть достигнуто при доступе к отдельным элементам. Ускорение таких оптимизированных процедур зависит от размера элемента массива, архитектуры и реализации.
С точки зрения памяти массивы представляют собой компактные структуры данных без затрат на каждый элемент . Могут существовать дополнительные издержки для каждого массива (например, для хранения границ индекса), но это зависит от языка. Также может случиться так, что элементы, хранящиеся в массиве, требуют меньше памяти, чем те же элементы, хранящиеся в отдельных переменных, поскольку несколько элементов массива могут храниться в одном слове ; такие массивы часто называют упакованными массивами. Крайним (но часто используемым) случаем является битовый массив , где каждый бит представляет один элемент. Таким образом, один октет может содержать до 256 различных комбинаций до 8 различных условий в наиболее компактной форме.
Доступ к массивам со статически предсказуемыми шаблонами доступа является основным источником параллелизма данных .
Сравнение с другими структурами данных
[ редактировать ]| Пик (индекс) | Изменить (вставить или удалить) в… | Лишнее пространство, средний | |||
|---|---|---|---|---|---|
| Начало | Конец | Середина | |||
| Связанный список | Θ( п ) | Я(1) | Θ(1) — известный конечный элемент; Θ( n ), неизвестный конечный элемент | Θ( п ) [9] [10] | Θ( п ) |
| Множество | Я(1) | — | — | — | 0 |
| Динамический массив | Я(1) | Θ( п ) | Θ(1) амортизировано | Θ( п ) | Θ( п ) [11] |
| Сбалансированное дерево | Θ(логарифм n) | Θ(логарифм n) | Θ(логарифм n ) | Θ(логарифм n ) | Θ( п ) |
| произвольного доступа Список | Θ(логарифм n) [12] | Я(1) | — [12] | — [12] | Θ( п ) |
| Дерево хешированного массива | Я(1) | Θ( п ) | Θ(1) амортизировано | Θ( п ) | Θ(√ п ) |
Динамические или расширяемые массивы аналогичны массивам, но добавляют возможность вставки и удаления элементов; добавление и удаление в конце особенно эффективно. Однако они резервируют линейную ( Θ ( n )) дополнительную память, тогда как массивы не резервируют дополнительную память.
Ассоциативные массивы предоставляют механизм для функциональности, подобной массиву, без огромных затрат на хранение, когда значения индекса разрежены. Например, массив, содержащий значения только с индексами 1 и 2 миллиарда, может выиграть от использования такой структуры. К специализированным ассоциативным массивам с целочисленными ключами относятся массивы Патрисии Три , массивы Джуди и деревья Ван Эмде Боаса .
Сбалансированные деревья требуют времени O(log n ) для индексированного доступа, но также позволяют вставлять или удалять элементы за время O(log n ). [13] тогда как растущим массивам требуется линейное (Θ( n )) время для вставки или удаления элементов в произвольной позиции.
Связанные списки позволяют удалять и вставлять посередине в постоянное время, но для индексированного доступа требуется линейное время. Их использование памяти обычно хуже, чем у массивов, но все равно линейно.
Вектор Илиффа является альтернативой многомерной структуре массива. Он использует одномерный массив ссылок на массивы на одно измерение меньше. В частности, для двух измерений эта альтернативная структура будет вектором указателей на векторы, по одному на каждую строку (указатель на c или c++). Таким образом, доступ к элементу в строке i и столбце j массива A будет осуществляться посредством двойной индексации ( A [ i ][ j ] в типичных обозначениях). Эта альтернативная структура допускает неровные массивы , где каждая строка может иметь разный размер или, вообще, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Он также экономит одно умножение (на приращение адреса столбца), заменяя его битовым сдвигом (для индексации вектора указателей строк) и один дополнительный доступ к памяти (выборка адреса строки), что может быть полезно в некоторых архитектурах.
Измерение
[ редактировать ]Размерность . массива — это количество индексов, необходимых для выбора элемента Таким образом, если массив рассматривается как функция набора возможных комбинаций индексов, это размерность пространства, дискретным подмножеством которого является его область определения. Таким образом, одномерный массив представляет собой список данных, двумерный массив — это прямоугольник данных. [14] трехмерный массив, блок данных и т. д.
Не следует путать это с размерностью множества всех матриц с заданным доменом, то есть количеством элементов в массиве. Например, массив из 5 строк и 4 столбцов является двумерным, но такие матрицы образуют 20-мерное пространство. Аналогично трехмерный вектор может быть представлен одномерным массивом размера три.
См. также
[ редактировать ]
Ссылки
[ редактировать ]- ^ Блэк, Пол Э. (13 ноября 2008 г.). "множество" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 22 августа 2010 г.
- ^ Перейти обратно: а б с д и Бьорн Андрес; Ульрих Кете; Торбен Крюгер; Хампрехт (2010). «Гибкие многомерные массивы и представления во время выполнения для C++98 и C++0x». arXiv : 1008.2909 [ cs.DS ].
- ^ Перейти обратно: а б с д Гарсия, Рональд; Ламсдейн, Эндрю (2005). «MultiArray: библиотека C++ для универсального программирования с массивами». Программное обеспечение: практика и опыт . 35 (2): 159–188. дои : 10.1002/спе.630 . ISSN 0038-0644 . S2CID 10890293 .
- ^ Дэвид Р. Ричардсон (2002), Книга о структурах данных. iUniverse, 112 страниц. ISBN 0-595-24039-9 , ISBN 978-0-595-24039-5 .
- ^ Перейти обратно: а б Вельдхейзен, Тодд Л. (декабрь 1998 г.). Массивы в Blitz++ . Вычисления в объектно-ориентированных параллельных средах. Конспекты лекций по информатике. Том. 1505. Берлин: Шпрингер. стр. 223–230. дои : 10.1007/3-540-49372-7_24 . ISBN 978-3-540-65387-5 . [ мертвая ссылка ]
- ^ Кнут, Дональд (1998). Сортировка и поиск . Искусство компьютерного программирования . Том. 3. Ридинг, Массачусетс: Addison-Wesley Professional. п. 159.
- ^ Леви, Генри М. (1984), Компьютерные системы, основанные на возможностях , Digital Press, стр. 22, ISBN 9780932376220 .
- ^ «Примеры кода массива — Функции массива PHP — Код PHP» . Компьютерное программирование. Советы по веб-программированию. Архивировано из оригинала 13 апреля 2011 года . Проверено 8 апреля 2011 г.
В большинстве компьютерных языков индекс массива (отсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и так далее. В массиве имен ниже вы можете увидеть индексы и значения.
- ^ Основной доклад дня 1 — Бьерн Страуструп: Стиль C++11 на GoingNative 2012 на канале Channel9.msdn.com с 45-й минуты или с 44-й минуты.
- ^ Обработка чисел: почему вы никогда и НИКОГДА не должны снова использовать связанный список в своем коде на kjellkod.wordpress.com
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , факультет компьютерных наук, Университет Ватерлоо
- ^ Перейти обратно: а б с Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы седьмой международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. дои : 10.1145/224164.224187 .
- ^ «Считанные B-деревья» .
- ^ «Двумерные массивы \ Processing.org» . обработка.орг . Проверено 1 мая 2020 г.
Внешние ссылки
[ редактировать ]
Структуры данных/массивы в Wikibooks
| Базы данных органов управления : Национальные |
|---|
