Неявная структура данных - Implicit data structure

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

Определение

Формально неявная структура данных - это структура с постоянным О(1) пространство над головой (над теоретико-информационный нижняя граница).

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

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

Примеры

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

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

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

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

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

Более сложные неявные структуры данных включают брякнуть (би-родительская куча).

История

Тривиальные примеры списков или таблиц значений относятся к доисторическим временам, в то время как исторически нетривиальные неявные структуры данных относятся, по крайней мере, к Ahnentafel, который был введен Микаэль Эйтцингер в 1590 г. для использования в генеалогии. В формальной информатике первой неявной структурой данных обычно считается отсортированный список, используемый для двоичного поиска, который был введен Джон Мочли в 1946 г. Лекции в школе Мура, первый в истории набор лекций по любой компьютерной теме.[4][5] Бинарная куча была представлена ​​в Уильямс (1964) реализовать heapsort.[5] Понятие неявной структуры данных было формализовано в Манро и Суванда (1980), как часть введения и анализа брякнуть.[5]

Смотрите также

Рекомендации

  1. ^ «Таким образом, для данных нужен только простой массив», с. 236; "Мы не будем проводить формального различия между указателем и целым числом (индексом) в диапазоне . В этом случае структура данных является неявной, если единственное такое целое число, которое необходимо сохранить, - это N Сама. ", стр. 238
  2. ^ «... можно предпочесть разрешить сохранение постоянного числа указателей и при этом обозначить структуру как неявную», с. 238
  3. ^ «Мы также предложим две структуры, которые можно описать как« полунявные », в которых переменная, но о(N), количество указателей (индексов) сохраняется. ", с. 238
  4. ^ Кнут 1998, §6.2.1 («Поиск в упорядоченной таблице»), подраздел «История и библиография».
  5. ^ а б c Франческини, Джанни; Манро, Дж. Ян (2006). Неявные словари с О(1) модификации за обновление и быстрый поиск. Семнадцатый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Майами, Флорида, США. С. 404–413. Дои:10.1145/1109557.1109603.
  • Манро, Дж. Ян; Суванда, Хендра (октябрь 1980 г.). «Неявные структуры данных для быстрого поиска и обновления». Журнал компьютерных и системных наук. 21 (2): 236–250. Дои:10.1016/0022-0000(80)90037-9.CS1 maint: ref = harv (связь)
  • Джейкобсон, Дж. Дж (1988). Краткие статические структуры данных (Кандидат наук.). Питтсбург, Пенсильвания: Университет Карнеги-Меллона.CS1 maint: ref = harv (связь)

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

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