Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья посвящена структуре на уровне байтового макета. Для абстрактного типа данных см. Тип данных массива . Для других типов массивов см. Массив .

В информатике , в массиве , или просто массив , является структурой данных , состоящей из набора элементов ( значений или переменных ), каждый из которых определяются по меньшей мере одним индексом массива или ключом . Массив хранится таким образом, что положение каждого элемента может быть вычислено из его индексного кортежа с помощью математической формулы. [1] [2] [3] Простейшим типом структуры данных является линейный массив, также называемый одномерным массивом.

Например, массив из 10 32-разрядный (4-байтовые) целочисленных переменных, с индексами от 0 до 9, может быть сохранен в виде 10 слов в адресах памяти 2000, 2004, 2008, ..., 2036, (в шестнадцатеричном формате : 0x7D0, 0x7D4` 0x7D8` ..., 0x7F4) так, чтобы элемент с индексом i имел адрес 2000 + ( i × 4). [4]

Адрес памяти первого элемента массива называется первым адресом, адресом основания или базовым адресом.

Поскольку математическая концепция матрицы может быть представлена ​​в виде двумерной сетки, двумерные массивы также иногда называют матрицами. В некоторых случаях термин «вектор» используется в вычислениях для обозначения массива, хотя кортежи, а не векторы, являются более математически правильным эквивалентом. Таблицы часто реализуются в виде массивов, особенно таблиц поиска ; слово таблица иногда используется как синоним массива .

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

Массивы полезны в основном потому, что индексы элементов могут быть вычислены во время выполнения . Помимо прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольно много элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и использовать одно и то же представление данных. Набор допустимых кортежей индексов и адреса элементов (и, следовательно, формула адресации элементов) обычно, [3] [5], но не всегда, [2] фиксируются, пока используется массив.

Термин « массив» часто используется для обозначения типа данных массива , вида типа данных, предоставляемого большинством языков программирования высокого уровня, который состоит из набора значений или переменных, которые могут быть выбраны одним или несколькими индексами, вычисляемыми во время выполнения. Типы массивов часто реализуются структурами массивов; однако на некоторых языках они могут быть реализованы с помощью хэш-таблиц , связанных списков , деревьев поиска или других структур данных.

Этот термин также используется, особенно в описании алгоритмов , для обозначения ассоциативного массива или «абстрактного массива», теоретической компьютерной модели ( абстрактного типа данных или ADT), предназначенной для захвата основных свойств массивов.

История [ править ]

Первые цифровые компьютеры использовали машинное программирование для создания и доступа к структурам массивов для таблиц данных, векторных и матричных вычислений и для многих других целей. Джон фон Нейман написал первую программу сортировки массивов (сортировка слиянием ) в 1945 году, во время создания первого компьютера с хранимой программой . [6] с. 159 Индексирование массивов первоначально выполнялось самомодифицирующимся кодом , а затем использовалось индексные регистры и косвенная адресация . Некоторые мэйнфреймы, разработанные в 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 · i 1 + c 2 · i 2 +… + c k · i 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 для статически объявленных массивов) элементы в каждой строке хранятся в последовательных позициях, и все элементы строки имеют меньший адрес, чем любой из элементов последовательной строки:

123456789

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

147258369

Для массивов с тремя или более индексами «основной порядок строк» ​​помещает в последовательные позиции любые два элемента, чьи индексные кортежи отличаются только на единицу в последнем индексе. «Старший порядок столбцов» аналогичен первому индексу.

В системах, которые используют кэш процессора или виртуальную память , сканирование массива происходит намного быстрее, если последовательные элементы хранятся в последовательных позициях в памяти, а не разбросаны по частям. Многие алгоритмы, использующие многомерные массивы, будут сканировать их в предсказуемом порядке. Программист (или сложный компилятор) может использовать эту информацию для выбора между разметкой строк или столбцов для каждого массива. Например, при вычислении произведения A · B двух матриц было бы лучше, чтобы A сохранялось в порядке строк, а B - в порядке столбцов.

Изменение размера [ править ]

Основная статья: Динамический массив

Статические массивы имеют фиксированный размер при их создании и, следовательно, не позволяют вставлять или удалять элементы. Однако, выделяя новый массив и копируя в него содержимое старого массива, можно эффективно реализовать динамическую версию массива; см. динамический массив . Если эта операция выполняется нечасто, для вставки в конец массива требуется только амортизированное постоянное время.

Некоторые структуры данных массива не перераспределяют хранилище, но сохраняют счетчик количества используемых элементов массива, называемый счетчиком или размером. Это фактически делает массив динамическим массивом с фиксированным максимальным размером или емкостью; Строки Паскаля являются примерами этого.

Нелинейные формулы [ править ]

Иногда используются более сложные (нелинейные) формулы. Например, для компактного двумерного треугольного массива формула адресации представляет собой полином степени 2.

Эффективность [ править ]

Оба хранят и выбирают постоянное время (детерминированный худший случай) . Массивы занимают линейное ( O ( n )) пространство по количеству содержащихся в них элементов n .

В массиве с размером элемента k и на машине с размером строки кэша B байтов итерация по массиву из n элементов требует минимального предела ( nk / B) пропусков кэша, поскольку его элементы занимают непрерывные области памяти. Это примерно в B / k раз больше, чем количество промахов в кэше, необходимое для доступа к n элементам в случайных ячейках памяти. Как следствие, последовательная итерация по массиву на практике происходит заметно быстрее, чем итерация по многим другим структурам данных, свойство, называемое локальностью ссылки (это, однако, не означает, что использование идеального хеша или тривиального хешавнутри того же (локального) массива не будет даже быстрее - и достижимо за постоянное время ). Библиотеки предоставляют низкоуровневые оптимизированные средства для копирования диапазонов памяти (например, memcpy ), которые можно использовать для перемещения смежных блоков элементов массива значительно быстрее, чем это может быть достигнуто с помощью доступа к отдельным элементам. Ускорение таких оптимизированных подпрограмм зависит от размера элемента массива, архитектуры и реализации.

С точки зрения памяти массивы представляют собой компактные структуры данных без дополнительных затрат на каждый элемент . Могут быть накладные расходы на каждый массив (например, для хранения границ индекса), но это зависит от языка. Также может случиться, что элементы, хранящиеся в массиве, требуют меньше памяти, чем те же элементы, хранящиеся в отдельных переменных, потому что несколько элементов массива могут храниться в одном слове ; такие массивы часто называют упакованными массивами. Крайний (но обычно используемый) случай - это битовый массив , где каждый бит представляет один элемент. Таким образом, один октет может содержать до 256 различных комбинаций до 8 различных условий в наиболее компактной форме.

Доступ к массивам со статически предсказуемыми шаблонами доступа является основным источником параллелизма данных .

Сравнение с другими структурами данных [ править ]

Сравнение структур данных списка
Связанный списокМножествоДинамический массивСбалансированное деревоСписок произвольного доступаДерево хешированных массивов
ИндексированиеΘ ( п )Θ (1)Θ (1)Θ (журнал n)Θ (журнал n) [9]Θ (1)
Вставить / удалить в началеΘ (1)Нет данныхΘ ( п )Θ (журнал n)Θ (1)Θ ( п )
Вставить / удалить в концеΘ (1) когда известен последний элемент ;
Θ ( n ) когда последний элемент неизвестен		Нет данныхΘ (1) с амортизациейΘ (журнал n )Не указано [9]Θ (1) с амортизацией
Вставить / удалить посерединевремя поиска + Θ (1) [10] [11]Нет данныхΘ ( п )Θ (журнал n )Не указано [9]Θ ( п )
Пустое пространство (в среднем)Θ ( п )0Θ ( n ) [12]Θ ( п )Θ ( п )Θ ( √ п )

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

Ассоциативные массивы предоставляют механизм для функций, подобных массиву, без огромных накладных расходов на хранение, когда значения индекса являются разреженными. Например, массив, содержащий значения только с индексами 1 и 2 миллиарда, может выиграть от использования такой структуры. К специализированным ассоциативным массивам с целочисленными ключами относятся массивы Патрисии , массивы Джуди и деревья Ван Эмде Боаса .

Сбалансированные деревья требуют времени O (log n ) для индексированного доступа, но также позволяют вставлять или удалять элементы за время O (log n ), [13] тогда как растущие массивы требуют линейного (Θ ( n )) времени для вставки или удаления элементов за один раз. произвольная позиция.

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

Илифф вектор является альтернативой многомерного массива структуры. Он использует одномерный массив ссылок на массивы на одну размерность меньше. В частности, для двух измерений эта альтернативная структура была бы вектором указателей на векторы, по одному для каждой строки (указатель на c или c ++). Таким образом, доступ к элементу в строке i и столбце j массива A будет осуществляться путем двойной индексации ( A [ i ] [ j ] в типичной записи). Эта альтернативная структура позволяет использовать неровные массивы, где каждая строка может иметь разный размер - или, как правило, допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Он также сохраняет одно умножение (на приращение адреса столбца), заменяя его битовым сдвигом (для индексации

Размер [ править ]

Размерность массива - это количество индексов, необходимых для выбора элемента. Таким образом, если массив рассматривается как функция на множестве возможных комбинаций индексов, это измерение пространства, в котором его домен является дискретным подмножеством. Таким образом, одномерный массив - это список данных, двумерный массив - это прямоугольник данных, [14] трехмерный массив - это блок данных и т. Д.

Это не следует путать с размерностью набора всех матриц с заданным доменом, то есть с количеством элементов в массиве. Например, массив с 5 строками и 4 столбцами является двумерным, но такие матрицы образуют 20-мерное пространство. Точно так же трехмерный вектор может быть представлен одномерным массивом размера три.

См. Также [ править ]

  • Динамический массив
  • Параллельный массив
  • Массив переменной длины
  • Битовый массив
  • Нарезка массива
  • Смещение (информатика)
  • Порядок строк и столбцов
  • Шаг массива

Ссылки [ править ]

  1. ↑ Black, Paul E. (13 ноября 2008 г.). «массив» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 22 августа 2010 года .
  2. ^ a b c d e Бьорн Андрес; Ульрих Кете; Торбен Крегер; Хампрехт (2010). «Гибкие во время выполнения многомерные массивы и представления для C ++ 98 и C ++ 0x». arXiv : 1008.2909 [ cs.DS ].
  3. ^ а б в г Гарсия, Рональд; Ламсдэйн, Эндрю (2005). «MultiArray: библиотека C ++ для универсального программирования с массивами». Программное обеспечение: практика и опыт . 35 (2): 159–188. DOI : 10.1002 / spe.630 . ISSN 0038-0644 . 
  4. ^ Дэвид Р. Ричардсон (2002), Книга о структурах данных. iUniverse, 112 страниц. ISBN 0-595-24039-9 , ISBN 978-0-595-24039-5 .  
  5. ^ a b Велдхёйзен, Тодд Л. (декабрь 1998 г.). Массивы в Blitz ++ (PDF) . Вычисления в объектно-ориентированных параллельных средах. Конспект лекций по информатике. 1505 . Springer Berlin Heidelberg. С. 223–230. DOI : 10.1007 / 3-540-49372-7_24 . ISBN  978-3-540-65387-5. Архивировано из оригинального (PDF) 9 ноября 2016 года.
  6. ^ Дональд Кнут, Искусство компьютерного программирования , т. 3. Эддисон-Уэсли
  7. ^ Леви, Генри М. (1984), Компьютерные системы на основе возможностей , Digital Press, стр. 22, ISBN 9780932376220.
  8. ^ «Примеры кода массива - Функции массива PHP - Код PHP» . http://www.configure-all.com/ : Компьютерное программирование Советы по веб-программированию. Архивировано из оригинального 13 апреля 2011 года . Проверено 8 апреля 2011 года . В большинстве компьютерных языков индекс массива (подсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и так далее. В массиве имен ниже вы можете видеть индексы и значения.
  9. ^ a b c Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Труды Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. DOI : 10.1145 / 224164.224187 .
  10. ^ Основной доклад дня 1 - Бьярн Страуструп: Стиль C ++ 11 на GoingNative 2012 на channel9.msdn.com с 45-й или 44-й минуты
  11. ^ Обработка чисел: почему вы никогда, никогда, НИКОГДА не должны использовать связанный список в своем коде снова на kjellkod.wordpress.com
  12. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF) , Департамент компьютерных наук, Университет Ватерлоо
  13. ^ "Счетные B-деревья" .
  14. ^ "Двумерные массивы \ Processing.org" . processing.org . Дата обращения 1 мая 2020 .