From: Alexey Tourbin <at@altlinux.ru>
To: ALT Devel discussion list <devel@lists.altlinux.org>
Subject: Re: [devel] оптимизация сборочных зависимостей
Date: Wed, 30 Aug 2006 23:07:59 +0400
Message-ID: <20060830190759.GA10542@localhost.localdomain> (raw)
In-Reply-To: <20060830161050.GA31919@basalt.office.altlinux.org>
[-- Attachment #1: Type: text/plain, Size: 2415 bytes --]
On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > переписке. Правда, спросонья я потерял к нему интерес. Если это
> > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
>
> Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> по теории графов?
Вот математическая постановка задачи. Дан список (множество) пакетов P.
Найти минимальное подмножество P_0, при котором множество P является
подмножеством транзитивного замыкания P_0:
P_0\subset P
P\subset [P_0]
\forall P_n P\subset [P_n] \Rightarrow |P_n|\geq|P_0|
Здесь [P] -- транзитивное замыкание множества, |P| -- мощность множества.
Подмножества не обязательно собственные.
Говорить о транзитивном замыкании множества не совсем корректно.
Речь идет о транзитивном замыкании пакетов по отношению "зависеть".
Например, если дан пакет A, и при этом известно, что пакет A требует
пакет B, тогда B входит в [A]. Если же пакет B зависит от пакета C,
тогда C снова входит в [A] и т.д.
Последнее условие выражает ту мысль, что подмножество P_0 должно быть
в некотором смысле минимальным. А именно, все другие подмножества с
транзитивным замыканием [P] или больше обладают не меньшей мощностью.
Решение этой задачи в лоб означает перебор всех подмножеств P_n и
построение для каждого из них транзитивного замыкания. Среди
подмножеств, у которых транзитивное замыкание не меньше [P] (а
фактически совпадает с [P]), нужно выбрать наименьшее по числу
элементов.
Однако известно, что перебор подмножеств -- это чрезвычайно трудоемкая
задача.
Кто ничего не понял, транзитивное замыкание -- это, грубо говоря, список
пакетов в чруте, который hasher/apt разворачивает по строчке
BuildRequires. Т.е. список пакетов в чруте -- это транзитивное
замыкание [BuildRequires]. Оптимизация списка BuildRequires тогда
состоит в том, чтобы при удалении некоторых элементов из этого списка
содержимое чрута в конечном счете не менялось. Остается только выбрать
наилучшую их всех возможных оптимизаций, при которой список
BuildRequires становится минимальным.
Кстати, можно изменить условие задачи:
-P_0\subset P
+P_0\subset [P]
Я реализовал это в buildreq2 и получил интересные результаты.
В buildreq2 решена задача построения транзитивного замыкания,
но не до конца не решена задача оптимизации.
[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]
next prev parent reply other threads:[~2006-08-30 19:07 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
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 [this message]
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=20060830190759.GA10542@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