ALT Linux Team development discussions
 help / color / mirror / Atom feed
From: Alexey Tourbin <at@altlinux.ru>
To: ALT Devel discussion list <devel@lists.altlinux.org>
Subject: Re: [devel] оптимизация сборочных зависимостей
Date: Thu, 31 Aug 2006 04:27:05 +0400
Message-ID: <20060831002704.GK11420@localhost.localdomain> (raw)
In-Reply-To: <20060830234550.GA16902@basalt.office.altlinux.org>

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

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.  Скорее наоборот. :)

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

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

Хорошо.

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

  reply	other threads:[~2006-08-31  0:27 UTC|newest]

Thread overview: 72+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2006-08-30 14:58 [devel] libpixman Alexey Tourbin
2006-08-30 15:01 ` Dmitry V. Levin
2006-08-30 15:10   ` Alexey Tourbin
2006-08-30 15:20     ` Valery V. Inozemtsev
2006-08-30 15:29     ` Dmitry V. Levin
2006-08-30 15:36       ` Valery V. Inozemtsev
2006-08-30 15:41         ` Dmitry V. Levin
2006-08-30 16:00       ` Alexey Tourbin
2006-08-30 16:10         ` [devel] оптимизация сборочных зависимостей Dmitry V. Levin
2006-08-30 16:28           ` Alexey Tourbin
2006-08-30 16:43             ` Dmitry V. Levin
2006-08-30 18:30               ` Alexey Tourbin
2006-08-30 20:12               ` Sergey Vlasov
2006-08-30 21:01                 ` Alexey Tourbin
2006-08-30 22:48                   ` Alexey Tourbin
2006-08-30 23:19                     ` Alexey Tourbin
2006-08-31  0:17                       ` Денис Смирнов
2006-08-31  4:05                       ` Alexey Tourbin
2006-09-05 13:10                         ` [devel] оптимизация сборочных зависимостей (buildreq) Ildar Mulyukov
2006-09-05 13:48                           ` Alexey Tourbin
2006-09-05 14:57                             ` Ildar Mulyukov
2006-09-05 18:15                           ` Michael Shigorin
2006-09-05 19:08                             ` Alexey Tourbin
2006-09-05 19:15                               ` Michael Shigorin
2006-09-06  4:06                                 ` Ildar Mulyukov
2006-08-30 23:45                     ` [devel] оптимизация сборочных зависимостей Dmitry V. Levin
2006-08-31  0:27                       ` Alexey Tourbin [this message]
2006-08-31  0:59                         ` Alexey Tourbin
2006-09-02 16:34                         ` Michael Shigorin
2006-09-03  2:12                           ` Alexey Tourbin
2006-08-30 19:07           ` Alexey Tourbin
2006-08-30 20:29           ` Alexey Tourbin
2006-08-30 20:57             ` Damir Shayhutdinov
2006-08-30 21:17               ` Dmitry V. Levin
2006-08-31 12:29                 ` Sergey Vlasov
2006-09-05 14:28                 ` Alexey Tourbin
2006-09-03  4:36           ` Alexey Tourbin
2006-09-03  6:34             ` Alexey Tourbin
2006-09-03  6:52               ` Alexey Tourbin
2006-09-03  6:56               ` Alexey Tourbin
2006-09-03 13:38               ` [devel] readlink Dmitry V. Levin
2006-09-04  7:30                 ` Alexey Tourbin
2006-09-03 17:08               ` [devel] оптимизация сборочных зависимостей Michael Shigorin
2006-09-03 17:39               ` Damir Shayhutdinov
2006-09-04  7:26                 ` Alexey Tourbin
2006-09-04 11:30                   ` Денис Смирнов
2006-09-04  9:42               ` [devel] xargs usage (Was: Re: оптимизация сборочных зависимостей) Andrei Bulava
2006-09-04  9:50                 ` Alexey Tourbin
2006-09-03 10:57             ` [devel] оптимизация сборочных зависимостей Alexey Tourbin
2006-09-03 17:07             ` Michael Shigorin
2006-09-04 11:14               ` [devel] esound (was: Re: оптимизация сборочных зависимостей ) Igor Zubkov
2006-09-02 16:24         ` [devel] buildreq2 (was: libpixman) Michael Shigorin
2006-09-03  1:29           ` Alexey Tourbin
2006-09-03 17:11             ` Michael Shigorin
2006-09-03  2:00           ` [devel] buildreq FRs Alexey Tourbin
2006-09-03 17:16             ` Michael Shigorin
2006-08-30 19:28       ` [devel] libpixman Kirill Maslinsky
2006-08-30 19:38         ` Andrey Rahmatullin
2006-08-30 19:52           ` Alexey Tourbin
2006-08-30 20:20             ` Sergey Vlasov
2006-08-30 20:31               ` Alexey Tourbin
2006-08-31 20:06                 ` [devel] buildreq ignore.d/fonts-cache Alexey Tourbin
2006-09-02 16:42                   ` Michael Shigorin
2006-09-02 17:17                     ` Dmitry V. Levin
2006-08-31  5:36             ` [devel] libpixman Andrey Rahmatullin
2006-08-31  6:11             ` Alexey I. Froloff
2006-09-02 16:40             ` Michael Shigorin
2006-08-30 19:57           ` [devel] buildreq при каждой сборке? Kirill Maslinsky
2006-08-30 19:39         ` [devel] libpixman Alexey Tourbin
2006-08-30 19:45           ` Konstantin A. Lepikhov
2006-08-30 19:53             ` Alexey Tourbin
2006-08-30 20:19           ` Kirill Maslinsky

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20060831002704.GK11420@localhost.localdomain \
    --to=at@altlinux.ru \
    --cc=devel@lists.altlinux.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

ALT Linux Team development discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
		devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
	public-inbox-index devel

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://lore.altlinux.org/org.altlinux.lists.devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git