Программистское недоуменное

[spamsink]

Есть у меня два файла, почти одинаковой длины, чуть поболее 6 миллионов строк каждый:

% wc -l f*
 6282918 f1.txt
 6287998 f2.txt

Сравним их.

% diff f1.txt f2.txt > diff12
% wc -l diff12
69246 diff12

Слегка так отличаются, чуть больше, чем на процент.
А теперь - наоборот:

% diff f2.txt f1.txt > diff21
% wc -l diff21
6756943 diff21

Я не понимаю, а вы?

Comments

[abzac-kakoj-to.livejournal.com]

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

Очевидно, для поиска "соответствующих" строк у него буфер какого-то размера. По-видимому, в одном из файле (f2?) есть подряд большой блок ни с чем не совпадающих строк, заполнивший этот буфер.

[spamsink]

дифф смотрит на первый файл и ищет "соответствующее" место во втором.

Это понятно, но что за бардак? В 21-м веке на многогигагерцовых машинах с многогигабайтной памятью можно бы по умолчанию и симметричное сравнение делать, нет?

[abzac-kakoj-to.livejournal.com]

дифф небось написан в 1979 году лично Керниганом. Или кто там был главный.

[spamsink]

Ну зачем же так огально ох... огульно охаивать?

diff (GNU diffutils) 2.8.1
Copyright (C) 2002 Free Software Foundation, Inc.
...
Written by Paul Eggert, Mike Haertel, David Hayes,
Richard Stallman, and Len Tower.

В 2002 году уже можно было и покрепче подумать над алгоритмом.

[iime.livejournal.com]

Тогда такого размера файлы, наверное, только в каком-нибудь АДАБАСе были.

[abzac-kakoj-to.livejournal.com]

Слово многогигагерцовый прекрасно.

[http://users.livejournal.com/_windwalker_/]

Можно использовать как скороговорку, аданазначна!

[cema.livejournal.com]

Ага, как-то так.

Diff несимметричный.

[spamsink]

Это не объяснение, это констатация того, что я продемонстрировал. Ты попробуй объяснить, какого рожна он несимметричный.

[mynine.livejournal.com]

Хм, а по моему вполне понятно, почему он несимметричный - он смотрит отличия второго от первого, чтобы получить разницу. Смысл париться и вычислять симметричный результат, если все равно он используется несимметрично ? мержить-то отличия можно только с первым файлом...

[spamsink]

Разница вполне может заключаться в том, что начальный блок первого файла во втором отсутствует.

[sab123.livejournal.com]

А посмотреть внутрь этих файлов и найти, в чем несимметричность?

[spamsink]

Один файл начинается на ABED..., а другой - на BCD..., где каждой буквой обозначены участки длиной около 6 тысяч строк. Когда файл, начинающийся на A... - первый, получается плохо. Это вполне согласуется с объяснением abzac_kakoj_to, но фиг ли?

[sab123.livejournal.com]

Вообще говоря, тогда все равно непонятно, почему несимметричность. Вот если строки из B встречаются также в A - тогда да. Кстати, сейчас читал man, нашел опцию -d "Change the algorithm to perhaps find a smaller set of changes. This makes diff slower (sometimes much slower)." Может вот он, ответ?

[spamsink]

Так-то да, с этим ключом получается 60969 в обоих случаях. Но почему бы по умолчанию не делать 69246 в обоих случаях?

[sab123.livejournal.com]

Может это не специально так, а просто глюк?

[spamsink]

Не верю, что я первый, кто нарывается на этот глюк. Но багтракера для gnu diff я навскидку не нашел.

[pkrs.livejournal.com]

diff дает набор команд, которые необходимо скормить sed'у, чтобы из первого файла получить второй. Очквидно, что этот набор команд несимметричен.

Если быть совсем точным, то команды для sed'а он выдает, если задать какой-то ключ (не помню какой именно), а без ключа - то же самое, но в более человекочитаемой форме.

[spamsink]

В симметричной форме, с галочками налево или направо, показывает содержимое "удаляемых" строк. Потому и результат должен быть симметричен с точностью до замены a на d и наоборот.

потому что все оттенки смысла умное число передает

[arno1251.livejournal.com]

То есть ты хочешь сказать, что если расстояние Левенштейна есть функция симметричная для строк, то дифф должен быть симметричным для файлов? Имхо все дело в реализации алгоритма. Дифф дает, по сути, последовательность команд для преобразования одного файла в другой, а число строк в результате есть лишь одна из метрик этой последовательности. Даже не самая значащая.
Возможно, не все фишки там учтены. По идее дифф должен прогнать оба варианта, взять из них более короткий и при необходимости инвертировать.

Re: потому что все оттенки смысла умное число передает

[spamsink]

По идее дифф должен прогнать оба варианта, взять из них более короткий и при необходимости инвертировать.

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

Re: потому что все оттенки смысла умное число передает

[arno1251.livejournal.com]

Я писал такие модули для баз данных. Там далеко не так все просто. Если размер хеша ограничен (иначе O(n)=n^2), то алгоритм изначально будет ущербным. Я, помню, для СУБД после мильона терзаний соорудил индексно-последовательный третий файл, в который прописал ссылки на оба исходных (за два селекта), а результат получал обработкой за третий проход. Не думаю, что у диффа есть такая возможность, это ведь обычный линейный алгоритм.

Re: потому что все оттенки смысла умное число передает

[spamsink]

Судя по соотношению размеров файлов и памяти, потребляемой диффом, размер хеша равен размеру файлов. Откуда возмется O(n^2) - мы же не сравниваем каждую строку с каждой?

на всякого мудреца довольно простоты

[arno1251.livejournal.com]

Возможно, хеш предусмотрен по размеру файла, а вот сопоставление работает с ограничителем.
Мы тут работали с индийскими партнерами, я всякого насмотрелся.

Re: на всякого мудреца довольно простоты

[cema.livejournal.com]

сопоставление работает с ограничителем

Кажется, так.

[dvv.livejournal.com]

Скорми диффы patch'у. В обе стороны (а то и во все четыре). Посмотри, что получится.

[spamsink]

Что ты ожидаешь увидеть, кроме "patch succeeded"?

[dvv.livejournal.com]

Что файл1+патч будет эквивалентен файлу2. Или неэквивалентен.