Решение
Первое решение, которое может прийти в голову: для каждой картинки в словаре пройдемся по ее дубликатам. И объединим множество дубликатов картинки с множествами дубликатов для каждого дубликата этой картинки. Но такое решение будет работать долго и неправильно. Долго потому что операция объединения множеств имеет линейную сложность, т.е. мы получим итоговую квадратичную сложность. А неправильно потому что может быть такая ситуация (рис. 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).
Вот и все. В итоге у нас получится система множеств картинок-дубликатов, которую мы хотели получить изначально.
Первое решение, которое может прийти в голову: для каждой картинки в словаре пройдемся по ее дубликатам. И объединим множество дубликатов картинки с множествами дубликатов для каждого дубликата этой картинки. Но такое решение будет работать долго и неправильно. Долго потому что операция объединения множеств имеет линейную сложность, т.е. мы получим итоговую квадратичную сложность. А неправильно потому что может быть такая ситуация (рис. 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).
Вот и все. В итоге у нас получится система множеств картинок-дубликатов, которую мы хотели получить изначально.