Скачать: CL | DM;

Поиск по массиву половинным делением и добавление элементов?   Найти похожие ветки 

← →
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, о чем я говорил еще в первых постах.

---

Страницы: 1 2 вся ветка

Скачать: CL | DM;



Память: 0.52 MB
Время: 0.012 c