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

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

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

Что-то подобное существует?

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

Dave Ray 18.01.2009 23:10

Я подумал об этом, потому что меня интересует дизайн PL, и я думал о том, что некоторые языки имеют очень точную и очевидную семантику пространства (например, C), а другие нет (я думал о Haskell и утечках пространства, но я не знаю, не указывает ли Haskell или это просто неинтуитивно / сложно)

Joseph Garvin 18.01.2009 23:13
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
10
2
5 901
11

Ответы 11

Хеш-таблица?

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

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

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

Большинство реализаций по-прежнему используют непрерывное хранилище.

Jasper Bekkers 18.01.2009 23:02

Верно, потому что это проще, но нет причин, по которым он должен быть непрерывным, верно?

Andrew Coleson 18.01.2009 23:03

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

Joseph Garvin 18.01.2009 23:03

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

Joseph Garvin 18.01.2009 23:20

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

Andrew Coleson 18.01.2009 23:32

Я понимаю, что это было бы WTF'y, но с академической точки зрения я думаю, что интересно, что может быть некоторая эквивалентность между постоянным размером / гарантированной непрерывностью / возможностью выделения в определенном месте.

Joseph Garvin 18.01.2009 23:55

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

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

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

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

По сути, именно так они и делают виртуальную память на оборудовании.

Darius Bacon 18.01.2009 23:11

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

Blaisorblade 19.01.2009 03:52

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

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

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

Звучит неплохо. Однако при использовании больших массивов у вас, вероятно, возникнут проблемы с использованием памяти.

strager 18.01.2009 23:22

Полностью. В конце концов, это действительно "O (1) + C". По сравнению с реальным массивом, я предполагаю, что C здесь немного больше :) С другой стороны, похоже, что он может хорошо работать для разреженных массивов.

Dave Ray 18.01.2009 23:28

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

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

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

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

Под «увеличением», я полагаю, вы имеете в виду уменьшение? Кстати. C++ std :: deque может быть реализован путем выделения небольших прерывистых фрагментов непрерывной памяти так, как вы описываете.

Hrvoje Prgeša 19.01.2009 00:18

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

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

Редактировать: Предполагая, что 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)), независимо от того, какой необычный алгоритм ты используешь.

Почему для огромных наборов данных O (log (n)) так же хорошо? Потому что разница между ним и константой со временем уменьшается? Кроме того, не могли бы вы объяснить часть O (root3 (n))? Я предполагаю, что это как-то связано с физикой подключения реальных цепей? Ссылка на сайт?

Joseph Garvin 19.01.2009 00:24

Если каждый отдельный бит занимает постоянное пространство, объем масштабируется как n ** 3. Я полагаю, однако, стоит отметить, что если вы попытаетесь масштабировать это в достаточной степени, вы получите черную дыру. :-)

Darius Bacon 19.01.2009 00:35

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

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

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

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

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

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

Thus it could be desirable to have a data structure that has O(1) random access, yet doesn't rely on continuous storage.

Is there such a thing?

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

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

ОП никогда не упоминал, что структура данных должна иметь возможность неограниченно расти

Jason S 19.01.2009 17:24

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

Rafał Dowgird 19.01.2009 17:32

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

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

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

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

Другие вопросы по теме