Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Добавление элемента в отсортированную структуру.

Riply © (2007-04-11 05:27:00)
Здравствуйте !
Допустим, у нас есть некая структура, отсортированная в соответствии с неким правилом.
Нам надо добавить в нее новый элемент, сохранив сортировку.
Для наглядности возьмем TList.
Добавить элемент можно двумя способами:
1.
List.Add(NewElement);
List.Sort(SortCompare);
2.
Находим индекс для вставки (в соответствии с нашим правилом сортировки)
List.Insert(Index, NewItem);

Допустим, у нас есть List с N элементами, и мы хотим добавить еще M элементов.
Как выбрать, из перечисленных выше способов добавления, наиболее оптимальный
для конкретных значений N и M ?

MBo (2007-04-11 11:56:00) [1]
>А про какую ветку идет речь ?
http://www.delphimaster.ru/cgi-bin/forum.pl?id=1176199472&n=3

Riply (2007-04-11 09:52:00) [2]
Спасибо !
P.S. А про какую ветку идет речь ?

MBo (2007-04-11 09:48:00) [3]
>Думкин
Ну это я извращенно - сначала ответил, потом спросил ;)
А ты сюда не читай, ты туда только читай :)) // © Джент. удачи

Думкин (2007-04-11 08:57:00) [4]
> MBo © (11.04.07 06:24) [5]

Сам и ответил на вопрос, который дал в ветке на сообразительность. :(

MBo (2007-04-11 06:24:00) [5]
Пардон, антитезу забыл дописать
>Если сразу добавлять M, сравнимое с N, то проще просто добавить, затем пересортировать.

Если же M заметно меньше N, то можно отдельно отсортировать эти новые элементы и выполнить слияние сортированных массивов - время O(MLogM +(M+N))~O(N+M)

MBo (2007-04-11 06:13:00) [6]
Решение задачи зависит от порядка N и M.
Если сразу добавлять M, сравнимое с N, то проще просто добавить, затем пересортировать.
Вообще для динамического поддержания сортированного порядка есть специальные структуры данных - например, бинарные деревья (лучше сбалансированные - например, RB или AVL), очереди по приоритетам или кучи (Heap). Они позволяют выполнить операции вставки за O(LogN) времени, в то время как массив или список требует O(N) времени (у массива - на сдвиг, у списка - на поиск).

SlymRO (2007-04-11 05:51:00) [7]
Модификация 2.:
First мы ограничили предыдущим индексом
Но можно и ограничит и Last произведя предварительно поиск и вставку последнего элемента M-

Sort(M);
index:=0;
LastIndex:=FindMinIndex(index,List.Size-1,M[High(M)],List);
List.Insert(M[High(M)],LastIndex);
for i:=Low(M) to High(M)-1 do
begin
index:=FindMinIndex(index,LastIndex,M[i],List);
List.Insert(M[i],index);
end;

SlymRO (2007-04-11 05:44:00) [8]
SlymRO © (11.04.07 5:41) [1]
List.Insert(M[i],Index);

SlymRO (2007-04-11 05:41:00) [9]
1. Сортируем множество M
2. Вставляем M[i] в List по нужному индексу
3. Для нахождения дальнейших индексов за начало списка List брать предыдущий индекс.

//forward declaration
procedure Sort(array or list);
function FindMinIndex(First,Last,Value,List):integer;
//...

Sort(M);
index:=0;
for i:=0 to length(M)-1 do
begin
index:=FindMinIndex(index,List.Size-1,M[i],List);
List.Insert(M[i]);
end;

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »