Ogoun 8 сен 2010 в 00:02

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

4 мин

4.1K

.NET*

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

flashnik 8 сен 2010 в 00:19

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

Ogoun 8 сен 2010 в 00:51

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

Ogoun 8 сен 2010 в 01:39

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

it4_kp 8 сен 2010 в 10:49

В ImageFileInspector замените

List<HashTreeNode> endNodes

на

HashSet<HashTreeNode> endNodes

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

Ogoun 8 сен 2010 в 11:06

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

it4_kp 8 сен 2010 в 11:14

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

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

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

Ogoun 8 сен 2010 в 11:40

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

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

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

Показать лучшие за всё время