Структура данных для обработки требования следующего прецедента

-2

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

все записи в линейном режиме (массив или связанный список является наиболее эффективной структуры данных для этого сценария для доступа в O (N) времени)
извлечения запись путем предоставления ключа (хэш-таблица может быть реализована для индексации ее в сложности O (1))
Получить набор записей для значения в конкретном байте в ключе. Пример: список всех записей, для которых 2-й номер (10-е место) в ключении должен быть 5, а если ключи 256, 1452, 362, 874, должны быть возвращены записи для ключей, 256 и 1452

источник

2012-02-08 Mike

Ваше третье требование не ясности.Для какого второго номера должно быть 5? – ggreiner

Я не понимаю, что такое 3. предполагается. Можете ли вы привести пример? Кроме того, зачем вам это нужно? Это домашнее задание? – svick

Это для моего любимого проекта, и я прошел мимо, чтобы сделать домашнее задание – Mike

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

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

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

источник

2012-02-08 06:32:28

Но его требования говорят «Получить набор записей для значения в конкретном байте в ключе». Как минимум (используя вашу идею) вам понадобится дерево для каждой возможной позиции цифр (например, дерево 1, дерево 10 деревьев, дерево 100 и т. Д.) –

@JimMischel: Предыдущие выпуски вопроса рассматривались только в 5 с в десятках , –

Для 1 и 2, я думаю, Linked Hash Map - хороший выбор.

Для точки 3 дополнительная карта хэширования с (цифрой, положением) кортежем как ключ и список указателей на значения.

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

источник

2012-02-09 11:29:57 m0skit0

Мне интересно, как именно это поможет получить записи, введенные с помощью (цифры, позиции) кортежа, пункт 3 в вопросе. Я думал, что LHM - это просто связанный список с хэшмапом - был ли я неправ? – kkm

Получение всех ключей и проверка их? Довольно медленно. Вы можете создать дополнительную структуру данных, которая содержит этот кортеж, и использовать ее в качестве дополнительного ключа. – m0skit0

Я предполагаю, что ключи не более d цифр (в десятичной форме).

Как насчет обычной хэш-таблицы и дополнительного 10-мерного массива (назовем это А) множеств. A [i] [j] - это набор ключей, которые имеют цифру i в j-ой позиции. Множества могут поддерживать O (1) insert/delete, если они реализованы как hashtables.

источник

2012-02-09 12:37:33 aelguindy

Храните ключи в trie. Для чисел в вашем примере (предполагается, что 4-значные номера) это выглядит следующим образом:

*root* 
| 
0 -- 2 - 5 - 6 
| | 
| +- 3 - 6 - 2 
| | 
| +- 8 - 7 - 4 
| 
1 - 4 - 5 - 2

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

источник

2012-02-09 13:52:21 gcbenison

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

Но O (N) может быть достаточно быстрым. Сколько элементов находится в вашем наборе данных и как часто вы будете выполнять эту третью функцию?

источник

2012-02-10 00:27:01

Структура данных для обработки требования следующего прецедента

ответ

Смежные вопросы