<div dir="ltr">On Wed, Oct 30, 2019 at 12:06 PM Andrey Savchenko &lt;<a href="mailto:bircoph@altlinux.org">bircoph@altlinux.org</a>&gt; wrote:<br>&gt;<br>&gt; On Wed, 30 Oct 2019 05:04:27 +0300 Alexey Tourbin wrote:<br>&gt; &gt; On Tue, Oct 29, 2019 at 9:23 PM Andrey Savchenko &lt;<a href="mailto:bircoph@altlinux.org">bircoph@altlinux.org</a>&gt; wrote:<br>&gt; &gt; &gt; К сожалению, для решения реальной проблемы этого недостаточно:<br>&gt; &gt;<br>&gt; &gt; Давайте решим реальную проблему. Что вы хотите сделать? Left outer join?<br>&gt;<br>&gt; Задача следующая:<br>&gt;<br>&gt; 1) Есть библиотека foo-1.0<br>&gt; 2) Она обновилась до foo-1.0.1<br>&gt; 3) Возник unmet пакета bar на libfoo.so (&gt;= set:abcdef)<br>&gt;<br>&gt; Мне нужно знать, каких именно символов из foo стало не хватать bar.<br><br>Ну и чево?  Есть set-версия R и есть множества строк P0 и P1. P0 удовлетворяет R, а P1 - не удовлетворят (какие-то строки из P1 удалили).  Есть готовые примитивы как это распаковать в массивы, как показано на рисунке.<br><br><font face="monospace">    P0           P1         R<br>+----+----+  +----+----+  +----+<br>| h0 | s0 |  | h0 | s0 |  | h0 |<br>+----+----+  +----+----+  +----+<br>| h1 | s1 |  | h2 | s2 |  | h1 |<br>+----+----+  +----+----+  +----+<br>| h2 | s2 |  | h3 | s3 |  | h3 |<br>+----+----+  +----+----+  +----+<br>| h3 | s3 |  | h4 | s4 |<br>+----+----+  +----+----+<br></font><br>На рисунке видно, что в новой версии P1 удалился символ s1 с хешем h1 (а добавился символ s4 с хешем h4).  Как тогда систематически напечатать недостающие символы?  Внешний цикл будет по R: для каждого хеша в R мы смотрим, есть ли такой же хеш в P1.  Если есть, то он удовлетворен, и проблемы нет.  А иначе он неудовлетворен, тогда нам нужно найти символ с таким же хешем в P0 и его напечатать. В общем, с непривычки написать такой цикл может и сложновато, но если думать логически, то ничего невозможного в этом нет.  Главное не пытаться каждый раз искать в P1 и P0 с самого начала, тогда получится квадратичная сложность.  Чтобы осталась линейная сложность, нужно &quot;подтягивать&quot; P0 и P1 с прошлых итераций (алгоритмы такого рода, &quot;подтягивания&quot; нескльких отсортированных списков, называются merge algorithms).  Для этого введем переменные P1h - текущий хеш, P1i - следующий индекс, по принципу P1h = P1[P1i++].v, аналогично для P0. Тогда цикл получается таким:<br><br>    size_t P0i = 0;<br>    size_t P1i = 0;<br>    uint32_t P0h = P0[P0i++].v;<br>    uint32_t P1h = P1[P1i++].v;<br>    for (size_t i = 0; i &lt; Rn; i++) {<br>        uint32_t Rh = R[i];<br>        // advance P1<br>        while (P1h &lt; Rh &amp;&amp; P1i &lt; P1n)<br>            P1h = P1[P1i++].v;<br>        // does P1 satisfy Rh?<br>        if (P1h == Rh)<br>            continue;<br>        // advance P0<br>        while (P0h &lt; Rh &amp;&amp; P0i &lt; P0n)<br>            P0h = P0[P0i++].v;<br>        // P0 then must satisfy Rh<br>        assert(P0h == Rh);<br>        // print the symbol associated with P0h<br>        fputs(P0[P0i-1].s, stdout);<br>        // more than one symbol may hash to Rh,<br>        // print them on the same line<br>        while (P0i &lt; P0n &amp;&amp; (P0h = P0[P0i++].v) == Rh)<br>            putchar(&#39; &#39;), fputs(P0[P0i-1].s, stdout);<br>        putchar(&#39;\n&#39;);<br>    }<br><br>Прикрепил полный пример. В общем, главное логически мыслить. Спросите там у Евгенича, он вам скажет.<br><br># Usage: unset P0.txt P1.txt set:R<br>$ ./unset &lt;(print -l a b c) &lt;(print -l a b d) $(print -l a c |/usr/lib/rpm/mkset 10)<br>c<br></div>