Быстрый поиск совпадений объектов по их контрольным суммам на примере поиска дублирующихся изображений

[flashnik]

Ээээ… это переизобретение суффиксного дерева?

[Ogoun]

А нигде и не написано что это новшество. Это просто реализация. Была необходимость написать, и время создания оказалось меньше времени поиска готового решения.

[Ogoun]

Почитал про суффиксные деревья, действительно одна из их реализаций. Внесу в пост.

[it4_kp]

В ImageFileInspector замените

List<HashTreeNode> endNodes

на

HashSet<HashTreeNode> endNodes

тогда ваша программа заработает в разы быстрее. Да и вообще весь этот бор
кажется лишним, помоему хватило бы простого словаря.

[Ogoun]

Существенного прироста производительности не даст. EndNodes — это уже конечный список, который не учавствует в построении дерева. Временные затраты на его обработку при использовании List на два порядка ниже чем на построение дерева что видно по результату теста.
Время поиска дубликатов(построение дерева): 117 секунд (2 минуты)
Время на обработку конечных узлов и копирование файлов: 6 секундкопирование

[it4_kp]

Как это не участвует?
Вы в LoadCurrentImage используете следующую конструкцию:

if ( !endNodes.Contains( node ) )
	endNodes.Add( node );

Contains это линейная операция на списке и практически константная на множестве, что
даст огромный выигрыш в производительности.

[Ogoun]

Протестировал.
Файлов: 10751
List
Построение дерева: 78968мс
Обработка результата: 2201мс.
HashSet
Построение дерева: 23148мс
Обработка результата: 1198мс.

Выигрыш в три раза. Признаю, был не прав.