Классическая структура данных произвольного доступа O (1) - это массив. Но массив полагается на используемый язык программирования, поддерживающий гарантированное непрерывное выделение памяти (поскольку массив полагается на возможность взять простое смещение основания для поиска любого элемента).
Это означает, что язык должен иметь семантику относительно того, является ли память непрерывной, а не оставлять это как деталь реализации. Таким образом, может быть желательно иметь структуру данных с произвольным доступом O (1), но не полагающуюся на непрерывное хранение.
Что-то подобное существует?
Я подумал об этом, потому что меня интересует дизайн PL, и я думал о том, что некоторые языки имеют очень точную и очевидную семантику пространства (например, C), а другие нет (я думал о Haskell и утечках пространства, но я не знаю, не указывает ли Haskell или это просто неинтуитивно / сложно)
Хеш-таблица?
Редактировать:
Массив - это поиск по O(1)
, потому что a[i]
- это просто синтаксический сахар для *(a+i)
. Другими словами, чтобы получить O(1)
, вам нужен либо прямой указатель, либо легко вычисляемый указатель на каждый элемент (наряду с хорошим ощущением, что память, которую вы собираетесь искать, предназначена для вашей программы). При отсутствии указателя на каждый элемент у него вряд ли будет легко вычисляемый указатель (и знать, что память зарезервирована для вас) без непрерывной памяти.
Конечно, вполне правдоподобно (хотя и ужасно) иметь реализацию Hashtable, в которой каждый адрес памяти поиска - это просто *(a + hash(i))
, который не выполняется в массиве, то есть динамически создается в указанном месте памяти, если у вас есть такой контроль ... суть в том, что что наиболее эффективной реализацией будет нижележащий массив, но, безусловно, вполне вероятно использовать хиты в другом месте, чтобы реализовать реализацию WTF, которая по-прежнему дает вам поиск в постоянном времени.
Edit2: Я хочу сказать, что массив полагается на непрерывную память, потому что это синтаксический сахар, но Hashtable выбирает массив, потому что это лучший метод реализации, а не потому, что он обязательный. Конечно, я должен слишком много читать DailyWTF, так как я представляю себе перегрузку оператора индекса массива C++, чтобы сделать это таким же образом без непрерывной памяти.
Большинство реализаций по-прежнему используют непрерывное хранилище.
Верно, потому что это проще, но нет причин, по которым он должен быть непрерывным, верно?
Можете ли вы реализовать хеш-таблицу с произвольным доступом O (1) без массива? Другими словами, мне кажется, что хеш-таблица - это способ решить, куда помещать элементы в массив.
Интересное изменение, я не думал о том, чтобы жертвовать непрерывным хранилищем на возможность создавать записи в указанном месте памяти.
Как заядлый читатель DailyWTF, я просто понимаю, что есть несколько способов снять шкуру с кошки, даже если с кошки снимать шкуру не нужно. Проблема с созданием записей в указанном месте заключается в том, что вы знаете, выделили ли вы это конкретное место в памяти или нет ..
Я понимаю, что это было бы WTF'y, но с академической точки зрения я думаю, что интересно, что может быть некоторая эквивалентность между постоянным размером / гарантированной непрерывностью / возможностью выделения в определенном месте.
Распределенные хеш-карты обладают таким свойством. Ну, на самом деле, не совсем так, по сути, хеш-функция сообщает вам, в каком сегменте хранилища искать, там вам, вероятно, придется полагаться на традиционные хеш-карты. Он не полностью покрывает ваши требования, так как список, содержащий области / узлы хранения (в распределенном сценарии), опять же, обычно представляет собой хеш-карту (по сути, превращая ее в хеш-таблицу хеш-таблиц), хотя вы можете использовать другие алгоритм, например если известно количество складских площадей.
Обновлено:
Забыл небольшую деталь, вы, вероятно, захотите использовать разные хеш-функции для разных уровней, иначе вы получите много похожих хеш-значений в каждой области хранения.
Помимо хэш-таблицы, у вас может быть двухуровневый массив массивов:
По сути, именно так они и делают виртуальную память на оборудовании.
И вы можете назвать это основанием системы счисления (ну, таблицы страниц находятся действительно основанием системы счисления)., Даже если оно не такое гибкое :-D
Как насчет три, где длина ключей ограничена некоторым постоянным K (например, 4 байта, поэтому вы можете использовать 32-битные целые числа в качестве индексов). Тогда время поиска будет O (K), то есть O (1) с несмежной памятью. Мне кажется разумным.
Вспоминая наши классы сложности, не забывайте, что каждый большой O имеет постоянный коэффициент, то есть O (n) + C. Этот подход, безусловно, будет иметь намного больший C, чем реальный массив.
РЕДАКТИРОВАТЬ: На самом деле, теперь, когда я думаю об этом, это O (K * A), где A - размер «алфавита». У каждого узла должен быть список до A дочерних узлов, который должен быть связанным списком, чтобы реализация не была смежной. Но A по-прежнему остается постоянным, так что это все еще O (1).
Звучит неплохо. Однако при использовании больших массивов у вас, вероятно, возникнут проблемы с использованием памяти.
Полностью. В конце концов, это действительно "O (1) + C". По сравнению с реальным массивом, я предполагаю, что C здесь немного больше :) С другой стороны, похоже, что он может хорошо работать для разреженных массивов.
Конечно, здесь речь идет не о непрерывном хранилище памяти как таковом, а о возможности индексировать содержащую структуру данных. Обычно динамический массив или список внутренне реализуется как массив указателей с фактическим содержимым каждого элемента в другом месте памяти. Для этого есть ряд причин - не в последнюю очередь то, что это позволяет каждой записи иметь разный размер. Как отмечали другие, большинство реализаций хеш-таблиц также полагаются на индексирование. Я не могу придумать способ реализовать алгоритм O (1), который не полагался бы на индексирование, но это подразумевает, по крайней мере, непрерывную память для индекса.
Можно выделить блок памяти не для всех данных, а только для массива ссылок на части данных. Это приводит к резкому уменьшению увеличивать длины необходимой непрерывной памяти.
Другой вариант: если элементы можно идентифицировать с помощью ключей, и эти ключи могут быть однозначно сопоставлены с доступными ячейками памяти, можно не размещать все объекты вместе, оставляя пробелы между ними. Это требует контроля над распределением памяти, чтобы вы по-прежнему могли распределять свободную память и перемещать объекты 2-й приоритета в другое место, когда вам нужно использовать это место в памяти для вашего объекта 1-го приоритета. Тем не менее, они по-прежнему будут смежными в суб-измерении.
Могу я назвать общую структуру данных, которая отвечает на ваш вопрос? Нет.
Под «увеличением», я полагаю, вы имеете в виду уменьшение? Кстати. C++ std :: deque может быть реализован путем выделения небольших прерывистых фрагментов непрерывной памяти так, как вы описываете.
На практике для небольших наборов данных использование непрерывного хранилища не является проблемой, а для больших наборов данных 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))? Я предполагаю, что это как-то связано с физикой подключения реальных цепей? Ссылка на сайт?
Если каждый отдельный бит занимает постоянное пространство, объем масштабируется как n ** 3. Я полагаю, однако, стоит отметить, что если вы попытаетесь масштабировать это в достаточной степени, вы получите черную дыру. :-)
Помимо очевидных вложенных структур с конечной глубиной, отмеченных другими, мне неизвестна структура данных с описанными вами свойствами. Я разделяю мнение других о том, что с хорошо спроектированной логарифмической структурой данных вы можете иметь несмежную память с быстрым временем доступа к любым данным, которые умещаются в основной памяти.
Мне известна интересная и тесно связанная структура данных:
Эта структура данных достаточно эффективна, чтобы вы могли представить с ее помощью все содержимое большого файла, а реализация достаточно умна, чтобы хранить биты на диске, если они вам не нужны.
Немного любопытства: хеш-три экономит место, чередуя в памяти массивы ключей 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 - запись O () должна учитывать бесконечный рост по определению. Для фиксированного размера данных все равно O (1).
Некоторые ответы псевдо O (1) -
VList - это доступ O (1) (в среднем) и не требует, чтобы все данные были непрерывными, хотя для этого требуется непрерывное хранилище небольшими блоками. Другие структуры данных, основанные на числовых представлениях, также амортизируются O (1).
Числовое представление применяет тот же `` обман '', что и радиксная сортировка, давая структуру доступа O (k) - если есть другая верхняя граница индекса, например, это 64-битное int, тогда двоичное дерево, где каждый уровень соответствует для разряда в индексе требуется постоянное время. Конечно, эта константа k больше, чем lnN для любого N, которое может использоваться со структурой, поэтому это вряд ли будет улучшением производительности (сортировка по основанию может улучшить производительность, если k лишь немного больше lnN и реализация Сортировка по основанию лучше использует платформу).
Если вы используете то же представление двоичного дерева, которое является обычным в реализациях кучи, вы вернетесь в массив.
Классный вопрос. Как и все, я сразу подумал о хэш-таблице и потом, конечно же, понял, что это всего лишь массив ведер. Хм.