On Wed, Aug 30, 2006 at 08:28:49PM +0400, Alexey Tourbin wrote:
> On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > > переписке.  Правда, спросонья я потерял к нему интерес.  Если это
> > > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
> > 
> > Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> > по теории графов?
> 
> Тогда повторю вопрос.
> 
>    145  "$PACKAGEOF" -f "$WORKDIR/files" >"$WORKDIR/packages"
>    146  sort -u -o "$WORKDIR/packages" "$WORKDIR/packages"

packages - это список имён пакетов, которые использовались для сборки
посредством files.

>    148  cat "$WORKDIR/packages" |
>    149          xargs -r rpmquery --qf '[%{REQUIRENAME}\n]' -- |  
>    150          sort -u >"$WORKDIR/reqs"

reqs - это все requires пакетов packages.

>    152  cat "$WORKDIR/packages" |
>    153          xargs -r rpmquery --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- |
>    154          sort -k2,2 -k1,1 -u >"$WORKDIR/provs"

provs - это всё provides пакетов packages в виде пар
"ProvideName PackageName".

>    156  comm -23 "$WORKDIR/packages" "$WORKDIR/reqs" >"$WORKDIR/package-reqs"

package-reqs - это пакеты packages за вычетом тех, имена которых совпали с
requires пакетов packages.  В частности, эта операция выкидывает простые
циклы целиком.

>    158  join -1 1 -2 2 -o 1.1 "$WORKDIR/reqs" "$WORKDIR/provs" |
>    159          sort -u >"$WORKDIR/reqs_provs"

reqs_provs - это те requires пакетов packages, которые есть среди provides
пакетов packages.

>    160  comm -23 "$WORKDIR/package-reqs" "$WORKDIR/reqs_provs" \
>    161          >"$WORKDIR/package-reqs-provs"

package-reqs-provs - это пакеты package-reqs за вычетом тех, имена которых
совпали с requires, перечисленными в reqs_provs.  В частности, эта
операция выкидывает все циклы полностью.

[...]
> join в строке 158 делает нечто отличное: ты соединяешь
> reqs<ВиртуальнаяЗависимость> на provs<ИмяПакета>, а на выходе хочешь   
> получить provs<ВиртуальнаяЗависимость>.  Это выглядит подозрительно,
> потому что происходит соединение по полям разных типов.

Почему разных?  Имя пакета - это частный случай виртуальной provides.

[...]
> Какой в этом смысл?

Минимизация мощности множества зависимостей.  Алгоритм нечестный в том
смысле, что он выкидывает циклы.

Поскольку исходное множество конечно, всегда есть алгоритм полного
перебора всех подмножеств данного множества, из которых выбирается любое
удовлетворяющее критерию отбора.  Очевидно, что этот алгоритм непрактичен.
Полагаю, что существует алгоритм приемлемой вычислительной сложности, но
мне он не известен.


-- 
ldv