Структура данных для быстрого поиска позиции

Ищем структуру данных, которая логически представляет последовательность элементов с ключами уникальных идентификаторов (для простоты давайте рассмотрим их как строки или, по крайней мере, хешируемые объекты).Каждый элемент может появляться только один раз, пробелов нет, первая позиция - 0.Должны поддерживаться следующие операции (продемонстрированные с однобуквенными строками):---- +: = 0 =: + ---- - добавить элемент с ключом ---- +: = 1 =: + ---- в последовательность со смещением ---- +: = 2 =: + ---- .Естественно, что позиция каждого последующего элемента в последовательности теперь увеличивается на единицу.Пример: ---- +: = 3 =: + -------- +: = 4 =: + ---- - удалить элемент со смещением ---- +: = 5 =: + ---- .Уменьшает позицию каждого элемента позже в последовательности на единицу.Пример: ---- +: = 6 =: + -------- +: = 7 =: + ---- - найти позицию элемента с ключом ---- +: = 8 =: + ---- .---- +: = 9 =: + ----Наивная реализация была бы либо связанным списком, либо массивом.Оба будут давать O (n) ---- +: = 10 =: + ---- , ---- +: = 11 =: + ---- и ---- +: = 12 =:+ ---- .На практике, ---- +: = 13 =: + ---- , вероятно, будет использоваться чаще всего, с ---- +: = 14 =: + ---- и ---- +: =15 =: + ---- происходит достаточно часто, поэтому было бы неплохо не быть линейным (что даст вам простая комбинация hashmap + array /list).В идеальном мире это было бы O (1) ---- +: = 16 =: + ---- , O (log n) ---- +: = 17 =: + ---- /-- +: = 18 =: + ---- , но я действительно подозреваю, что это не сработает с чисто теоретической точки зрения (хотя я не пробовал), поэтому O (log n) ----+: = 19 =: + ---- все равно было бы неплохо.
7 голосов | спросил agnoster 18 PM00000020000004231 2012, 14:58:42

0 ответов


Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132