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