Вопрос в том, где находился этот файл — если на компьютере, подключенном к роутеру проводами — то все ОК. Если на диске, подключенном к роутеру по USB — будут тормоза.
Предлагаю один из «странных», но рабочих вариантов оптимизации (кому-то этот способ может показаться быдлокодерским). Поскольку в клиент-серверных системах данные на клиенте вне транзакций можно всегда считать неактуальными (на сервере они уже могли измениться), то на клиенте можно реализовать логику «не запрашивать заданный справочник у сервера чаще чем 1 раз в N секунд» (ну или миллисекунд — в зависимости от того, как часто клиентский код может запросить актуальную версию справочника у сервера).
Такой вариант позволяет в клиентском коде не беспокоиться (не думать) о сокращении количества обращений за актуальной версией справочника — слишком частые вызовы просто будут проигнорированы промежуточным слоем клиента, обращений к серверу при этом не будет вообще.
У Амазона есть определенная репутация, которой он рискует в случае нарушения заявленных в SLA гарантий. Это очень серьезный риск.
Кстати любимый всеми DropBox хранит все данные как раз на серверах Амазона. Для вас это что-нибудь значит? ;)
В бизнесе всегда делаются уступки, исключения из правил, заключаются специальные соглашения, к каждому клиенту/партнер может использоваться свой индивидуальный подход. Без этой «изворотливости» (в позитивном смысле) успешный бизнес не построить.
>о бесплатном приложении Mikogo для демонстрации экрана
Раньше оно было абсолютно бесплатным, впоследствии стало бесплатным лишь для некоммерческого использования.
Упс, точно, просмотрел первый вариант :) Имею в виду второй конечно (динамическое программирование). Я по первой картинке смотрел :) Извините что ввел вас в заблуждение
Поверьте мне, именно про тупой железобетонно-деревянно-неэффективный первый алгоритм с огромной матрицей :) (с предварительным эмпирическим подразбиением файлов). Собственно найти саму LCS это лишь малая часть сравнения. У меня была задача для измененных фрагментов (участков, где нет ни одного равного абзаца) показать точные изменения в тексте абзацев. А для этого нужно было сначала найти оптимальное сопоставление измененных абзацев на основе степени их схожести. Я как раз собирался сначала написать про LCS в продолжение к моему первому топику, но вы меня опередили :) Видимо теперь придется писать сразу уже про схожесть и поиск оптимального соответствия :)
Обойти ограничения первого алгоритма по времени вычислений и требуемому объему памяти можно, например, предварительно разбив файл на отдельные сравнительно небольшие участки для поиска LCS (например, содержащие не более 5000 строк). Матрицу из 5000*5000*4 байта(Integer) = 100 МБ еще как-то можно упихнуть в память). Конечно, найденная последовательность не будет самой оптимальной с математической точки зрения, но для сравнения файлов вполне годится.
Для разделения файлов на участки можно использовать какой-нибудь эмпирический подход.
Например:
1) Определить очередную теоретическую точку разделения в файлах А и Б. Эта точка находится на выбранном удалении от предыдущих найденных точек разделения. Например, 5000 строк.
2) На относительно небольшом расстоянии по отношению к размеру участка (например, 100 строк) от теоретической точки разделения найти наиболее показательные элементы (например, 10 самых длинных строк). Взять очередную найденную показательную строку (по убыванию показательности) и попытаться найти ее во втором файле на бОльшем расстоянии по сравнению с участком поиска показательных элементов в файле А, но меньшем размера участка разделения (например, 25%-50% от участка разделения, т.е. 1200-2500 строк).
3) Если соответствующая строка в файле Б найдена, то можно дополнительно подстраховаться, что мы не ошиблись, сравнив несколько строк, соседствующих c выбранной строкой (они тоже должны совпадать).
4) Если соответствующая строка в документе Б не найдена, то можно взять следующую показательную строку и попытаться выполнить шаги 2-4 для нее.
5) Если для всех показательных строк так и не получилось найти соответствие в документе Б, можно сравнение на основе точного соответствия заменить на сравнение на основе похожести («дистанции») между строками, но при этом длину участка поиска в документе Б нужно сократить.
6) Если точки разделения уточнить по схожим строкам не удалось, значит нам не повезло, вынуждены принять теоретические точки разделения за фактические.
Для найденных отдельных участков ищем LCS независимо любым из перечисленных выше алгоритмов.
Самый первый алгоритм (примитивный) хорош тем, что можно использовать веса при вычислении LCS, т.е. считать, что вес совпадения может быть равен не только 1, но и 2, 3… и даже 0 (причем этот вес можно сделать даже дробным при желании). Это удобно при построчном сравнении файлов, т.к., например, пустые строки дают меньший вклад в оценку наибольшей совпадающей подпоследовательности, чем содержащие текст. Также строки большой длины имеют больший вес по сравнению с короткими строками.
Для примера:
Версия 1:
a
b
cdefghijklm
Версия 2:
cdefghijklm
a
b
При равных весах строк при сравнении LCS будет представлена строками (a, b), хотя на самом деле строка cdefghijklm содержит больше значимой информации, чем a и b вместе взятые.
В простейшем случае за вес можно взять длину строки или количество значимых символов в ней.
Такой вариант позволяет в клиентском коде не беспокоиться (не думать) о сокращении количества обращений за актуальной версией справочника — слишком частые вызовы просто будут проигнорированы промежуточным слоем клиента, обращений к серверу при этом не будет вообще.
Кстати любимый всеми DropBox хранит все данные как раз на серверах Амазона. Для вас это что-нибудь значит? ;)
Грустно не то, что индусы привыкли к Tcl, а то, что и без индусов многие проекты делаются так, как вы описали.
Раньше оно было абсолютно бесплатным, впоследствии стало бесплатным лишь для некоммерческого использования.
Для разделения файлов на участки можно использовать какой-нибудь эмпирический подход.
Например:
1) Определить очередную теоретическую точку разделения в файлах А и Б. Эта точка находится на выбранном удалении от предыдущих найденных точек разделения. Например, 5000 строк.
2) На относительно небольшом расстоянии по отношению к размеру участка (например, 100 строк) от теоретической точки разделения найти наиболее показательные элементы (например, 10 самых длинных строк). Взять очередную найденную показательную строку (по убыванию показательности) и попытаться найти ее во втором файле на бОльшем расстоянии по сравнению с участком поиска показательных элементов в файле А, но меньшем размера участка разделения (например, 25%-50% от участка разделения, т.е. 1200-2500 строк).
3) Если соответствующая строка в файле Б найдена, то можно дополнительно подстраховаться, что мы не ошиблись, сравнив несколько строк, соседствующих c выбранной строкой (они тоже должны совпадать).
4) Если соответствующая строка в документе Б не найдена, то можно взять следующую показательную строку и попытаться выполнить шаги 2-4 для нее.
5) Если для всех показательных строк так и не получилось найти соответствие в документе Б, можно сравнение на основе точного соответствия заменить на сравнение на основе похожести («дистанции») между строками, но при этом длину участка поиска в документе Б нужно сократить.
6) Если точки разделения уточнить по схожим строкам не удалось, значит нам не повезло, вынуждены принять теоретические точки разделения за фактические.
Для найденных отдельных участков ищем LCS независимо любым из перечисленных выше алгоритмов.
Для примера:
Версия 1:
a
b
cdefghijklm
Версия 2:
cdefghijklm
a
b
При равных весах строк при сравнении LCS будет представлена строками (a, b), хотя на самом деле строка cdefghijklm содержит больше значимой информации, чем a и b вместе взятые.
В простейшем случае за вес можно взять длину строки или количество значимых символов в ней.