Существуют ли O (1) структуры данных с произвольным доступом, которые не зависят от непрерывного хранения?

Question

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

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

Есть ли такая вещь?

Answer 1

Как насчет trie , где длина ключей ограничена некоторой константой K (например, 4 байта, поэтому вы можете использовать 32-битные целые числа в качестве индексов). Тогда время поиска будет O (K), то есть O (1) с несмежной памятью. Кажется разумным для меня.

Вспоминая наши классы сложности, не забывайте, что у каждого big-O есть постоянный коэффициент, то есть O (n) + C. Этот подход, безусловно, будет иметь гораздо больший C, чем реальный массив.

РЕДАКТИРОВАТЬ : На самом деле, теперь, когда я думаю об этом, это O (K * A), где A - это размер "алфавита". Каждый узел должен иметь список до A дочерних узлов, который должен быть связанным списком, чтобы реализация не была непрерывной. Но A по-прежнему постоянен, поэтому он все равно O (1).

Answer 2

На практике для небольших наборов данных использование непрерывного хранилища не является проблемой, а для больших наборов данных O (log (n)) так же хорошо, как O (1); постоянный фактор гораздо важнее.

На самом деле, для ДЕЙСТВИТЕЛЬНО больших наборов данных O (root3 (n)) произвольный доступ - лучшее, что вы можете получить в трехмерной физической вселенной.

Edit: Предполагая, что log10 и алгоритм O (log (n)) в два раза быстрее, чем алгоритм O (1) на миллион элементов, потребуется триллион элементов, чтобы они стали четными, и квинтиллион для алгоритма O (1) стать в два раза быстрее - гораздо больше, чем даже самые большие базы данных в мире.

Все современные и прогнозируемые технологии хранения требуют определенного физического пространства (назовем его v) для хранения каждого элемента данных. В трехмерной вселенной это означает, что для n элементов существует минимальное расстояние root3 (n * v * 3/4 ​​/ pi) между по крайней мере некоторыми элементами и местом, в котором выполняется поиск, потому что это радиус сфера объемом n * v. И затем, скорость света дает физическую нижнюю границу root3 (n * v * 3/4 ​​/ pi) / c для времени доступа к этим элементам - и это O (root3 (n)), независимо от того, какой причудливый алгоритм вы используете.

Answer 3

Таким образом, может быть желательно иметь структуру данных, которая имеет O (1) произвольный доступ, но не полагается на постоянное хранение.

Есть ли такая вещь?

Нет, нет. Эскиз доказательства:

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

Answer 4

Помимо хеш-таблицы, вы можете иметь двухуровневый массив массивов:

• Сохранить первые 10000 элементов в первом подмассиве
• Сохранить следующие 10000 элементов в следующем подмассиве
• и т.д.

Answer 5

Hashtable?

Edit: Массив O(1) lookup, потому что a[i] - это просто синтаксический сахар для *(a+i). Другими словами, чтобы получить O(1), вам нужен либо прямой указатель, либо легко вычисляемый указатель на каждый элемент (вместе с хорошим ощущением, что память, которую вы собираетесь искать, предназначена для вашей программы). При отсутствии указателя на каждый элемент вряд ли будет легко рассчитанный указатель (и мы знаем, что память зарезервирована для вас) без смежной памяти.

Конечно, возможно (если это ужасно) иметь реализацию Hashtable, в которой адрес памяти каждого поиска просто *(a + hash(i)) Не выполняется в массиве, т. Е. Создается динамически в указанной ячейке памяти, если у вас есть такой контроль ... дело в том, что наиболее эффективной реализацией будет базовый массив, но вполне вероятно, что в других местах возможны попадания для реализации WTF, которая все еще дает вам поиск в постоянном времени.

Edit2: Я хочу сказать, что массив опирается на непрерывную память, потому что это синтаксический сахар, но Hashtable выбирает массив, потому что это лучший способ реализации, а не потому, что он требуется . Конечно, я, должно быть, слишком много читаю DailyWTF, так как я представляю, как перегружаю оператор индекса массива в C ++, чтобы делать это без смежной памяти тем же способом.

Answer 6

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

Мне известна интересная и тесно связанная структура данных:

• Cedar веревки являются неизменяемыми строками, которые обеспечивают логарифмический, а не постоянный доступ , но обеспечивают операцию конкатенации в постоянное время и эффективную вставку символов. Статья защищена авторским правом, но есть объяснение Wikipedia .

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

Answer 7

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

Answer 8

Некоторые псевдо O (1) ответы-

A VList - это O (1) доступ (в среднем) и не требует, чтобы все данные были непрерывными, хотя для этого требуется непрерывное хранение в небольших блоках. Другие структуры данных, основанные на числовых представлениях, также амортизируются O (1).

Числовое представление применяет тот же «чит», что и radix sort , что дает структуру доступа O (k) - если есть другая верхняя граница индекса, такая как 64-битная int, тогда двоичное дерево, где каждому уровню соответствует бит в индексе, занимает постоянное время. Конечно, эта константа k больше, чем lnN для любого N, который может использоваться со структурой, поэтому вряд ли это будет повышение производительности (радикальная сортировка может привести к улучшению производительности, если k только немного больше, чем lnN, и реализация радикальная сортировка работает лучше, эксплуатирует платформу).

Если вы используете то же представление двоичного дерева, которое распространено в реализациях кучи, вы в конечном итоге возвращаетесь к массиву.

Answer 9

Немного любопытства: хэш-дерево экономит пространство, чередуя в памяти массивы ключей узлов дерева, которые не сталкиваются. То есть, если узел 1 имеет ключи A, B, D, а узел 2 имеет ключи C, X, Y, Z, например, то вы можете использовать одно и то же непрерывное хранилище для обоих узлов одновременно. Он обобщен на разные смещения и произвольное количество узлов; Кнут использовал это в своей программе наиболее распространенных слов в Грамотное программирование .

Таким образом, это дает O (1) доступ к ключам любого данного узла, не резервируя для него непрерывное хранилище, хотя все вместе используют непрерывное хранилище для всех узлов.

Answer 10

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

Другой вариант: если элементы могут быть идентифицированы с помощью ключей, и эти ключи могут быть однозначно сопоставлены с доступными ячейками памяти, можно не размещать все объекты непрерывно, оставляя пробелы между ними. Это требует контроля над распределением памяти, так что вы все еще можете распределять свободную память и перемещать объекты 2-го прирота в другое место, когда вам нужно использовать это место в памяти для объекта 1-го приоритета. Хотя они все еще были бы смежны в одном измерении.

Могу ли я назвать общую структуру данных, которая отвечает на ваш вопрос? Нет.