On Thu, Aug 31, 2006 at 02:48:51AM +0400, Alexey Tourbin wrote:
[...]
> Вот скрипт, который использует топологическую сортировку + вычеркивание
> как в решете Эратосфена.

Боюсь, что для читающей публики нужны комментарии.

> $ cat ./optimize_package_list
> #!/bin/sh -ef
> . tmpdir.sh
> cd $TMPDIR
> rpm -q --qf '[%{REQUIRENAME}\t%{NAME}\n]' -- "$@" >qR
> rpm -q --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- "$@" >qP
> awk '{print$2,$1}' qR |sort -u -k2,2 -k1,1 -o qR
> awk '{print$2,$1}' qP |sort -u -k2,2 -k1,1 -o qP

Зачем так сложно?  Понятно что итератор (REQUIRENAME/PROVIDENAME) должен
быть первым, но зачем переставлять?

sort -u -k1,1 -k2,2 -o qR qR
sort -u -k1,1 -k2,2 -o qP qP

> #head -v qR qP
> join -j 2 -o '1.1 2.1' qR qP |sort -u >p2p

соответственно
join -j 1 -o '1.2 2.2' qR qP |sort -u >p2p
и т.д.

Таким образом, p2p состоит из пар имён пакетов вида
(зависящий,удовлетворяющий)

> tsort p2p >tsorted || [ -s tsorted ]

Может ли быть, чтобы tsort разорвал циклы не самым оптимальным образом?
Может, но это не важно ввиду последующего.

> #head -v p2p tsorted
> set -- `cat tsorted`
> for i in `seq 1 $(($#-1))`; do
>         eval master="\$$i"
>         for j in `seq $((i+1)) $#`; do
>                 eval slave="\$$j"
>                 if grep -qs -Fx "$master $slave" p2p; then
>                         #echo master=$master slave=$slave >&2
>                         echo "$slave"
>                 fi
>         done
> done >extrareq

Не нравится мне эти eval'ы...
Я бы всё же не стал называть зависящий пакет master, а удовлетворяющий
зависимость slave.  Скорее наоборот. :)
Итак, в extrareq попадают (все?) имена пакетов, которые удовлетворяют
хотя бы один зависящий.

> sort -o extrareq -u extrareq
> awk '{print$1}' qR |sort -u >req

req - это имена всех пакетов, у которых есть зависимости.
Поскольку любой пакет имеет какие-нибудь зависимости, хотя бы на
rpmlib(...), это список совпадает с исходным списком.
И всё же я бы сделал этот же самый список на основе qP, воспользовавшись
другим свойством пакетов: всякий пакет предоставляет одноимённый provides.
Или ещё переносимее: rpmquery --qf '%{NAME}\n' -- "$@" >names

> #head -v req extrareq
> comm -23 req extrareq |xargs -r echo
> $

Наконец, из списка имён всех пакетов удаляются имена тех, от которых
зависит хотя бы один.

> У меня пока нет уверенности, что он до конца правильно работает,
> однако "основные проблемы" в нём как будто не проявляются.

Выглядит правильно.


-- 
ldv