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

Neox_GeForce

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

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

Загрузка ...

Опытный

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

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

Сделал так

Код


  public class ListFiles
    {
        ArrayList length = new ArrayList(100);
        ArrayList name = new ArrayList(100);
        public void addFilesToList(long l, string name)
        {
            this.length.Add(l);
            this.name.Add(name);
        }

    }

в рекурсивной функции уже зачисляю.
Диск Е: прошло за 10 сек
а С: за 3 минуты

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

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

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

azesmcar

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

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

Загрузка ...

uploading...

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

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

Neox_GeForce

Зачем? для этого же Dictionary есть. У него и поиск намного быстрее (логаритмическая сложность) и вместо двух контейнеров будет один. Я пример привел на предыдущей странице.

Любитель

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

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Тебе надо найти все дубликаты или найти дубликаты для известного файла?

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

http://oryolalex.mybrute.com

Neox_GeForce

Дата 22.5.2009, 17:03 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(azesmcar @ 22.5.2009, 16:09)

Код


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 у нас лежат все файлы каталога с тем же самым размером.

круто. НО в files сохраняется одинаковых значений.
тоесть если в каталоге ести одинаковые файли 1,11,111
to files[0]=11,1

files[1]=111,1

тоесть
если есть 20 одинаковых файлов
то будет 20!/(18!) 380пар.

П.С стековая версия обхода каталогов понравилась smile

Добавлено @ 17:08

Цитата(Любитель @ 22.5.2009, 16:28)

Тебе надо найти все дубликаты или найти дубликаты для известного файла?

Все дубликаты

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

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

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

Neox_GeForce

Дата 22.5.2009, 18:27 (ссылка)

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

Загрузка ...

Опытный

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

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

я тут придумал. тока не знаю как реализовать.
надо чота типа такого
"размер файла"-список файлов
"размер файла1"-список файлов

МОжно ли обновлять значения словаря по заданому ключу????? smile

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

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

Любитель

Дата 22.5.2009, 19:01 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Лучше не размер. А Dictionary<CustomKey, List<string>>. CustomKey будет хранить размер и хеш. И перегружать Equals и GetHashCode, чтобы сравнивать вначале размер, а затем (если понадобится - хеш). Можно ещё считать хеш только по требованию, чтобы для файлов с "уникальным" размером вообще не считать его.

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

http://oryolalex.mybrute.com

Neox_GeForce

Дата 22.5.2009, 19:17 (ссылка)

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

Загрузка ...

Опытный

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

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

гм..
не пойму.

1. у меня есть список файлов каталога и пустой словарь

дальше я не могу придумать норм алгоритм который би собирал дубликаты в групы(тоесть списки).

И СustomKey ето что? структура?

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

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

Любитель

Дата 23.5.2009, 00:38 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Суть CustomKey - в переопределении Equals (если размеры не равно - хеши не сравниваем), ну и GetHashCode соответственно. Далее, key сам знает для какого он файла создавался (путь). Это позволит при вызове Equals, если равны размеры у двух ключей - вызвать (у обоих) подсчёт хеша файла и сравнить его (лишний раз хеш считаться не будет - для файлов "одиночек" по размеру). После подсчёта хеша - используем *в дальнейшем) рассчитанный хеш (сделай его nullable полем, например, чтобы проще было определить рассчитан или нет). Имя файла больше не несёт смысла. При такой реализации ключа достаточно пройтись по всему дереву каталогов, создать для каждого элемента ключ, сделать TryGetValue для дикшенри (если ничего не получили - создаём новый список и добавляем в дикшенри), добавить файл в список. После обхода по дереву каталогов, проходим по элементам дикшенри, если в списке больше одного элемента - это потенциальные кандидаты. Тут уже делаем full content comparsion.

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

http://oryolalex.mybrute.com

Neox_GeForce

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

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

Загрузка ...

Опытный

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

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

Цитата(Любитель @ 23.5.2009, 00:38)

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

(если ничего не получили - создаём новый список и добавляем в дикшенри)
а если получили то куда ? в Словарь? но он же не сохраняет одинаковые ключи?

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

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

Любитель

Дата 23.5.2009, 20:54 (ссылка)

(голосов:1)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Если получили - добавляем элемент в полученный список.

Код


List<string> filesList;
if (!filesInfo.TryGetValue(key, out filesList))
{
    filesList = new List<string>();
    filesInfo.Add(key, filesList);
}

filesList.Add(fileName);

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

http://oryolalex.mybrute.com

Neox_GeForce

Дата 23.5.2009, 21:49 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Любитель @ 23.5.2009, 00:38)

и как переопределить Equals i GetHashCode, там ошибки
"ConsoleApplication1.Program.CustomKey.Equals(ConsoleApplication1.Program.CustomKey, ConsoleApplication1.Program.CustomKey)": не найден метод, пригодный для переопределения

КастомКей имеет три поля размер контрольная сумма и путь
Я правильно понял?

Код


 public class CustomKey
        {
            public long length;
            public int Code;
            public string path;
                       public CustomKey(long l, int k)
            {
                this.length = l;
                this.Code = k;
            }
            public CustomKey(long l)
            {
                this.length =l;
                this.Code =0;
            }

            public override bool Equals(object obj)
            {
                CustomKey lk = obj as CustomKey;
                if (length != lk.length) return false;
                else
                    if (GetHashCode() != lk.GetHashCode()) return false;
                    else
                        return true;
            }
            public override int GetHashCode()
            {
                uint crc = 0;
                byte[] data = new Byte[1024];
                FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);

                fs.Read(data, 0, 1024);
                crc =Comparer.CRC32.Compute(data);
                return (int)crc;
            }

        }

Это сообщение отредактировал(а) Neox_GeForce - 23.5.2009, 22:05

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

Neox_GeForce

Дата 23.5.2009, 22:35 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Любитель @ 23.5.2009, 20:54)

Если получили - добавляем элемент в полученный список.

Код


List<string> filesList;
if (!filesInfo.TryGetValue(key, out filesList))
{
    filesList = new List<string>();
    filesInfo.Add(key, filesList);
}

filesList.Add(fileName);

словарь у тя такой

Код


 Dictionary<CustomKey,List<string>> filesInfo = new Dictionary<CustomKey,List<string>>();

Вот какой у меня код

Код


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Diagnostics;
namespace ConsoleApplication1
{
    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 (UnauthorizedAccessException)
                {
                    Console.WriteLine("Cannot open directory ({0})", dir);
                }
                catch (DirectoryNotFoundException )
                {
                    Console.WriteLine("Каталог ("+"{0}"+") не существует",dir);
                }
            }
            return result;
        }
    }
    public class CustomKey
        {
            private long length;
            private int Code;
            private string path;
           public CustomKey(long l, int k)
            {
                this.length = l;
                this.Code = k;
            }
            public CustomKey(string path)
            {
                FileInfo fl = new FileInfo(path);
               this.length= fl.Length;
               this.path= fl.FullName;
            }

            public override bool Equals(object obj)
            {
                CustomKey lk = obj as CustomKey;
                if (length != lk.length) return false;
                else
                    if (GetHashCode() != lk.GetHashCode()) return false;
                    else
                        return true;
            }
            public override int GetHashCode()
            {
                uint crc = 0;
                byte[] data = new Byte[1024];
                FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);

                fs.Read(data, 0, 1024);
                crc =Comparer.CRC32.Compute(data);
                return (int)crc;
            }

        }
    class Program
    {
       
        static void Main(string[] args)
        {
            try
            {
                Stopwatch st = new Stopwatch();
                st.Start();
                
                Dictionary<CustomKey,List<string>> filesInfo = new Dictionary<CustomKey,List<string>>();
                List<string> filelist = FileHelper.GetFilesRecursive("E:\\Compare"); //Список файлов каталога
          
                for (int i = 0; i < filelist.Count; i++)
                {
                    CustomKey temp= new CustomKey(filelist[i]);
                    List<string> filesList;
                    if (!filesInfo.TryGetValue(temp, out filesList))
                    {
                        filesList = new List<string>();
                        filesInfo.Add(temp, filesList);
                    }

                    filesList.Add(filelist[i]);
                }

             Console.WriteLine("\n{0}", st.ElapsedMilliseconds);
              
            }
            catch (IndexOutOfRangeException )
            {
                Console.WriteLine("Помилка!\nНе введено каталог пошуку!");
            }
            catch(Exception e)
            {
                Console.WriteLine("Неожиданная ошибка! \n", e.Message);
            }
            Console.ReadLine();
        }
        
    }
}

З.Ы неработает подсветка

Это сообщение отредактировал(а) Neox_GeForce - 24.5.2009, 11:06

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

Любитель

Дата 24.5.2009, 10:52 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Цитата(Neox_GeForce @ 23.5.2009, 22:35

)

код какой то не ясный. ЧТо он делает?

Пытается получить список файлов для определённого ключа, если нету такого - создаёт новый список и добавляет его на этот ключ в словарь. Затем добавляет файл в список. Всё просто.

GetHashCode ты не правильно переопределил. В данном случае выигрыша ноль (Dictionary будет всегда вызывать твой GetHashCode, да и ещё он у тебя не кешируется). Я бы вообще вернул в GetHashCode length. А в Equals:

Код


CustomKey otherKey = obj as CustomKey;
return otherKey != null && otherKey.length == this.length && otherKey.Hash == this.Hash;

Где Hash - прайват проперти:

Код


private uint? hash = null;

private uint Hash
{
    get
    {
        if (hash == null)
        {
            // твой рассчёт хеша, сохраняешь в поле hash
        }

        return hash.Value;
    }
}

Вот как-то так.

И ещё - зачем тебе два прохода по файлам? Можно вместо result.AddRange(Directory.GetFiles(dir, "*.*")); сразу сделать foreach по файлам каталога и добавить их (как описано выше) в dictionary.

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

http://oryolalex.mybrute.com

Neox_GeForce

Дата 24.5.2009, 12:19 (ссылка)

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

Загрузка ...

Опытный

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

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

у меня выскакивает exception. отказано в доступе. как побороть то?
и

Код


return (int)crc;

не видно из-за блока try

Код


    public override int GetHashCode()
            {
                try
                {
                    uint crc = 0;
                    byte[] data = new Byte[1024];
                    FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);
                    fs.Read(data, 0, 1024);
                    crc = Comparer.CRC32.Compute(data);
                    return (int)crc;
                }
                catch (Exception e)
                {
                   Console.WriteLine("Ошибка! {0}", e.Message);
               }
            }

Это сообщение отредактировал(а) Neox_GeForce - 24.5.2009, 12:32

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

Neox_GeForce

Дата 24.5.2009, 17:05 (ссылка)

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

Загрузка ...

Опытный

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

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

Сделал.
Протестите пожалуйста.
Задание у мя было такое:
Найти одинаковые файлы по содержимому и вывести группы одинаковых файлов.

Кажется работает

Это сообщение отредактировал(а) Neox_GeForce - 24.5.2009, 20:56

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

Comparer.rar 73,77 Kb

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

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