<div dir="ltr">On Wed, Oct 30, 2019 at 12:06 PM Andrey Savchenko <<a href="mailto:bircoph@altlinux.org">bircoph@altlinux.org</a>> wrote:<br>><br>> On Wed, 30 Oct 2019 05:04:27 +0300 Alexey Tourbin wrote:<br>> > On Tue, Oct 29, 2019 at 9:23 PM Andrey Savchenko <<a href="mailto:bircoph@altlinux.org">bircoph@altlinux.org</a>> wrote:<br>> > > К Ñожалению, Ð´Ð»Ñ Ñ€ÐµÑˆÐµÐ½Ð¸Ñ Ñ€ÐµÐ°Ð»ÑŒÐ½Ð¾Ð¹ проблемы Ñтого недоÑтаточно:<br>> ><br>> > Давайте решим реальную проблему. Что вы хотите Ñделать? Left outer join?<br>><br>> Задача ÑледующаÑ:<br>><br>> 1) ЕÑÑ‚ÑŒ библиотека foo-1.0<br>> 2) Она обновилаÑÑŒ до foo-1.0.1<br>> 3) Возник unmet пакета bar на libfoo.so (>= set:abcdef)<br>><br>> Мне нужно знать, каких именно Ñимволов из 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 Ñ Ñамого начала, тогда получитÑÑ ÐºÐ²Ð°Ð´Ñ€Ð°Ñ‚Ð¸Ñ‡Ð½Ð°Ñ ÑложноÑÑ‚ÑŒ. Чтобы оÑталаÑÑŒ Ð»Ð¸Ð½ÐµÐ¹Ð½Ð°Ñ ÑложноÑÑ‚ÑŒ, нужно "подтÑгивать" P0 и P1 Ñ Ð¿Ñ€Ð¾ÑˆÐ»Ñ‹Ñ… итераций (алгоритмы такого рода, "подтÑгиваниÑ" неÑкльких отÑортированных ÑпиÑков, называютÑÑ 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 < Rn; i++) {<br>    uint32_t Rh = R[i];<br>    // advance P1<br>    while (P1h < Rh && P1i < P1n)<br>      P1h = P1[P1i++].v;<br>    // does P1 satisfy Rh?<br>    if (P1h == Rh)<br>      continue;<br>    // advance P0<br>    while (P0h < Rh && P0i < 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 < P0n && (P0h = P0[P0i++].v) == Rh)<br>      putchar(' '), fputs(P0[P0i-1].s, stdout);<br>    putchar('\n');<br>  }<br><br>Прикрепил полный пример. Ð’ общем, главное логичеÑки мыÑлить. СпроÑите там у Евгенича, он вам Ñкажет.<br><br># Usage: unset P0.txt P1.txt set:R<br>$ ./unset <(print -l a b c) <(print -l a b d) $(print -l a c |/usr/lib/rpm/mkset 10)<br>c<br></div>