Post #100

​​Решение Первое решение, которое может прийти в голову: для каждой картинки в словаре пройдемся по ее дубликатам. И объединим множество дубликатов картинки с множествами дубликатов для каждого дубликата этой картинки. Но такое решение будет работать долго и неправильно. Долго потому что операция объединения множеств имеет линейную сложность, т.е. мы получим итоговую квадратичную сложность. А неправильно потому что может быть такая ситуация (рис. 1): # input { 'img2': {'img1'}, 'img3': {'img1', 'img4'}, 'img1': {'img2', 'img3'}, } # output { 'img2': {'img1', 'img3'}, 'img3': {'img1', 'img4', 'img2'}, 'img1': {'img2', 'img3', 'img4'}, } Т.е. для картинки img2 нужно было не просто объединить ее множество с множеством картинки img1, а еще и провалиться в множество картинки img1 и взять оттуда все множества дубликатов. Думаю, вы поняли, что здесь запахло рекурсией… поэтому забудем про это решение. Корректное и быстрое решение можно сделать при помощи структуры данных система непересекающихся множеств (Disjoint-set). Библиотечка для python. Но там буквально несколько строк, можно и самим написать. В этой структуре данных все объекты хранятся в непересекающихся множествах. У нее есть две операции: - get(x) — возвращает некоторого представителя из множества, которому принадлежит объект x - union(x, y) — объединяет два множества, в которых лежат объекты x и y Разберем на примере. Пусть была такая система множеств: {img1, img2, img3}, {img4, img5}, {img6, img7} get(img1) вернет нам одно из значений из множества {img1, img2, img3}. Т.е. некоторого представителя этого множества union(img2, img4) преобразует систему множеств к такому виду: {img1, img2, img3, img4, img5}, {img6, img7} Обе операции работают почти за О(1). В сложности фигурирует обратная функция Аккермана, но ее можно принять за небольшую константу в реальных задачах. Вообще, есть даже работы, которые утверждают, что нашли ошибку в выводе классической оценки и она может быть улучшена. Приспособить эту структуру данных под нашу задачу можно следующим образом (рис. 2). Вот и все. В итоге у нас получится система множеств картинок-дубликатов, которую мы хотели получить изначально.