VPF::Поиск дубликатов - Форум программистов

Neox_GeForce

Дата 21.5.2009, 20:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

Мне нужно искать дубликаты файлов. Я решил найти контрольные суммы файлов и их сравнивать.
Но какой мне алгоритм использовать
CRC32, MD5,SHA1 какой самый самый быстрый??????? smile

--------------------

Челябинские программисты настолько суровы, что обходятся без компиляторов.
Челябинские программисты настолько суровы, что считают ассемблер недопустительной роскошью - они вручную магнетизируют участки жесткого диска.

DVariuS

Дата 22.5.2009, 09:06 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 200
Регистрация: 10.2.2009
Где: Ukraine

Репутация: 5
Всего: 8

Neox_GeForce, юзай CRC32 smile

Код можно взять, например, тут.

azesmcar

Дата 22.5.2009, 13:23 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Цитата(DVariuS @ 22.5.2009, 09:06

)

CRC32

CRC32 конечно можно подсчитать быстрее, но не надо забывать о коллизиях, речь идет о хэше файлов на диске - их реально много и повторения могут случаться (особенно учитывая законы Мэрфи).

По скорости Adler32 вроде быстрее CRC32. Но я бы использовал MD5 или SHA1. Надежность важнее smile

azesmcar

Дата 22.5.2009, 13:44 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

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

Цитата

Какое минимальное количество байт файла нужно для генерирование более-менее устойчивой CRC суммы(Нужно для поиска дубликатов файла)?

не думаю что кто нибудь сможет ответить на этот вопрос. Таких чисел никто не называeт, просто знай что CRC32 имеет низкую вероятность коллизий, но все же выше чем MD5 и SHA1. Для коротких текстов вероятность коллизий почти достигает нуля..но в том то и дело что почти smile

это все теория.

Это сообщение отредактировал(а) azesmcar - 22.5.2009, 13:45

Neox_GeForce

Дата 22.5.2009, 13:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

Мне нужно найти дубликаты файлов и вывести путь до груп дубликатов. Я решил делать поиск по контрольной сумме. но там задача что есть несколько сотен тисяч файлов и макс размер до 2гб.+программа должна быть производительней.
Я придумал такой алгоритм:
1. Сохраняем сумму и путь к файлу у списке.
2. потом ищу одинаковые значение к.с
еще раз по точнее проверяю ети файли.
Вывожу результати.
Вот такое я придумал. smile

--------------------

azesmcar

Дата 22.5.2009, 13:49 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Цитата(Neox_GeForce @ 22.5.2009, 13:45

)

вывести путь до груп дубликатов

в принципе не страшно..можно и CRC32..а когда найдешь дубликаты - вот тогда можно проверить и остальными чтобы удостоверится.
я бы сделал так.

1. Проверить размеры файлов - если не одинаковые - даже не считать сумму.
2. Если размеры одинаковые - подсчитать CRC32, проверить, если не одинаковые - забыть про этот файл и идти дальше
3. Если CRC32 одинаковые - проверить сумму MD5.

сводится к тому чтобы обращатся к сложным и медленным алгоритмам как можно реже.

PashaPash

Дата 22.5.2009, 13:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 13
Всего: 49

Neox_GeForce, можешь еще добавить
1. Сравнение размера.
2. Рассчет и кэширование контрольной суммы только при нахождении файлов с одинаковым размером.

Добавлено через 31 секунду
azesmcar, обогнал...

--------------------

Bird's-eye View?

Neox_GeForce

Дата 22.5.2009, 14:08 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

вижу надо какие то исходники показать.

Добавлено через 13 минут и 58 секунд

Цитата(azesmcar @ 22.5.2009, 13:49)

Цитата(Neox_GeForce @ 22.5.2009, 13:45

)

вывести путь до груп дубликатов

так надо сохранить размер файла-путь к файлу
а потом искать одинаковые размеры.
да??

Присоединённый файл ( Кол-во скачиваний: 13 )

Comparer.rar 67,34 Kb

--------------------

azesmcar

Дата 22.5.2009, 14:33 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Цитата(Neox_GeForce @ 22.5.2009, 14:08

)

вижу надо какие то исходники показать.

а в чем проблема то?

Цитата(Neox_GeForce @ 22.5.2009, 14:08

)

так надо сохранить размер файла-путь к файлу
а потом искать одинаковые размеры.
да??

ну да, сперва ищешь файлы с одинаковым размером, потом с той же суммой црц32, потом контрольный выстрел - мд5

Neox_GeForce

Дата 22.5.2009, 15:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

а хорошо ли я сохраняю списко файлов

Код


 public struct tablefile
    {
        public long length;
        public string fullName;
        public tablefile(long h, string n)
        {
            this.length = h;
            this.fullName = n;
        }
    };


public void AddFileToTable(string filename)
   {
       FileInfo fil = new FileInfo(filename);
       long len= fil.Length;
       FileList.Add(new tablefile(len,filename));
   }

--------------------

azesmcar

Дата 22.5.2009, 15:06 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Neox_GeForce

Я бы хранил в Dictionary
Ключ - размер файла, значение - путь к файлу.
Если такой размер уже есть, выделаешь в отдельный контейнер для дальнейшего сравнения. Типа того.

Neox_GeForce

Дата 22.5.2009, 15:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

не это для меня засложно. smile

Это сообщение отредактировал(а) Neox_GeForce - 22.5.2009, 15:47

--------------------

azesmcar

Дата 22.5.2009, 15:31 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Neox_GeForce

что тут сложного то? подожди, попозже скину примеры (хотя может до меня это кто нибудь другой сделает)

Это сообщение отредактировал(а) azesmcar - 22.5.2009, 15:32

Neox_GeForce

Дата 22.5.2009, 15:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 14.11.2007
Где: Украина

Репутация: нет
Всего: нет

думаю использовать SortedList

но вот если будут одинаковые раззмеры файлов то нужно вновь создавать список.а я не знаю как .

--------------------

azesmcar

Дата 22.5.2009, 16:09 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 6
Всего: 211

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication1
{
    struct SimilarFiles
    {
        public string file1_;
        public string file2_;
    }

    static class FileHelper
    {
        public static List<string> GetFilesRecursive(string b)
        {
            List<string> result = new List<string>();
            Stack<string> stack = new Stack<string>();
            stack.Push(b);
            while (stack.Count > 0)
            {
                string dir = stack.Pop();
                try
                {
                    result.AddRange(Directory.GetFiles(dir, "*.*"));
                    foreach (string dn in Directory.GetDirectories(dir))
                    {
                        stack.Push(dn);
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine("Cannot open directory ({0}}", e.Message);
                }
            }
            return result;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<long, string> temp = new Dictionary<long, string>();

            List<SimilarFiles> files = new List<SimilarFiles>();

            List<string> dirs = FileHelper.GetFilesRecursive("C:\\downloads\\");

            foreach (string path in dirs)
            {
                FileInfo info = new FileInfo(path);
                
                string file;
                if (!temp.TryGetValue(info.Length, out file))
                {
                    temp.Add(info.Length, path);
                } else
                {
                    SimilarFiles f;
                    f.file1_ = path;
                    f.file2_ = file;
                    files.Add(f);
                }
            }
        }
    }
}

после выполнения - в переменной files у нас лежат все файлы каталога с тем же самым размером.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »