On Thu, Aug 31, 2006 at 03:45:50AM +0400, Dmitry V. Levin wrote:
> > Вот скрипт, который использует топологическую сортировку + вычеркивание
> > как в решете Эратосфена.
[...]
> > 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) должен
> быть первым, но зачем переставлять?

Я не претендую на то, что именно этот скрипт лучше всего выражает идею
"топологическая сортировка + вычеркивание как в решете Эратосфена".
Сейчас просто хочется проверить, продуктивна идея или нет.

Что до перестановки, то таковы мои ментальные особенности как
программиста.  Бинарное отношение мыслится как глагол ("требует" и
"предоставляет"), что фиксирует соответствующий порядок атрибутов
("пакет" "требует" "зависимость" и "пакет" "предоставляет" "зависимость").
Но в реляционной алгебре, действительно, постулируется неупорядоченность
атрибутов (как и неупорядоченность кортежей).  С другой стороны, в
реляционной алгебре у каждого атрибута есть имя и тип, а стандартные
средства UNIX под это не заточены.

(Я с тобой немного обсуждал на конференции, как реализовать реляционную
алгебру на шелле.  Идея в том, что первая строка должна содержать имена
(и, возможно, типы) атрибутов).  Тогда сортировка кортежей реализуется
так: read -r header; echo "$header"; exec sort "$@".  И т.п.  Есть
www.rdb.rpm -- ссылка на статью была в докладе -- и свободная реализация 
nosql, но мне не нравится, как там сделано.)

> > tsort p2p >tsorted || [ -s tsorted ]
> 
> Может ли быть, чтобы tsort разорвал циклы не самым оптимальным образом?
> Может, но это не важно ввиду последующего.

Насколько я понял, 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'ы...

Мне тоже не нравится.  Шелл прекрасно приспособлен к метафоре
"преобразование потока данных", когда для каждой строчки в потоке
выполняется какое-либо действие.  В таких случаях на шелле писать
даже удобнее, чем на перле.  Но вложенные циклы -- чисто императивная
фишка, которая плохо вписывается в "преобразование потока" -- на шелле
это писать плохо.  Может на awk этот цикл надо написать.

Кстати, проверка включения grep'ом тоже не очень-то эффективна.
Допустим, что в списке n=100 пакетов.  Тогда придется выполнить
99+98+...+1 т.е. порядка n^2/2 грепов.  Кажется, это "классическая"
задача -- найти сумму чисел от 1 до 100.  Нужно складывать 0+100 потом
1+99 потом 2+98 и т.д., получится 100*50+50=5050.

> Я бы всё же не стал называть зависящий пакет master, а удовлетворяющий
> зависимость slave.  Скорее наоборот. :)

Ну, это дело вкуса, и, на самом деле, метафоры.  Я вообразил себе, что
некий Господин держит при себе вниз по списку некоторое количество Рабов.
Причем Господин сам может являться Рабом какого-нибудь более крутого
Господина -- того, что выше по списку.  Менеджер среднего звена.
Социальная иерархия. :)

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

Хорошо.