[devel] apt virtual packages

[devel] apt virtual packages

[@ 2006-10-09 22:32 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-09 22:41 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-10 0:40 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-10 15:39 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-10 15:52 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-10 22:11 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-11 0:16 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-10-12 9:18 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-07 22:52 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-08 21:27 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-08 21:43 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-08 21:59 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-08 22:01 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-08 22:23 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-13 3:35 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-14 23:40 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-14 23:46 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-14 23:54 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-15 1:25 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-15 13:49 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-15 16:52 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-15 22:27 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-15 22:42 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 12:03 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 20:19 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 21:02 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 21:08 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 21:26 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-16 21:42 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 13:51 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 14:12 UTC (permalink / raw)]

[devel] Papadimitriou

[@ 2006-12-17 16:47 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 16:58 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 17:45 UTC (permalink / raw)]

Re: [devel] [JT] apt virtual packages

[@ 2006-12-17 17:57 UTC (permalink / raw)]

Re: [devel] [JT] apt virtual packages

[@ 2006-12-17 18:13 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 9:58 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 10:02 UTC (permalink / raw)]

Re: [devel] apt virtual packages

[@ 2006-12-17 10:37 UTC (permalink / raw)]

[devel] [PATCH] apt virtual packages

[@ 2006-12-17 13:43 UTC (permalink / raw)]

[devel] gendiff

[@ 2006-12-17 13:46 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 14:14 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 16:09 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 16:15 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 17:05 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 17:17 UTC (permalink / raw)]

Re: [devel] [PATCH] apt virtual packages

[@ 2006-12-17 16:41 UTC (permalink / raw)]

[devel] std::sort

[@ 2006-12-17 16:49 UTC (permalink / raw)]

Re: [devel] std::sort

[@ 2006-12-17 17:15 UTC (permalink / raw)]

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

[@ 2006-12-17 17:54 UTC (permalink / raw)]

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

[@ 2006-12-17 18:06 UTC (permalink / raw)]

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

[@ 2006-12-17 19:42 UTC (permalink / raw)]

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

[@ 2006-12-17 20:01 UTC (permalink / raw)]

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

[@ 2006-12-17 20:33 UTC (permalink / raw)]

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

[@ 2006-12-17 20:18 UTC (permalink / raw)]

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

[Hihin Ruslan]

[-- 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 --]

Re: [devel] [PATCH] apt virtual packages

[Led]

В сообщении от 17 декабря 2006 18:09 Alexey Tourbin написал(a):
> On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> > On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > > +static inline bool
> > > +vercmpOrder(const pkgCache::VerIterator &a, const
> > > pkgCache::VerIterator &b) +{
> > > +   return a.CompareVer(b) < 0;
> > > +}
> >
> > Кстати вот тут должно быть "<" или "<="?
> > Что-то у Страуса примера на сортировку с предикатом порядка нету.
>
> Ага, тут похоже должно быть "<=".  Дело в том, что всего одной операции
> "<=" достаточно, чтобы логически вывести все остальные операции сравнения.
>
> (==)(a,b) := (a<=b)&&(b<=a)
> (>=)(a,b) := !(b<=a)
> (!=)(a,b) := !(a==b)
> (<)(a,b)  := (a<=b)&&(a!=b)
> (>)(a,b)  := (a>=b)&&(a!=b)
>
> А в случае с одной только операцией "<" такой ляпоты не получается,
> потому что не удается логически вывести равенство.

(==)(a,b) := !(a<b)&&!(b<a)

?

-- 
Led.

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Mon, Dec 18, 2006 at 12:39:28PM +0200, Led wrote:
> > А в случае с одной только операцией "<" такой ляпоты не получается,
> > потому что не удается логически вывести равенство.
> 
> (==)(a,b) := !(a<b)&&!(b<a)
> 
> ?

Да.  Я уже исправился и предложил вариант
(a==b) := !((a<b)||(b<a))

который по закону Де Моргана или как его там эквиваленен вашему.

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

Re: [devel] [PATCH] apt virtual packages

[Dmitry V. Levin]

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

On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > +static inline bool
> > +vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
> > +{
> > +   return a.CompareVer(b) < 0;
> > +}
> 
> Кстати вот тут должно быть "<" или "<="?

Для std:: должно быть less.


-- 
ldv

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> Этот патч был неправильным, потому что версии в ProvidesList на самом
> деле не отсортированы.  Вот правильный вариант патча (прицеплен).

В принципе этот патч почти хороший.  То есть его можно брать в очередную
сборку.

Есть другая идея.  В TryToChangeVer можно теперь вызывать не Find(),
который вернет наилучшую версию, а новый FindAll(), и применять к нему
технику &(Fix.ScoreSort).

Ну в общем это техника не совсем родная для апта, она содержится
в apt-0.5.15cnc6-alt-virtual-scores.patch.  Что-то я уже не понимаю что
у апта родное а что кто-то из нас добавил года три назад.

В общем смысл в чем.  Сейчас как происходит: когда просим ставить пакет
без версии, тогда вызывается Fix.ScoreSort.  А когда просим ставить
пакет с версией, тогда уже никакого ScoreSort нет.  Простейший вариант --
при попытке ставить виртуальный или реальный пакет с версией ставить
всегда реальный пакет с наибольшей реальной версией, удовлетворяющей
зависимость по требуемой версиеи.  Это то что сделано в [PATCH].  Второй
вариант -- ввести ScoreSort в TryToChangeVer.

В общем-то по идее НЕ надо делать различия между виртуальными и
реальными пакетам.  Одна и та же зависимость может разрешаться в N
реальных пактов и M виртуальных пакетов.  Тогда что делать?

Я тут думал о теории графов но на самом деле графа-то как такового нет.
Если нельзя однозначно сконструировать матрицу инциденций тогда это уже
не граф.

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