Ogoun 7 сен 2010 в 20:02

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

4 мин

4.4K

.NET *

Комментарии 7

flashnik 7 сен 2010 в 20:19

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

Ogoun 7 сен 2010 в 20:51

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

Ogoun 7 сен 2010 в 21:39

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

it4_kp 8 сен 2010 в 06:49

В ImageFileInspector замените

List<HashTreeNode> endNodes

на

HashSet<HashTreeNode> endNodes

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

Ogoun 8 сен 2010 в 07:06

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

it4_kp 8 сен 2010 в 07:14

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

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

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

Ogoun 8 сен 2010 в 07:40

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий