Re: [devel] [JT] std::sort

[Hihin Ruslan <ruslandh@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 3175 bytes --]

Здравствуйте Alex V. Myltsev
  В сообщении от Sunday 17 December 2006 23:18 Alex V. Myltsev 
написал(a):
 > On Sun, 17 Dec 2006 22:42:52 +0300 Hihin Ruslan wrote:
 > >  > подают нам на вход последовательность {a,c,d,b,e}; она
 > >  > неупорядочена, а   сравнением соседних элементов мы этого
 > >  > обнаружить не можем. И  сортировка вся идёт лесом.
  > > Как это не парадоксально,  но если читать что несравнимость - это
  > > один из видов равенства, то можно упорядочить в - вашем примере
  > Конечно, можно. Это же частичный порядок, никто не мешает его
  > доопределить %-).
 >
 > > В общем имеем ситуацию сортировки элементов графа
  > Угу. И что-то подсказывает мне, что это дольше, чем сортировка
  > множества с полным порядком
 Упрощённо имеем :
Множество пакетов A(a1),B(a2),C(a3)...N(an), 
A1(b1),B1(b2),...N1(bn), ......Z1(z1),Z2(z2),...ZN(zn), 
где a...z - характеристика ветки, 
     1..n -  вес пакета в ветке
     A...ZN - имя пакета:
Имеются следующие отношения между пакетами 
Наследования A<B, если характеристика ветки у них совпадает и вес пакета 
в ветке у пакета A < веса пакета в ветке у пакета B 
A=B - пакеты не соизмеримы (характеристика веток не совпадает).

Каждый пакет A несёт в себе информацию о пакетах от которых он зависит, 
т.е. если пакет A имеет характеристику веток A(a4,b3,...zn), то он 
несёт в себе перечень пакетов (имена B,C...N) с характеристиками веток 
a3,b2,..z(n-1)

Имеем неупорядоченное множество пакетов {A,....Z}
Выбираем первый пакет (A) и определяем пакты - родители пакета A,
пусть это будут RA1, RA2 .. RAN, пере-упорядочиваем множество :
{RA1, RA2.. RAN, A,..... Z}, теперь выбираем элемент множества RA1 и 
ставим перед ним всех его родителей и т.д. в результате вытягиваем всех 
предков пакета A. Аналогично разбираемся с пакетами B и т.д. Если 
оказывается, что пакет F, имеет родителем уже рассмотренный пакет. 
например RB3, то он ставится после пакета RB3, а все родители пакета F 
находящиеся пока справа от него, перемещаются налево от него и по ним 
тоже происходит сортировка, после чего сортировка возвращается к 
элементу, следовавшему за F (пусть будет E).
   
  > , которая чаще всего нужна на практике.
 Правильнее сказать - её алгоритм проще, а вот насчёт того, что 
сортировка графов дольше - это неверно, наоборот сортировка множества 
дольше, т.к. в нём не учитывается, что в самих пакетах уже есть 
информация о пакетах - родителях и приходится путём перебора 
их "отсеивать".
  > Поэтому и появилось в STL упомянутое требование. (А те, кому
  > действительно нужно сортировать графы, могут написать собственный
  > sort.)
Вообще-то есть tsort, правда я не разбирался как он работает, но в RPM 
он есть, во всяком случае в исходниках RPM лежит программка rpmsort 
(опять-же подробно не смотрел её код). Насколько я знаю алгоритм 
сортировки графов подробно рассмотрен в одном из томов Кнут (в юности 
читал, но сам том с сортировкой у меня не сохранился).

http://homepages.compuserve.de/chasluebeck/lipsky2.htm
http://algolist.manual.ru/sort/

 > (Мне кажется, продолжать тему в этом направлении можно только в
 > smoke-room.)
Ну извините, я заканчиваю на этом :)

-- 
С уважением Xихин Руслан

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]