Структура данных

Question

[Dair_Targ]

Подскажите структуру данных, для которой:

• Время вставки: гарантированно O(1) (желательно со скоростью вставки в linked list)
• Время доступа к произвольному элемету по его номеру в списке тоже гарантированно O(1) (желательно со скоростью доступа к элементу массива)

В структуре будут хранится указатели или целые числа. Время работы других операций не имеет значения.

Comments

[mydoom]

O(1) — имеется в виду наихудший случай?

[Dair_Targ]

O(1) — гарантированный случай.

[burdakovd]

Мне кажется это невозможно.

[Eol]

Я тоже склоняюсь к такой мысли…

Answer 1

[MikhailEdoshin]

По-моему, единственный вариант с ожидаемым O(1) — хэш-таблица. Если данные известны, можно подобрать perfect hash function и тогда O(1) будет гарантирован.

Comments

[Eol]

Мм, хэш-таблица даёт возможность поиска по ключу. Что же использовать тут в качестве ключа? Номер в массиве? тогда вставка будет увеличивать все ключи большие этого на 1 — не вариант. Тогда что?

[MikhailEdoshin]

Да вот я тоже перечитал вопрос, вижу, что само значение в качестве ключа использовать вроде как не предполагается, предполагается вроде как вставить и получить некоторый «номер в списке» («номерок» :), по которому затем можно получить обратно значение. Хотя где будет хранится этот «номерок»?

Если так, то можно сделать тупо увеличивающийся массив — сначала выделяем, например, 512 элементов, запоминаем номер следующего пустого (0), при вставке вставляем и сдвигаем указатель на позицию, когда больше вставлять некуда — realloc до 1024 элементов и т. д. Удаление только вот не предусматривается, хотя можно и удаление сделать, со связанным списком пустых элементов.

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

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

Answer 2

[Eol]

Фибоначчиевы кучи?

Comments

[burdakovd]

1) Время их работы амортизировано, а значит некоторые отдельные операции могут быть долгими (автору требуется гарантированное время работы O(1))
2) доступ к произвольному элементу по его номеру в списке — как это реализовать на ФК? «Из коробки» ФК предоставляют только доступ к минимальному элементу.

[Eol]

Хорошо, согласен. Видимо, мне показалось, что я могу организовать доступ с помощью ФК…

Answer 3

[kefiijrw]

ээммм. боюсь опозориться на виду у всего района, но… динамический массив?

Comments

[kefiijrw]

в припадке «боже, что я несу?» убежал читать томик Кормена.
Так вот, второе издание, глава 11 («Хэш-таблицы»), параграф 11.1 («Таблицы с прямой адресации») подтверждает говорит, что «Каждая из приведенных операций [поиск, вставка и удаление] очень быстрая: время их работы равно O(1)».

Но, конечно, всё не так просто, применимость зависит от характера данных. А то фрагментация страшная, уникальность для индексации обеспечить…

Подозреваю, что это совсем не то, что вы искали. Но сам я противоречий условиям вопроса не нашел )

[Dair_Targ]

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

Answer 4

[Artemzr]

Хэш-таблица наверное самый подходящий вариант. Для устранения коллизии заменяйте каждый элемент списком либо делайте открытую адресацию.