[devel] оптимизация сборочных зависимостей
Alexey Tourbin
=?iso-8859-1?q?at_=CE=C1_altlinux=2Eru?=
Чт Авг 31 04:27:05 MSD 2006
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. Скорее наоборот. :)
Ну, это дело вкуса, и, на самом деле, метафоры. Я вообразил себе, что
некий Господин держит при себе вниз по списку некоторое количество Рабов.
Причем Господин сам может являться Рабом какого-нибудь более крутого
Господина -- того, что выше по списку. Менеджер среднего звена.
Социальная иерархия. :)
> Выглядит правильно.
Хорошо.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип : application/pgp-signature
Размер : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url : <http://lists.altlinux.org/pipermail/devel/attachments/20060831/650e73ca/attachment-0001.bin>
Подробная информация о списке рассылки Devel