Википедия

Массив (тип данных): различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Реализация: стилевые правки, дополнение
Строка 110:
 
== Реализация ==
Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является следующий :
Одним из способов реализации статических массивов с одним типом элементов является следующий (в [[Фортран]]е порядок индексов противоположен таковому в [[Си (язык программирования)|Си]]{{sfn|Бартеньев|2000|сс = 108-112}}):
# Под массив выделяется непрерывный блок памяти объёмом S*m<sub>1</sub>*m<sub>2</sub>*m<sub>3</sub>…m<sub>n</sub>, где S — размер одного элемента, а m<sub>1</sub>…m<sub>n</sub> — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
# При обращении к элементу массива A[i<sub>1</sub>, i<sub>2</sub>, i<sub>3</sub>, …, i<sub>n</sub>] адрес соответствующего элемента вычисляется как B+S*((…(i<sub>1p</sub>*m<sub>1</sub>+i<sub>2p</sub>)*m<sub>2</sub>+…+i<sub>(n-1)p</sub>)*m<sub>n-1</sub>+i<sub>np</sub>), где B — база (адрес начала блока памяти массива), i<sub>kp</sub> — значение k-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. Приведённый соответствует реализации в большинстве компиляторов языка [[Си (язык программирования)|Си]]; в [[Фортран]]е порядок индексов противоположен{{sfn|Бартеньев|2000|сс = 108-112}}).
 
Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково. <small> ''Примечание'': ОсобенностиОдинаковость времени доступа следует понимать как отсутствие теоретической зависимости времени доступа от положения элемента и размера массива. В действительности особенности аппаратной реализации конкретной вычислительной платформы могут дать определённый разброс времени доступа. Например, [[CAS-латентность]] [[ОЗУ]] приводит к увеличению времени доступа к данным, расположенным в другой колонке (странице) ОЗУ, по отношению к предыдущим считанным данным. В практике программирования такими тонкостями обычно пренебрегают, за редчайшими исключениями.</small>
 
Первый элемент массива, в зависимости от [[язык программирования|языка программирования]], может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для [[Низкоуровневый язык программирования|низкоуровневых языков программирования]], однакохотя этотвстречается метод был использовани в языках более высокого уровня, языкомнапример, программированияв том же Си. В ряде языков ([[Паскаль (язык программирования)|Паскаль]], [[Ада (язык программирования)|Ада]], [[Модула-2]]) диапазон индексов может определяться как произвольный диапазон значений любого типа данных, приводимого к целому, то есть целых чисел, символов, перечислений, даже логического типа (в последнем случае массив имеет два элемента, индексируемых значениями «Истина» и «Ложь»).
 
Обычным способом реализации гетерогенных массивов является отдельное хранение самих значений элементов и размещение в блоке памяти массива (организованного как обычный гомогенный массив, описанный выше) указателей на эти элементы. Поскольку указатели на значения любых типов, как правило, имеют один и тот же размер, удаётся сохранить простоту вычисления адреса, хотя возникают дополнительные накладные расходы на размещение значений элементов и обращение к ним.
Более сложные типы массивов — динамические и гетерогенные — реализуются сложнее.
 
Для динамических массивов может использоваться тот же механизм размещения, что и для статических, но с выделением некоторого объёма дополнительной памяти для расширения и добавлении механизмов изменения размера и перемещения содержимого массива в памяти.
 
Также динамические и гетерогенные массивы могут реализовываться путём использования принципиально иных методов хранения значений в памяти, например, одно- или двухсвязных списков. Такие реализации могут быть более гибкими, но требуют, как правило, дополнительных накладных расходов. Кроме того, в них обычно не удаётся выдержать требование константного времени доступа к элементу.
 
== Достоинства ==
Источник — https://ru.wikipedia.org/wiki/Массив_(тип_данных)