[devel] Утилиты для работы с setversions?

[Alexey Tourbin]

On Wed, Oct 30, 2019 at 12:06 PM Andrey Savchenko <bircoph на altlinux.org>
wrote:
>
> On Wed, 30 Oct 2019 05:04:27 +0300 Alexey Tourbin wrote:
> > On Tue, Oct 29, 2019 at 9:23 PM Andrey Savchenko <bircoph на altlinux.org>
wrote:
> > > К сожалению, для решения реальной проблемы этого недостаточно:
> >
> > Давайте решим реальную проблему. Что вы хотите сделать? Left outer join?
>
> Задача следующая:
>
> 1) Есть библиотека foo-1.0
> 2) Она обновилась до foo-1.0.1
> 3) Возник unmet пакета bar на libfoo.so (>= set:abcdef)
>
> Мне нужно знать, каких именно символов из foo стало не хватать bar.

Ну и чево?  Есть set-версия R и есть множества строк P0 и P1. P0
удовлетворяет R, а P1 - не удовлетворят (какие-то строки из P1 удалили).
Есть готовые примитивы как это распаковать в массивы, как показано на
рисунке.

    P0           P1         R
+----+----+  +----+----+  +----+
| h0 | s0 |  | h0 | s0 |  | h0 |
+----+----+  +----+----+  +----+
| h1 | s1 |  | h2 | s2 |  | h1 |
+----+----+  +----+----+  +----+
| h2 | s2 |  | h3 | s3 |  | h3 |
+----+----+  +----+----+  +----+
| h3 | s3 |  | h4 | s4 |
+----+----+  +----+----+

На рисунке видно, что в новой версии P1 удалился символ s1 с хешем h1 (а
добавился символ s4 с хешем h4).  Как тогда систематически напечатать
недостающие символы?  Внешний цикл будет по R: для каждого хеша в R мы
смотрим, есть ли такой же хеш в P1.  Если есть, то он удовлетворен, и
проблемы нет.  А иначе он неудовлетворен, тогда нам нужно найти символ с
таким же хешем в P0 и его напечатать. В общем, с непривычки написать такой
цикл может и сложновато, но если думать логически, то ничего невозможного в
этом нет.  Главное не пытаться каждый раз искать в P1 и P0 с самого начала,
тогда получится квадратичная сложность.  Чтобы осталась линейная сложность,
нужно "подтягивать" P0 и P1 с прошлых итераций (алгоритмы такого рода,
"подтягивания" нескльких отсортированных списков, называются merge
algorithms).  Для этого введем переменные P1h - текущий хеш, P1i -
следующий индекс, по принципу P1h = P1[P1i++].v, аналогично для P0. Тогда
цикл получается таким:

    size_t P0i = 0;
    size_t P1i = 0;
    uint32_t P0h = P0[P0i++].v;
    uint32_t P1h = P1[P1i++].v;
    for (size_t i = 0; i < Rn; i++) {
        uint32_t Rh = R[i];
        // advance P1
        while (P1h < Rh && P1i < P1n)
            P1h = P1[P1i++].v;
        // does P1 satisfy Rh?
        if (P1h == Rh)
            continue;
        // advance P0
        while (P0h < Rh && P0i < P0n)
            P0h = P0[P0i++].v;
        // P0 then must satisfy Rh
        assert(P0h == Rh);
        // print the symbol associated with P0h
        fputs(P0[P0i-1].s, stdout);
        // more than one symbol may hash to Rh,
        // print them on the same line
        while (P0i < P0n && (P0h = P0[P0i++].v) == Rh)
            putchar(' '), fputs(P0[P0i-1].s, stdout);
        putchar('\n');
    }

Прикрепил полный пример. В общем, главное логически мыслить. Спросите там у
Евгенича, он вам скажет.

# Usage: unset P0.txt P1.txt set:R
$ ./unset <(print -l a b c) <(print -l a b d) $(print -l a c
|/usr/lib/rpm/mkset 10)
c
----------- следующая часть -----------
Вложение в формате HTML было удалено...
URL: <http://lists.altlinux.org/pipermail/devel/attachments/20191030/50339d34/attachment-0001.html>