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

Ответ 1

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

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

EDIT: На самом деле, теперь, когда я думаю об этом, это O (K * A), где A - размер "алфавита". Каждый node должен иметь список до дочерних узлов, которые должны быть связанным списком, чтобы реализация не была непрерывной. Но A по-прежнему остается постоянным, поэтому он все еще O (1).

Ответ 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)), независимо от того, какой фантастический алгоритм вы используете.

Ответ 3

Hashtable?

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

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

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

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

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

Ответ 8

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

ИЗМЕНИТЬ:
Забыл немного немного, вы, вероятно, захотите использовать разные хеш-функции для разных уровней, иначе у вас будет много одинаковых значений хэша в каждой области хранения.

Ответ 9

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

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

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

Ответ 10

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

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

Ответ 11

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

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

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

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