← →TUser ©
(2008-11-30 07:12)
[40]
>
> Насчёт общего выигрыша в скорости - думаю должен быть, если
> основной массив большой.
>
Зависит от задачи. Конкретно от того, насколько часто тебе надо добавлять элементы, и насколько часто искать новые.
Давай оценивать. Пусть поиск в массиве из N элементов выполняется за k1*logN, а вставка нового элемента - за k2*N. При размерах большого и малого массивов L и S соотвественно это будет занимать у тебя k1*(logS+logL) и k2*S + время на сортировку при объединении массивов. От последнего и бдет зависеть эффективность алгоритма.
← →palva ©
(2008-11-30 09:08)
[41]
> Как вам идея?
Идея хорошая. На подобной идее основано ведение журнала в базе данных, когда изменения вставляются не в основную базу, а добавляются к журналу. Объединение журнала с основной базой можно вести во время простоя системы. Смущает только
> а когда он заполниться
Журнал может заполниться в самое горячее время. И тут вдруг алгоритм подвиснет на пару секунд. В это время должна будет выполняться вставка.
Саму вставку сразу нескольких элементов тоже можно организовать экономнее, чем если бы элементы вставлялись по одному. Вот такие идеи при этом возникают:
Малый массив небольшой, копируем его в другое место, ибо на него будет наползать большой массив в процессе вставки.
Вставку ведем начиная с последнего элемента малого массива.
Ищем место вставки последнего элемента, но сдвигаем нижнюю часть массива не на один элемент а на количество элементов в малом массиве.
Поиск следущего элемента нужно осуществлять в верхней части большого массива, эта часть будет становиться все меньше и меньше, так что на поиске будет экономия.
Перед вставкой очередного элемента для сдвига будет выбираться кусок большого массива до места предыдущей вставки, а величина сдвига каждый раз уменьшается на один элемент. Таким образом общее количество сдвигаемых элементов будет то же самое, что и при однократной вставке первого элемента малого массива, так что здесь тоже будет экономия.
Сдвиги надо делать функцией move, о чем я говорил еще в первых постах.
Поиск по массиву половинным делением и добавление элементов? Найти похожие ветки
← →