Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Сравнение файлов

Страницы: < 1 2
vasIZmax © (2007-09-20 10:33:00)
Столкнулся с такой задачкой.
В папке порядка 17 000 файлов. Но среди них попадается большое количество дубликатов, т.е. полностью одинаковые, кроме имени. Как можно удалить дубликаты?
Думаю реализовывать так: через findfirst, findnext. Берем первый файл и начинаем сравнивать по-байтово(об этом тож сейчас думаю — как реализовать) его со всеми по очередно. Если полностью схожи, то дубликат удаляем.
Но,имхо, такой метод будет очень долгим? Может по другому как?

Jeer (2007-09-20 14:13:00) [21]

> Anatoly Podgoretsky © (20.09.07 13:39) [14]
>
> > Jeer (20.09.2007 11:56:07) [7]
>
> А если на миллионном и таких файлов много?

А как тебе такая статистика по реальному тесту ?

Время ( *E6 ticks) выполнения операций Comparemem и CRC32 над буферами
в памяти с объемом в Mbyte :
Size___T(Compare)___T(CRC32)

0.04___0.05______0.07
0.256__1.3_______4.5
1______3.6_______18
10_____34________185
100____313_______1870

Как видим, для обоих случаев зависимость линейная, но коэффициент у CompareMem (t = 3.4*Size) лучше, чем у CRC (t = 18.5*Size) более чем в 5 раз.

P.S.
Реализация CRC32 стандартная, через table и asm
P.P.S
Понятно, что можно и CRC16, но возможны уже коллизии при больших size.

Slym (2007-09-20 13:49:00) [22]
Для параноиков: можно выычислить различные свертки- CRC,MD5,SHA
если для 2х файлов совпали CRC,MD5,SHA то вероятность что файл одинаковые как предел слева к 1

stanislav (2007-09-20 13:47:00) [23]
Slym © (20.09.07 13:42) [15]
может меньше т.к. если совпадения будут допустим с 5 файлами они удаляться :-)

Slym (2007-09-20 13:42:00) [24]
stanislav © (20.09.07 13:35) [11]
площадь половины (по диагонали) квадрата т.е. 17000^2/2

Anatoly Podgoretsky (2007-09-20 13:39:00) [25]
> Jeer (20.09.2007 11:56:07) [7]

А если на миллионном и таких файлов много?

Anatoly Podgoretsky (2007-09-20 13:39:00) [26]
> clickmaker (20.09.2007 11:54:06) [6]

> сравнение первых, скажем, 100 байтов будет медленее расчета CRC?

А разница в 101 байте.

Slym (2007-09-20 13:38:00) [27]
Повторное сканирование частично берет данные из предыдущего сканирования...
т.е. при совпадении ShortName|Type|FullPath|Size контрольная сумма не пересчитывается

stanislav (2007-09-20 13:35:00) [28]
Плохиш © (20.09.07 13:26) [9]
ок не 17000^2? но больше 17000

Slym (2007-09-20 13:34:00) [29]
Я делал такую паделку...
1. Сканил диск в БД, яля кеширование
ShortName|Type|FullPath|Size|CRC
2. Дальше средствами SQL искал жертву аля
2.1. SELECT FullPath GROUP Type,Size,CRC HAVING Count(FullPath)>1
Тут удаление можно на автомате приделать, оставлять только 1 файл
2.2. SELECT FullPath GROUP ShortName HAVING Count(FullPath)>1
этот запрос выводил в Grid с фоном вычисляемыл из CRC
т.е. название одно, а разница содержания сразу бросается в глаза
3. Удаляю жертву, удаляю запись о ней

Плохиш (2007-09-20 13:26:00) [30]

> а сравнивать побайтово 17000^2!

Ну если с логикой проблемы, то, да, сравнивайте одни и те же файлы по два раза :-)

stanislav (2007-09-20 13:22:00) [31]
clickmaker © (20.09.07 11:54) [6]
Рсчет CRC Будет произведен 17 000, а сравнивать побайтово 17000^2!

Jeer (2007-09-20 11:56:00) [32]
Sergey13 © (20.09.07 11:13) [4]
Anatoly Podgoretsky © (20.09.07 11:44) [5]

Тоже смысла не вижу, т.к. comparemem вылетит с false на первом же байте.

clickmaker (2007-09-20 11:54:00) [33]

> [5] Anatoly Podgoretsky © (20.09.07 11:44)

с чего бы?
сравнение первых, скажем, 100 байтов будет медленее расчета CRC?

Anatoly Podgoretsky (2007-09-20 11:44:00) [34]
> Sergey13 (20.09.2007 11:13:04) [4]

Есть смысл, при данной задаче можно сильно ускориться.

Sergey13 (2007-09-20 11:13:00) [35]
Может подумать вокруг контрольной суммы?

vasIZmax (2007-09-20 10:44:00) [36]
> MBo © (20.09.07 10:35) [1]

если бы — попадаются много (!) одинаковых. При чем размер может быть одинаковый, а содержимое — разное.

> clickmaker © (20.09.07 10:36) [2]

ок, сейчас посмотрю

clickmaker (2007-09-20 10:36:00) [37]
если размеры одинаковые, начинать сравнивать побайтово: читать кусками, потом CompareMem

MBo (2007-09-20 10:35:00) [38]
размеры разные?

Страницы: < 1 2

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »