Неявные структуры данных: эффективность и особенности реализации.

Введение

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

Определение

Неявная структура данных – это структура с постоянным объемом памяти O(1) сверх теоретической нижней границы, необходимой для хранения информации. Исторически, имплицитная структура данных (и алгоритмы, работающие с ней) определялась как структура, "в которой структурная информация содержится в способе хранения данных, а не задается явно с помощью указателей". Это определение несколько размыто: наиболее строго оно определяется как единый массив, в котором сохраняется только размер (одно число накладных расходов), а более свободно – как структура данных с постоянным объемом накладных расходов (O(1)). Последнее определение сегодня является более распространенным, а еще более широкое понятие структуры данных с непостоянным, но малым объемом накладных расходов o(n) сегодня известно как компактная структура данных, как определено ; ранее она называлась полунеявной.

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

Примеры

Тривиальным примером неявной структуры данных является структура данных массива, которая представляет собой неявную структуру данных для списка и требует лишь постоянных накладных расходов на хранение длины; в отличие от связного списка, который содержит указатель для каждого элемента данных, явно определяющий связь между элементами. Аналогично, строка с завершающим нулем является неявной структурой данных для строки (списка символов). Эти структуры считаются очень простыми, поскольку они являются статическими (только для чтения) и поддерживают только простую операцию итерации по элементам. Несколько проще представлять многомерный массив как единый одномерный массив вместе с его размерностями. Например, массив размером m × n можно представить как список длиной m·n, вместе с числами m и n (вместо одномерного массива указателей на каждый одномерный подмассив). Элементы не обязательно должны быть одного типа, и таблицу данных (список записей) также можно неявно представить в виде плоского (одномерного) списка вместе с длиной каждого поля, при условии, что каждое поле имеет фиксированный размер (то есть можно использовать один размер для каждого поля, а не для каждой записи). Менее тривиальным примером является представление отсортированного списка с помощью отсортированного массива, что позволяет выполнять поиск за логарифмическое время с помощью бинарного поиска. Это отличается от дерева поиска, в частности, двоичного дерева поиска, которое также позволяет выполнять поиск за логарифмическое время, но требует использования указателей. Отсортированный массив эффективен только как статическая структура данных, поскольку изменение списка происходит медленно – в отличие от двоичного дерева поиска – но не требует дополнительных затрат памяти на хранение указателей. Важным примером неявной структуры данных является представление полного двоичного дерева в виде списка, упорядоченного по возрастанию глубины: корень, первый левый потомок, первый правый потомок, первый левый потомок первого левого потомка и так далее. Такое дерево часто встречается, например, в генеалогическом древе заданной глубины, и неявное представление известно как Ahnentafel (таблица предков). Этот подход можно обобщить на неполное двоичное дерево (где последний уровень может быть неполным), что приводит к наиболее известному примеру неявной структуры данных, а именно двоичной куче, которая является неявной структурой данных для очереди с приоритетами. Это более сложный пример, чем предыдущие, поскольку он позволяет выполнять несколько операций и является эффективной динамической структурой данных (поддерживает эффективное изменение данных): не только доступ к вершине, но и вставку и удаление. К более сложным неявным структурам данных относятся бип-кучи (bi parental heap).

A trivial example of an implicit data structure is an array data structure, which is an implicit data structure for a list, and requires only the constant overhead of the length; unlike a linked list, which has a pointer associated with each data element, which explicitly gives the relationship from one element to the next. Similarly, a null terminated string is an implicit data structure for a string (list of characters). These are considered very simple because they are static data structures (read only), and only admit the simple operation of iteration over the elements. Similarly simple is representing a multi dimensional array as a single 1 dimensional array, together with its dimensions. For example, representing an m × n array as a single list of length m·n, together with the numbers m and n (instead of as a 1 dimensional array of pointers to each 1 dimensional subarray). The elements need not be of the same type, and a table of data (a list of records) may similarly be represented implicitly as a flat (1 dimensional) list, together with the length of each field, so long as each field has uniform size (so a single size can be used per field, not per record). A less trivial example is representing a sorted list by a sorted array, which allows search in logarithmic time by binary search. Contrast with a search tree, specifically a binary search tree, which also allows logarithmic time search, but requires pointers. A sorted array is only efficient as a static data structure, as modifying the list is slow – unlike a binary search tree – but does not require the space overhead of a tree. An important example of an implicit data structure is representing a perfect binary tree as a list, in increasing order of depth, so root, first left child, first right child, first left child of first left child, etc. Such a tree occurs notably for an ancestry chart to a given depth, and the implicit representation is known as an Ahnentafel (ancestor table). This can be generalized to a complete binary tree (where the last level may be incomplete), which yields the best known example of an implicit data structure, namely the binary heap, which is an implicit data structure for a priority queue. This is more sophisticated than earlier examples because it allows multiple operations, and is an efficient dynamic data structure (it allows efficient modification of the data): not only top, but also insert and pop. More sophisticated implicit data structures include the beap (bi parental heap).

История

Тривиальные примеры списков или таблиц значений восходят к доисторическим временам, а исторически нетривиальные неявные структуры данных, по крайней мере, относятся к Ahnentafel, который был предложен Михаэлем Эйцингером в 1590 году для использования в генеалогии. В формальной информатике первой неявной структурой данных обычно считается отсортированный список, используемый для бинарного поиска, который был предложен Джоном Маучли в 1946 году в лекциях в Школе Мура – первом в истории наборе лекций, посвященных компьютерной тематике. Бинарная куча была предложена для реализации сортировки кучей. Понятие неявной структуры данных было формализовано в , в рамках представления и анализа бипа.