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 02:48:51 +0400
Message-ID: <20060830224851.GI11420@localhost.localdomain> (raw)
In-Reply-To: <20060830210106.GH11420@localhost.localdomain>

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

On Thu, Aug 31, 2006 at 01:01:06AM +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
#head -v qR qP
join -j 2 -o '1.1 2.1' qR qP |sort -u >p2p
tsort p2p >tsorted || [ -s tsorted ]
#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
sort -o extrareq -u extrareq
awk '{print$1}' qR |sort -u >req
#head -v req extrareq
comm -23 req extrareq |xargs -r echo
$

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

$ ./optimize_package_list glibc-core sh
sh
$ ./optimize_package_list perl-base    
perl-base
$ ./optimize_package_list perl-DateTime-TimeZone perl-DateTime     
tsort: p2p: input contains a loop:                                     
tsort: perl-DateTime
tsort: perl-DateTime-TimeZone
perl-DateTime
$

Очень прошу указать мне ситуацию, в которой скрипт лажается.

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

  reply	other threads:[~2006-08-30 22:48 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 [this message]
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
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=20060830224851.GI11420@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