[devel] оптимизация сборочных зависимостей
Alexey Tourbin
=?iso-8859-1?q?at_=CE=C1_altlinux=2Eru?=
Ср Авг 30 23:07:59 MSD 2006
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 решена задача построения транзитивного замыкания,
но не до конца не решена задача оптимизации.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя : =?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/20060830/e0cca169/attachment-0001.bin>
Подробная информация о списке рассылки Devel