Дан массив в 10^9 элементов, но известно, что одновременно в нем может храниться не более 10^6 (скажем, ненулевые, остальные нули). Элементы могут как добавляться, так и удаляться. Способ хранения с возможностью только добавления я придумал — время доступа O( (log(n))^3 ). А вот с удалением проблемы. Кто-нибудь знает, где можно найти алгоритм и структуру данных? Должны быть относительно быстрыми операции вставки, удаления, присваивания, взятия значения и поиск.
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS> А вот с удалением проблемы. Кто-нибудь знает, где можно найти алгоритм и структуру данных? Должны быть относительно быстрыми операции вставки, удаления, присваивания, взятия значения и поиск.
Хэш-таблица — классическое решение. Пр хорошей хеш-функции все операции получаются достаточно хорошо сбалансированными по времени выполнения. Поиск элемента — в среднем констатное время O(1). Недостаток — значительная дисперсия по времени операций. То есть, скажем, в 99% случаев время доступа — O(1), но для некоторых элементов может сваливаться до O(N). В среднем же гораздо быстрее Binary Search
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Любой ассоциативный контейнер подойдёт. Про хеш-таблицу уже написали. Можно сделать map на сбалансированном дереве (хотя бы std::map), будет O(log n) на любую операцию.
MS> но для некоторых элементов может сваливаться до O(N).
Хм, а как это может произойти?
ИМХО, если у хеша разумный уровень коллизий и размер хеша примерно соответствует числу хранимых элементов, то доступ к элементу всегда должен быть в районе O(1).
Здравствуйте, a18, Вы писали:
a18>ИМХО, если у хеша разумный уровень коллизий и размер хеша примерно соответствует числу хранимых элементов, то доступ к элементу всегда должен быть в районе O(1).
Ну так это при условии, что хеш-значения независимы и равномерно распределены. Но никто не гарантирует, что количество коллизий не станет порядка N.
a18>>ИМХО, если у хеша разумный уровень коллизий и размер хеша примерно соответствует числу хранимых элементов, то доступ к элементу всегда должен быть в районе O(1). Mab>Ну так это при условии, что хеш-значения независимы и равномерно распределены. Но никто не гарантирует, что количество коллизий не станет порядка N.
Мысль ясна. Только, наверное, не N, а, в нашем примере, 10^9/10^6=1000 коллизий на ячейку хеш-таблицы для наихудшего набора данных (если, конечно, хеш хоть сколько-нибудь годный). Но, согласен, даже это немало.
DS>Дан массив в 10^9 элементов, но известно, что одновременно в нем может храниться не более 10^6 (скажем, ненулевые, остальные нули). Элементы могут как добавляться, так и удаляться. Способ хранения с возможностью только добавления я придумал — время доступа O( (log(n))^3 ). А вот с удалением проблемы. Кто-нибудь знает, где можно найти алгоритм и структуру данных? Должны быть относительно быстрыми операции вставки, удаления, присваивания, взятия значения и поиск.
Здравствуйте, a18, Вы писали:
a18>Мысль ясна. Только, наверное, не N, а, в нашем примере, 10^9/10^6=1000 коллизий на ячейку хеш-таблицы для наихудшего набора данных (если, конечно, хеш хоть сколько-нибудь годный). Но, согласен, даже это немало.
Не понял, честно говоря, откуда такая дробь взялась. Коллизия -- это когда совпадают хеши у разных ключей. Вот в худшем случае они все и совпадут.
a18>>Мысль ясна. Только, наверное, не N, а, в нашем примере, 10^9/10^6=1000 коллизий на ячейку хеш-таблицы для наихудшего набора данных (если, конечно, хеш хоть сколько-нибудь годный). Но, согласен, даже это немало. Mab>Не понял, честно говоря, откуда такая дробь взялась. Коллизия -- это когда совпадают хеши у разных ключей. Вот в худшем случае они все и совпадут.
ОК, попробую привести пример:
Задача — представить массив с ключами в виде целых чисел от 0 до 10^9 (ключи влезают в 30 бит), у которого только некоторые (10^6) элементы заполнены единицами, а всё остальные — нули.
В качестве хеш функции возьмём очень упрощённый вариант — 20 бит от ключа (для удобства — пусть это будут старшие биты — с 10-го по 29-й, нумерация с 0).
Соответственно, строим хеш-таблицу в виде массива от 0 до 2^20-1 (чуть больше 1 млн. ячеек).
Теперь пытаемся заполнить эту хеш-таблицу максимально плохими (с точки зрения коллизий) данными. Очевидно, для этого надо брать ключи подряд от 0 и дальше. Ключи 0-1023 дадут одинаковый хеш (0) и попадут в первую ячейку хеш-таблицы, следующая пачка ключей (1024-2047) уже пойдёт во вторую ячейку и т.п.
Т.е. даже для самого худшего набора данных получаем всего примерно 10^3 коллизий в ячейке. Вот это я и имел ввиду.
Конечно, если взять совсем дурацкий хеш (например, который для любого ключа тупо выдаёт 0), то можно догнать число коллизий и до 10^6, но это уже совсем маразм!
