Неявная структура данных

В информатике неявная структура данных или структура данных с эффективным использованием пространства — это структура данных , которая хранит очень мало информации, кроме основных или необходимых данных: структура данных, требующая низких накладных расходов . Их называют «неявными», потому что положение элементов несет в себе смысл и связь между элементами; это контрастирует с использованием указателей для явной связи между элементами. Определения «низких накладных расходов» различаются, но обычно означают постоянные накладные расходы; в большом обозначении O , O (1) накладных расходов. Менее строгое определение — это краткая структура данных , которая допускает большие накладные расходы.

Определение

Неявная структура данных — это структура с постоянными $издержками пространства O (1)$ (выше нижней границы теории информации ).

Исторически Манро и Суванда (1980) определяли неявную структуру данных (и алгоритмы, действующие на нее) как структуру, «в которой структурная информация является неявной в способе хранения данных, а не явной в указателях». Они несколько расплывчаты в определении, наиболее строго определяя его как единый массив, сохраняя только размер (единственное число служебных данных). ^[1] или, более свободно, как структура данных с постоянными издержками ( $O (1)$ ). ^[2] Это последнее определение сегодня является более стандартным, а еще более широкое понятие структуры данных с непостоянными, но небольшими $накладными расходами o (n)$ сегодня известно как краткая структура данных , как это определено Джейкобсоном (1988) ; назвали его полунеявным Манро и Суванда (1980) . ^[3]

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

Примеры

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

Столь же просто представить многомерный массив как один одномерный массив вместе с его размерностями. Например, представление массива m × n в виде одного списка длиной m·n вместе с числами m и n (вместо одномерного массива указателей на каждый одномерный подмассив). Элементы не обязательно должны быть одного и того же типа, и таблица данных (список записей ) аналогичным образом может быть неявно представлена в виде плоского (1-мерного) списка вместе с длиной каждого поля , при условии, что каждое поле имеет единый размер (поэтому один размер можно использовать для каждого поля, а не для каждой записи).

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

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

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

Более сложные неявные структуры данных включают beap (двойную кучу).

История

Тривиальные примеры списков или таблиц значений относятся к доисторическим временам, тогда как исторически нетривиальные неявные структуры данных относятся, по крайней мере, к Анентафелю, который был введен Михаэлем Эйтцингером в 1590 году для использования в генеалогии. В формальной информатике первой неявной структурой данных обычно считается отсортированный список, используемый для двоичного поиска, который был представлен Джоном Мочли в 1946 году в « Лекциях Школы Мура» , первом в истории наборе лекций, посвященных любой компьютерной тематике. тема. ^[4]^[5] Бинарная куча была введена Уильямсом (1964) для реализации пирамидальной сортировки . ^[5] Понятие неявной структуры данных было формализовано в работе Munro & Suwanda (1980) как часть введения и анализа beap . ^[5]

Ссылки

^ «Таким образом, для данных нужен только простой массив.», стр. 236; «Мы не будем проводить формального различия между указателем и целым числом (индексом) в диапазоне $[0,N]$ . В этом случае структура данных является неявной, если единственным таким целым числом, которое необходимо сохранить, является само N. ", стр. 238.
^ «... можно было бы предпочесть разрешить сохранение постоянного количества указателей и при этом обозначить структуру как неявную.», стр. 238
^ переменная, но o ( N «Мы также предложим две структуры, которые можно описать как «полу-неявные», поскольку сохраняется ), количество указателей (индексов).», стр. 238
^ Кнут 1998 , §6.2.1 («Поиск в упорядоченной таблице»), подраздел «История и библиография».
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Франческини, Джанни; Манро, Дж. Ян (2006). Неявные словари с O (1) модификациями на обновление и быстрым поиском . Семнадцатый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Майами, Флорида, США. стр. 404–413. дои : 10.1145/1109557.1109603 .

Джейкобсон, Дж. Дж. (1988). Краткие статические структуры данных (доктор философии). Питтсбург, Пенсильвания: Университет Карнеги-Меллон.
Кнут, Дональд (1998). Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN 978-0-201-89685-5 .
Манро, Дж. Ян ; Суванда, Хендра (октябрь 1980 г.). «Неявные структуры данных для быстрого поиска и обновления» . Журнал компьютерных и системных наук . 21 (2): 236–250. дои : 10.1016/0022-0000(80)90037-9 .
Уильямс, JWJ (июнь 1964 г.). «Алгоритм 232 — пирамидальная сортировка». Коммуникации АКМ . 7 (6): 347–348. дои : 10.1145/512274.512284 .

Дальнейшее чтение

См. публикации Эрве Брённимана , Дж. Яна Манро и Грега Фредериксона .

[1] «Таким образом, для данных нужен только простой массив.», стр. 236; «Мы не будем проводить формального различия между указателем и целым числом (индексом) в диапазоне $[0,N]$ . В этом случае структура данных является неявной, если единственным таким целым числом, которое необходимо сохранить, является само N. ", стр. 238.

[2] «... можно было бы предпочесть разрешить сохранение постоянного количества указателей и при этом обозначить структуру как неявную.», стр. 238

[3] переменная, но o ( N «Мы также предложим две структуры, которые можно описать как «полу-неявные», поскольку сохраняется ), количество указателей (индексов).», стр. 238

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-4] Кнут 1998 , §6.2.1 («Поиск в упорядоченной таблице»), подраздел «История и библиография».

[FranceschiniMunro2006-5] Перейти обратно: Перейти обратно: ^а ^б ^с Франческини, Джанни; Манро, Дж. Ян (2006). Неявные словари с O (1) модификациями на обновление и быстрым поиском . Семнадцатый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Майами, Флорида, США. стр. 404–413. дои : 10.1145/1109557.1109603 .

[1]

[2]

[3]

[4]

[5]