Usuwanie duplikatów z pliku


(Drobok) #1

Otóż mam spory problem. Mam duży plik i muszę z niego wywalić wszystkie powtarzające się wersy.

Mogę to zrobić sprawdzając czy dany wers jest różny od poprzednich, a jak jest zapisać go do innego pliku lub jak nie jest usunąć. Ale szukam bardziej optymalnej metody. Bowiem jeśli będzie on musiał przeszukać 30-40tyś wersów to raczej długo to potrwa ;/


(Tomek Matz) #2

Czy musisz zachować kolejność tych wersów? Jeśli nie to spróbuj może na razie najprostszego rozwiązania i zobacz ile to zajmie czasu, a więc ... wczytujesz wszystko do pamięci (nie wiem jak długie masz te wersy, ale myślę, że powinieneś się zmieścić w 50MB), sortujesz, a następnie przechodzisz pętlą i porównujesz w niej dany wers z następnym. Jeśli ten dany wers jest inny niż ten następny to wrzucasz go do osobnej kolekcji (bądź zapisujesz od razu do pliku), a jeśli jest taki sam to nic z nim nie robisz.


(Grzelix) #3

Mój pierwszy pomysł jaki przyszedł mi do głowy to tworzysz tablicę hash'y wersów z pliku przy pomocy jakieś funkcji (sha, md5) - i porównujesz dane z tablicy podwzględem powtórzeń

to powinno zmiejszyć wielkość potrzebnej pamięci i czasu porównywania napisów.


(Tomek Matz) #4

@grzelix

Nie wiem, czy rozumiem. Czyli chciałbyś wczytywać wiersz, tworzyć hash i patrzeć, czy taki wiersz już istnieje w słowniku? Całkiem fajne rozwiązanie, ale pytanie na ile czasochłonne będzie tworzenie hasha dla każdego z 40 tyś wierszy. Być może będzie to szybsze rozwiązanie, a być może nie. IMO ciężko ocenić.


(floyd) #5

Jeżeli to plik tekstowy, to w programie:


(Tomek Matz) #6

Usiadłem i naskrobałem to swoje rozwiązanie. Tutaj link: https://rapidshare.com/files/1149629710/DuplicateFinder.exe. Po wybraniu pliku za pomocą przycisku Open, musisz z listy rozwijanej wybrać kodowanie w jakim został ten plik zapisany (przy użyciu takiego samego kodowania zostanie zapisany wynikowy plik), a następnie nacisnąć przycisk Find.

PS Żeby uruchomić ten program musisz zainstalować http://www.dobreprogramy.pl/NET-Framework,Program,Windows,17632.html.


(floyd) #7

Moje gratulacje. Jestem pod wrażeniem szybkości działania programu. Wydaje mi się, że nie jest to jednak zasługa użytego algorytmu, ale języka w którym procedura usuwania duplikatów została napisana. :slight_smile:


(Tomek Matz) #8

Być może tak właśnie jest. Mimo to możesz popatrzeć u siebie w kodzie, czy czegoś nie możesz zmienić. Może to być wspomniany algorytm, może to być zamiana jednego wbudowanego typu na jakiś inny (bardziej odpowiedni do tego zadania) lub użycie innej wbudowanej metody zamiast jednej z tych, które aktualnie używasz (tak wiem takie testowanie jest czasochłonne). W przypadku tak dużej ilości iteracji mały szczegół może b. negatywnie wpłynąć na działanie całego programu. Ja jeszcze trochę podłubałem w tym swoim kodzie. Oto nowa wersja: https://rapidshare.com/files/1191679322/DuplicateFinder.exe. Teraz kod działa szybciej, a wiersze do wynikowego pliku wstawianej są we właściwej kolejności.

-- Dodane 14.05.2011 (So) 23:49 --

Dodałem do tego programu dwie opcje (zaktualizowałem powyższy link), a mianowicie ignorowanie wielkości liter, a także ignorowanie spacji oraz tabulatorów przy porównywaniu wierszy. Tak więc po zaznaczeniu Ignore case i Ignore whitespace to zdanie:

sA s SS 123

będzie równe temu zdaniu:

sa s ss 123


(floyd) #9

Święte słowa. :slight_smile: Wszyscy wiemy, że np. różne instrukcje mają też różne czasy wykonywania. W praktyce często o tym zapominamy w szczególności gdy jakaś instrukcja powtarza się tylko kilka razy. Bardzo zaskoczyło mnie, że np.

łączenie zbiorów typu: zbior=zbior&tekst jest tak czasochłonne. Przebieg pustej pętli nawet 40000 razy trwa co najwyżej kilka sekund, a gdy umieścimy w niej właśnie :zbior=zbior&tekst to czas wykonania takiej pętli urasta do nawet kilkunastu minut. Również wykonywanie operacji na dużych zbiorach też jest bardziej czasochłonne. Moja pętla była bardzo prosta i właściwie był w niej tylko jedno zapytanie i jedna instrukcja, a mimo to czas przebiegu pętli był długi. Wystarczyło tylko zmienić aby bardziej czasochłonne instrukcje wykonywane były rzadziej i czas wykonywania pętli skrócił się z 45 minut do 5 minut. Pozdrawiam.


(somekind) #10

Nie jest to na pewno zasługa języka, no chyba że chcesz porównywać język kompilowany z jakimś skryptowym, bo takie faktycznie potrafią być sporo wolniejsze.

Wpływ na szybkość programu ma użycie właściwego algorytmów, odpowiednia struktura aplikacji, a język jest może dopiero na trzecim miejscu, o ile oczywiście odpowiednio się go użyje. Język ma dużo większy wpływ na szybkość napisania programu.

W tym przypadku, gdyby matzu nie posortował wierszy przed ich porównaniem, algorytm wyszukujący duplikaty miałby znacznie większą złożoność obliczeniową (porównanie każdy z każdym zamiast każdy z następnym) i w żadnym języku nie byłby szybki.

IMHO, przebieg pustej pętli nie trwa w ogóle, bo kompilator nie powinien w ogóle umieścić czegoś takiego w pliku wynikowym. :slight_smile:

matzu , bardzo fajny i nieźle wykonany programik, ale mam parę uwag:

1) O ile naturalne jest użycie List dla outputRows, to inputRows mogłyby być zwykłą tablicą. Wszakże z pliku wczytujesz tablicę, a potem przetwarzasz ją tylko w zwykłej pętli for. Lista nie ma w tym przypadku uzasadnienia. (No chyba, że ja czegoś nie widzę, a Ty masz jakieś.)

2) Rzucanie zdarzenia OnProgressChanged w każdej iteracji pętli jest bez sensu. Zazwyczaj nie da ono żadnego skutku, gdyż wartość postępu w kolejnych iteracjach różni się niewiele. Za to rzucenie zdarzenia kosztuje, a ponieważ dzieje się to w pętli może znacząco spowalniać cały program.

Moim zdaniem mógłbyś to zoptymalizować dzieląc liczbę wierszy wejściowych przez liczbę kroków postępu (80, bo chyba tyle kroków postępu przeznaczasz na algorytm, chociaż ja bym raczej zrobił bardziej uniwersalnie - 100). Wtedy wiedziałbyś, co ile wierszy jest w ogóle sens zaraportować zmianę. W pętli mógłbyś sprawdzić czy zmienna i jest wielokrotnością tej liczby i tylko wtedy rzucić zdarzenie.

3) Metoda Display():

a) Ta metoda powinna być tak naprawdę w klasie DuplicateFinderResult, bo przecież jej celem jest wyświetlenie informacji o wyniku wyszukiwania, a informacje o nim trzymasz właśnie w obiekcie tej klasy.

b) Jej implementacja jest... eufemistycznie mówiąc, najsłabszym i najmniej czytelnym punktem Twojego programu. Wygląda jak połączenie asemblera z Cobolem. Tak się nie buduje łańcuchów znaków, zamiast tablicy stringów i Concat powinieneś użyć klasy StringBuilder.


(Tomek Matz) #11

@somekind

Wydaje mi się, że posiadasz tą starą wersję programu (która oparta była na tym sposobie z sortowaniem i prostą pętlą). Ta nowa zawarta jest w moim ostatnim poście (oparta jest na typie Hashset, który IMO jest genialny, i też prostej pętli). BTW plik otworzyłeś w ildasm, czy w czymś innym?

AD 1)

odnośnie outputRows:

jest to zmienna typu Hashset. Dzięki użyciu tego typu mogłem zrezygnować z sortowania i dzięki temu wyjściowe wersy wstawiane są do wynikowego pliku we właściwej kolejności (tzn. nieposortowane).

odnośnie inputRows:

wiersze wczytuję z pliku do tablicy string[], ale później iteruję po nich, żeby usunąć puste wiersze, bądź wiersze zawierające tylko i wyłącznie spacje lub/i tabulatory (taki nieopisany feature). Z racji tego, że nie wiem ile będzie takich wierszy, no to inputRows jest typu List. Ale zgadzam się, że gdybym tego nie robił to najlepszym wyborem jest zwykła tablica.

AD 2) Tak na algorytm przeznaczyłem 80% całego progressbara. Na upartego mógłbym dać więcej, o ile nie nawet 100% (o czym wspominasz). Robiłem to trochę na wyczucie, bo nie wiem jak duże ma te pliki autor tematu i nie wiem jak wpłynęło by to na czas ich wczytywania i zapisywania.

Zgadzam się z tym, że tak częste wywoływanie tego zdarzenia nie ma sensu. Nie poprawiłem tego z czystego lenistwa :smiley: Gdy program zamykał mi się już w czasie poniżej 2sek to stwierdziłem, że może tak na razie zostać. Ale gdybym to zmieniał to plan był, żeby zrobić dokładnie to o czym piszesz.

AD 3)

a) Tej klasy już nie ma. Uznałem, że jest ona niepotrzebna. Początkowo chciałem, żeby metoda Find zwracała obiekt tego typu, tj. DuplicateFinderResult, który przechowywałby informacje o czasie wykonania, wynikowe wiersze, itd. Ostatecznie uznałem, że lepiej będzie, gdy zachowam jedną klasę, tj. DuplicateFinder, a metoda Find nie będzie nic zwracać, a jedynie modyfikować zmienne w obrębie klasy. Ale faktycznie, gdy ta klasa jeszcze była to lepiej byłoby umieścić w niej Display().

b) Tutaj się nie zgadzam. IMO jest ok. Oto kod:

public string Display()

{

    return "Duration: " + Duration.ToString() + ".\n\n"

        + "Distinct rows count: " + DistinctRowsCount.ToString() + ".\n"

        + "Duplicate rows count: " + DuplicateRowsCount.ToString() + ".\n"

        + "Total rows count: " + TotalRowsCount.ToString() + ".\n\n"

        + "Output file: " + outputFilePath + ".";

}

Choć w sumie teraz jak tak patrzę to tą metodę powinienem wywalić, a jej kod wrzucić do przeciążonej metody ToString(), co zaraz zrobię :slight_smile: PS Dzięki za konstruktywną krytykę. DuplicateFinder.cs

using System;

using System.Collections.Generic;

using System.IO;

using System.Text;


namespace DuplicateFinder

{

    public class DuplicateFinder

    {

        public delegate void ProgressChangedHandler(object sender, MyEventArgs.ProgressChangedEventArgs e);

        public event ProgressChangedHandler ProgressChanged;


        private string inputFilePath;

        private string outputFilePath;

        private Encoding fileEncoding;

        private List inputRows;

        private HashSet outputRows;

        private DateTime startTime;

        private DateTime stopTime;


        public DuplicateFinder()

        {

            this.inputFilePath = string.Empty;

            this.outputFilePath = string.Empty;

            this.fileEncoding = null;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public DuplicateFinder(string inputFilePath, string outputFilePath, Encoding fileEncoding)

        {

            this.inputFilePath = inputFilePath;

            this.outputFilePath = outputFilePath;

            this.fileEncoding = fileEncoding;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public string InputFilePath

        {

            get { return inputFilePath; }

            set { inputFilePath = value; }

        }

        public string OutputFilePath

        {

            get { return outputFilePath; }

            set { outputFilePath = value; }

        }

        public Encoding FileEncoding

        {

            get { return fileEncoding; }

            set { fileEncoding = value; }

        }

        public List InputRows

        {

            get { return inputRows; }

        }

        public HashSet OutputRows

        {

            get { return outputRows; }

        }

        public DateTime StartTime

        {

            get { return startTime; }

        }

        public DateTime StopTime

        {

            get { return stopTime; }

        }

        public TimeSpan Duration

        {

            get { return StopTime.Subtract(StartTime); }

        }

        public int TotalRowsCount

        {

            get { return inputRows.Count; }

        }

        public int DistinctRowsCount

        {

            get { return outputRows.Count; }

        }

        public int DuplicateRowsCount

        {

            get { return TotalRowsCount - DistinctRowsCount; }

        }


        public void OnProgressChanged(object sender, MyEventArgs.ProgressChangedEventArgs e)

        {

            if (ProgressChanged != null)

                ProgressChanged(sender, e);

        }


        public void Clear()

        {

            inputRows.Clear();

            outputRows.Clear();

        }


        public string GetDefaultOutputFilePath()

        {

            return Path.Combine(

                Path.GetDirectoryName(inputFilePath),

                Path.GetFileNameWithoutExtension(inputFilePath) + "Result" + Path.GetExtension(inputFilePath)

                );

        }


        public void Read()

        {

            this.Clear();


            if (File.Exists(inputFilePath))

            {

                string[] copy = File.ReadAllLines(inputFilePath, fileEncoding);

                for (int i = 0; i < copy.Length; i++)

                {

                    if (!string.IsNullOrEmpty(copy[i].Trim()))

                        inputRows.Add(copy[i]);

                }

            }

        }


        public void Write()

        {

            File.WriteAllLines(outputFilePath, outputRows, fileEncoding);

        }


        public void Find(bool ignoreCase, bool ignoreWhitespace)

        {

            this.OnProgressChanged(this, new MyEventArgs.ProgressChangedEventArgs(0));


            // Read file (10% of total progress)

            startTime = DateTime.Now;

            this.Read();

            this.OnProgressChanged(this, new MyEventArgs.ProgressChangedEventArgs(10));


            // Find duplicates (80% of total progress)

            if (ignoreCase || ignoreWhitespace)

            {

                HashSet set = new HashSet();

                string row = string.Empty;

                for (int i = 0; i < inputRows.Count; i++)

                {

                    row = this.FindHelper(inputRows[i], ignoreCase, ignoreWhitespace);

                    if (!set.Contains(row))

                    {

                        set.Add(row);

                        outputRows.Add(inputRows[i]);

                    }


                    this.OnProgressChanged(this, new MyEventArgs.ProgressChangedEventArgs((int)(((i + 1.0) / inputRows.Count) * 80 + 10.0)));

                }

                set.Clear();

            }

            else

            {

                for (int i = 0; i < inputRows.Count; i++)

                {

                    if (!outputRows.Contains(inputRows[i]))

                        outputRows.Add(inputRows[i]);


                    this.OnProgressChanged(this, new MyEventArgs.ProgressChangedEventArgs((int)(((i + 1.0) / inputRows.Count) * 80 + 10.0)));

                }

            }


            // Write file (10% of total progress)

            this.Write();

            stopTime = DateTime.Now;

            this.OnProgressChanged(this, new MyEventArgs.ProgressChangedEventArgs(100));

        }


        private string FindHelper(string row, bool ignoreCase, bool ignoreWhitespace)

        {

            if (ignoreCase && ignoreWhitespace)

                return row.Trim().Replace(" ", "").Replace("\t", "").ToLower();

            else if (ignoreCase)

                return row.ToLower();

            else if (ignoreWhitespace)

                return row.Trim().Replace(" ", "").Replace("\t", "");

            return row;

        }


        public override string ToString()

        {

            return "Duration: " + Duration.ToString() + ".\n\n"

                + "Distinct rows count: " + DistinctRowsCount.ToString() + ".\n"

                + "Duplicate rows count: " + DuplicateRowsCount.ToString() + ".\n"

                + "Total rows count: " + TotalRowsCount.ToString() + ".\n\n"

                + "Output file: " + outputFilePath + ".";

        }

    }

}

(somekind) #12

Masz racje, analizowałem starą wersję, moje przeoczenie.

ILdasm niewiele by mi dał. :wink: Otwierałem w ILSpy i dla porównania w JustDecompile.

Tak, teraz widzę. Na upartego mógłbyś to jakoś zrobić przy użyciu LINQ. Tylko pewno byłoby wolniejsze, więc niekoniecznie jest sens.

Pytanie na jak dużych danych testowałeś. :slight_smile: Bo ogólnie robić coś i wiedzieć, że to bez sensu jest bez sensu. :stuck_out_tongue:

Ja bym jej nie wyrzucał. Oddzielenie klasy wykonującej operację od klasy reprezentującej jej wynik jest dobrym pomysłem.

Wiesz, nie miałem kodu tej metody Display, ILSpy pokazywał coś bardzo bez sensu, co mnie zmyliło:

public string Display()

{

	string[] array = new string[11];

	array[0] = "Duration: ";

	array[1] = this.Duration.ToString();

	array[2] = ".\n\nDistinct rows count: ";

	string[] arg_40_0 = array;

	int arg_40_1 = 3;

	int num = this.DistinctRowsCount;

	arg_40_0[arg_40_1] = num.ToString();

	array[4] = ".\nDuplicate rows count: ";

	string[] arg_59_0 = array;

	int arg_59_1 = 5;

	num = this.DuplicateRowsCount;

	arg_59_0[arg_59_1] = num.ToString();

	array[6] = ".\nTotal rows count: ";

	string[] arg_72_0 = array;

	int arg_72_1 = 7;

	num = this.TotalRowsCount;

	arg_72_0[arg_72_1] = num.ToString();

	array[8] = ".\n\nOutput file: ";

	array[9] = this.outputFilePath;

	array[10] = ".";

	return string.Concat(array);

}

Ale i tak się przyczepię do Twojej wersji - czytelniej byłoby użyć string.Format zamiast tak to konkatenować.

Będzie jeszcze więcej czepialstwa, ale to jak wstanę i pójdę do pracy. :wink:


(Tomek Matz) #13

Wziąłem sobie stworzyłem pliczek 7,5MB, 100k wierszy. Anyway dziś tą metodę przerobię. Później wrzucę kod. W sumie zauważyłem, że w tej metodzie Find jest potrzebna jeszcze jedna (być może nawet istotniejsza) zmiana. Niepotrzebnie tak często tworzę obiekt klasy ProgressChangedEventArgs.

Prawda, ale miałem problem co zrobić z dwiema zmiennymi i poszedłem po najmniejszej linii oporu. Chodzi o zmienne fileEncoding oraz inputRows. Zmienną inputRows używam do odczytania informacji o TotalRowsCount (mam taką właściwość). Oczywistym jest, że ta informacja jest też potrzebna w klasie DuplicateFinderResult. I teraz pytanie jak to zrobić, żeby to miało ręce i nogi. Można by utworzyć zmienną totalRowsCount w klasie DuplicateFinderResult, ale wtedy mamy w dwóch miejscach tą samą informację. Można by utworzyć zmienną inputRows w klasie DuplicateFinderResult i przekazywać referencję, ale wówczas też mamy w dwóch miejscach tą samą informację. Podobnie jest z fileEncoding, bowiem informacja o tym przy użyciu jakiego kodowania został zapisany wynikowy plik też powinna znaleźć się w klasie DuplicateFinderResult.

W sumie masz rację. BTW znalazłem coś ciekawego. Wcześniej wspominałeś o tym StringBuilder i z ciekawości zerknąłem jak jest z wydajnością w przypadku używania operatora + i klasy StringBuilder. Rezultaty są na prawdę ciekawe: http://weblogs.asp.net/jeff/archive/2004/08/15/214912.aspx.

W porządku. Dla mnie to nie jest czepialstwo, a tak jak napisałem konstruktywna krytyka.

-- Dodane 16.05.2011 (Pn) 14:44 --

https://rapidshare.com/files/1851141828/DuplicateFinder.exe (plik, o którym przed chwilą wspominałem, przerabiam teraz w 200-300 ms).

DuplicateFinder.cs

using System;

using System.Collections.Generic;

using System.IO;

using System.Text;

using DuplicateFinder.MyEventArgs;


namespace DuplicateFinder

{

    public class DuplicateFinder

    {

        public delegate void ProgressChangedHandler(object sender, ProgressChangedEventArgs args);

        public event ProgressChangedHandler ProgressChanged;


        private string inputFilePath;

        private string outputFilePath;

        private Encoding fileEncoding;

        private List inputRows;

        private HashSet outputRows;

        private DateTime startTime;

        private DateTime stopTime;


        public DuplicateFinder()

        {

            this.inputFilePath = string.Empty;

            this.outputFilePath = string.Empty;

            this.fileEncoding = null;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public DuplicateFinder(string inputFilePath, string outputFilePath, Encoding fileEncoding)

        {

            this.inputFilePath = inputFilePath;

            this.outputFilePath = outputFilePath;

            this.fileEncoding = fileEncoding;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public string InputFilePath

        {

            get { return inputFilePath; }

            set { inputFilePath = value; }

        }

        public string OutputFilePath

        {

            get { return outputFilePath; }

            set { outputFilePath = value; }

        }

        public Encoding FileEncoding

        {

            get { return fileEncoding; }

            set { fileEncoding = value; }

        }

        public List InputRows

        {

            get { return inputRows; }

        }

        public HashSet OutputRows

        {

            get { return outputRows; }

        }

        public DateTime StartTime

        {

            get { return startTime; }

        }

        public DateTime StopTime

        {

            get { return stopTime; }

        }

        public TimeSpan Duration

        {

            get { return StopTime.Subtract(StartTime); }

        }

        public int TotalRowsCount

        {

            get { return inputRows.Count; }

        }

        public int DistinctRowsCount

        {

            get { return outputRows.Count; }

        }

        public int DuplicateRowsCount

        {

            get { return TotalRowsCount - DistinctRowsCount; }

        }


        public void OnProgressChanged(ProgressChangedEventArgs args)

        {

            if (ProgressChanged != null)

                ProgressChanged(this, args);

        }


        public bool IsValid()

        {

            if (!string.IsNullOrEmpty(inputFilePath)

                && File.Exists(inputFilePath)

                && fileEncoding != null

                && !string.IsNullOrEmpty(outputFilePath)

                && Directory.Exists(Path.GetDirectoryName(outputFilePath))

                && Path.HasExtension(outputFilePath))

                return true;

            return false;

        }


        public void Clear()

        {

            inputRows.Clear();

            outputRows.Clear();

        }


        public string GetDefaultOutputFilePath()

        {

            return Path.Combine(

                Path.GetDirectoryName(inputFilePath),

                Path.GetFileNameWithoutExtension(inputFilePath) + "Result" + Path.GetExtension(inputFilePath)

                );

        }


        public void Read()

        {

            this.Clear();


            string[] copy = File.ReadAllLines(inputFilePath, fileEncoding);

            for (int i = 0; i < copy.Length; i++)

            {

                if (!string.IsNullOrEmpty(copy[i].Trim()))

                    inputRows.Add(copy[i]);

            }

        }


        public void Write()

        {

            File.WriteAllLines(outputFilePath, outputRows, fileEncoding);

        }


        public void Find(bool ignoreCase, bool ignoreWhitespace)

        {

            ProgressChangedEventArgs args = new ProgressChangedEventArgs(0);

            HashSet rows = new HashSet();

            string row = string.Empty;

            int stepSize = (int)Math.Round(inputRows.Count / 90.0, 0, MidpointRounding.AwayFromZero);

            int stepsSize = stepSize;


            this.OnProgressChanged(args);


            // Read file (5% of total progress)

            startTime = DateTime.Now;

            this.Read();

            args.PercentComplete = 5;

            this.OnProgressChanged(args);


            // Find duplicates (90% of total progress)

            for (int i = 0; i < inputRows.Count; i++)

            {

                if (ignoreCase && ignoreWhitespace)

                    row = inputRows[i].Trim().Replace(" ", "").Replace("\t", "").ToLower();

                else if (ignoreCase)

                    row = inputRows[i].ToLower();

                else if (ignoreWhitespace)

                    row = inputRows[i].Trim().Replace(" ", "").Replace("\t", "");

                else

                    row = inputRows[i];


                if (rows.Add(row))

                    outputRows.Add(inputRows[i]);


                if ((i + 1) == stepsSize)

                {

                    args.PercentComplete += 1;

                    this.OnProgressChanged(args);

                    stepsSize += stepSize;

                }

            }

            rows.Clear();


            // Write file (5% of total progress)

            this.Write();

            stopTime = DateTime.Now;

            args.PercentComplete = 100;

            this.OnProgressChanged(args);

        }


        public override string ToString()

        {

            return String.Format("Duration: {0}.\n\nDistinct rows count: {1}.\nDuplicate rows count: {2}.\nTotal rows count: {3}.\n\nOutput file: {4}.",

                Duration.ToString(), DistinctRowsCount.ToString(), DuplicateRowsCount.ToString(), TotalRowsCount.ToString(), outputFilePath);

        }

    }

}

(somekind) #14

Przepraszam, że tak późno, ale po pierwsze nie zauważyłem scalonego posta, a poza tym byłem ostatnio dość zajęty. :wink:

1) Tak ogólnie, to w C# 3.0 wprowadzono "auto-implement properties". Dzięki nim można zaoszczędzić palców na pisanie oddzielnych pól i właściwości, np:

public string InputFilePath { get; set; }

public string InputFilePath { get; private set; } // nie ustawiane z zewnątrz

2) Wydaje mi się, że InputFilePath, OutputFilePath oraz FileEncoding niepotrzebnie mają settery. Ktoś będzie je zmieniał z zewnątrz po utworzeniu obiektu DuplicateFinder? Ja bym po prostu usunął ten bezparametrowy konstruktor i wymusił przez to podawanie tych danych zawsze przy tworzeniu obiektu.

3) Metoda IsValid() - tam nie trzeba ifa, wystarczy też jeden return. :wink:

4) Nie wywoływałbym Clear z Read. To oddzielne operacje, powinny być wywołane oddzielnie.

5) ToString - te wszystkie wywołania ToString (np. Duration.ToString()) chyba nie są potrzebne.

6) Piszesz trochę niespójnie, bo czasem używasz this, a czasem nie.

No to koniec czepiania się detali. :slight_smile:

Teraz mam do Ciebie małą prośbę. Mógłbyś szybko dodać jeszcze (analogicznie do ignorowania wielkości liter oraz białych znaków, które już masz) trzy nowe opcje: pomijania cyfr, znaków diakrytycznych oraz znaków interpunkcyjnych?


(Fordmtonly) #15

Z tego co widziałem to w poprzednich rozwiązaniach pliki ładowane są w całości do pamięci. Gdyby ktoś chciał zaimplementować

taki sam program ale dla dużych plików (np większych niż dostępny RAM) to proponuję zastosować:

  • algorytm sortowania EXTERNAL MERGE SORT + na etapie merge'owania posortowanych części przy zapisie do wynikowego pliku należy porównywać zapisywaną bieżącą linię z poprzednio już zapisaną. W przypadku gdy identyczne trzeba odrzucić.

(uwaga: ten algorytm nie zapewnia identycznej kolejności linii jak w pliku wsadowym)


(Tomek Matz) #16

Kwestia starych nawyków. Zostawię to tak jak mam teraz. Poza tym ja nie piszę tego samodzielnie, bo od tego są refactor-y.

Tak nie mogę zrobić. To by oznaczało, że w klasie DuplicateFinderForm musiałbym za każdym razem tworzyć nowy obiekt w momencie, gdy użytkownik wybierze nowy plik lub zmieni kodowanie wybranego pliku. Obecnie w zdarzeniu Load formy tworzę sobie obiekt klasy DuplicateFinder, a później w zdarzeniach openButton_Click oraz fileEncodingComboBox_SelectedIndexChanged modyfikuję jedynie właściwości tego obiektu.

Poprawiłem.

Nie są, ale niech będzie widoczne, że mamy tutaj do czynienia ze zmianą typu.

Jest taka ukryta spójność :). Ja zawsze używam this, gdy odwołuję się do metody. Do samych zmiennych odwołuję się bez this. Kwestia starych nawyków.

Tego tak szybko to się nie da zrobić, bo to nie jest taka banalna sprawa. W szczególności problem jest z ignorowaniem znaków diaktrycznych. Anyway ignorowanie znaków diaktrycznych zrobiłem na zasadzie, że jeśli jest np. literka ł,ß lub ä to będą one odpowiednio równe literkom l, ss lub a. Niestety nie mogę zagwarantować, że zadziała to poprawnie z każdą literą w każdym języku (więcej informacji pod tym linkiem http://blogs.msdn.com/b/michkap/archive ... 29747.aspx). Link do nowej wersji programu: https://rapidshare.com/files/2913628870/DuplicateFinder.exe. Zobacz, czy o to Ci chodziło. Jakbyś znalazł jakieś błędy to daj proszę znać. Zaznaczam, że wprowadzenie tych nowych zmian spowodowało spadek wydajności o 2 sek. DuplicateFinder.cs

using System;

using System.Collections.Generic;

using System.IO;

using System.Text;

using DuplicateFinder.MyEventArgs;

using System.Globalization;


namespace DuplicateFinder

{

    public class DuplicateFinder

    {

        public delegate void ProgressChangedHandler(object sender, ProgressChangedEventArgs args);

        public event ProgressChangedHandler ProgressChanged;


        private string inputFilePath;

        private string outputFilePath;

        private Encoding fileEncoding;

        private List inputRows;

        private HashSet outputRows;

        private DateTime startTime;

        private DateTime stopTime;


        public DuplicateFinder()

        {

            this.inputFilePath = string.Empty;

            this.outputFilePath = string.Empty;

            this.fileEncoding = null;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public DuplicateFinder(string inputFilePath, string outputFilePath, Encoding fileEncoding)

        {

            this.inputFilePath = inputFilePath;

            this.outputFilePath = outputFilePath;

            this.fileEncoding = fileEncoding;

            this.inputRows = new List();

            this.outputRows = new HashSet();

            this.startTime = DateTime.Now;

            this.stopTime = DateTime.Now;

        }


        public string InputFilePath

        {

            get { return inputFilePath; }

            set { inputFilePath = value; }

        }

        public string OutputFilePath

        {

            get { return outputFilePath; }

            set { outputFilePath = value; }

        }

        public Encoding FileEncoding

        {

            get { return fileEncoding; }

            set { fileEncoding = value; }

        }

        public List InputRows

        {

            get { return inputRows; }

        }

        public HashSet OutputRows

        {

            get { return outputRows; }

        }

        public DateTime StartTime

        {

            get { return startTime; }

        }

        public DateTime StopTime

        {

            get { return stopTime; }

        }

        public TimeSpan Duration

        {

            get { return StopTime.Subtract(StartTime); }

        }

        public int TotalRowsCount

        {

            get { return inputRows.Count; }

        }

        public int DistinctRowsCount

        {

            get { return outputRows.Count; }

        }

        public int DuplicateRowsCount

        {

            get { return TotalRowsCount - DistinctRowsCount; }

        }


        public void OnProgressChanged(ProgressChangedEventArgs args)

        {

            if (ProgressChanged != null)

                ProgressChanged(this, args);

        }


        public bool IsValid()

        {

            return (!string.IsNullOrEmpty(inputFilePath)

                && File.Exists(inputFilePath)

                && fileEncoding != null

                && !string.IsNullOrEmpty(outputFilePath)

                && Directory.Exists(Path.GetDirectoryName(outputFilePath))

                && Path.HasExtension(outputFilePath));

        }


        public void Clear()

        {

            inputRows.Clear();

            outputRows.Clear();

        }


        public string GetDefaultOutputFilePath()

        {

            return Path.Combine(

                Path.GetDirectoryName(inputFilePath),

                Path.GetFileNameWithoutExtension(inputFilePath) + "Result" + Path.GetExtension(inputFilePath)

                );

        }


        public void Read()

        {

            string[] copy = File.ReadAllLines(inputFilePath, fileEncoding);

            for (int i = 0; i < copy.Length; i++)

            {

                if (!string.IsNullOrEmpty(copy[i].Trim()))

                    inputRows.Add(copy[i]);

            }

        }


        public void Write()

        {

            File.WriteAllLines(outputFilePath, outputRows, fileEncoding);

        }


        public void Find()

        {

            this.Find(false, false, false, false, false);

        }


        public void Find(bool ignoreCase, bool ignoreWhitespace, bool ignoreDigits, bool ignorePunctuationMarks, bool ignoreDiacriticalMarks)

        {

            ProgressChangedEventArgs args = new ProgressChangedEventArgs(0);

            int stepSize = (int)Math.Round(inputRows.Count / 90.0, 0, MidpointRounding.AwayFromZero);

            int stepsSize = stepSize;

            HashSet rows = new HashSet();

            StringBuilder rowBuilder = new StringBuilder();

            string rowString = string.Empty;

            string charString = string.Empty;

            char c = ' ';


            this.OnProgressChanged(args);


            // Read file (5% of total progress)

            startTime = DateTime.Now;

            this.Clear();

            this.Read();

            args.PercentComplete = 5;

            this.OnProgressChanged(args);


            // Find duplicates (90% of total progress)

            for (int i = 0; i < inputRows.Count; i++)

            {

                rowString = inputRows[i].Normalize(NormalizationForm.FormD);

                for (int j = 0; j < rowString.Length; j++)

                {

                    c = rowString[j];

                    charString = c.ToString();


                    if (!(

                    (ignoreWhitespace && char.IsWhiteSpace(c))

                    || (ignoreDigits && char.IsDigit(c))

                    || (ignorePunctuationMarks && char.IsPunctuation(c))

                    || (ignoreDiacriticalMarks && char.GetUnicodeCategory(c) == UnicodeCategory.NonSpacingMark)

                    ))

                    {

                        if (ignoreDiacriticalMarks && Consts._DIACRITICS.ContainsKey(c))

                            charString = Consts._DIACRITICS[c];

                        rowBuilder.Append(charString);

                    }

                }

                rowString = rowBuilder.ToString();

                if (ignoreCase && !string.IsNullOrEmpty(rowString))

                    rowString = rowString.ToLower(CultureInfo.InvariantCulture);


                if (rows.Add(rowString))

                    outputRows.Add(inputRows[i]);

                rowBuilder.Clear();


                if ((i + 1) == stepsSize)

                {

                    args.PercentComplete += 1;

                    this.OnProgressChanged(args);

                    stepsSize += stepSize;

                }

            }

            rows.Clear();


            // Write file (5% of total progress)

            this.Write();

            stopTime = DateTime.Now;

            args.PercentComplete = 100;

            this.OnProgressChanged(args);

        }


        public override string ToString()

        {

            return String.Format("Duration: {0}.\n\nDistinct rows count: {1}.\nDuplicate rows count: {2}.\nTotal rows count: {3}.\n\nOutput file: {4}.",

                Duration.ToString(), DistinctRowsCount.ToString(), DuplicateRowsCount.ToString(), TotalRowsCount.ToString(), outputFilePath);

        }

    }

}

-- Dodane 18.05.2011 (Śr) 21:41 --

Podmieniłem mały duperel w programie (link zaktualizowałem).


(somekind) #17

Rozumiem. :slight_smile: Ale chyba łatwiej napisać prop, wcisnąć TAB i wpisać nazwę typu oraz właściwości i gotowe.

Mniej kodu oznacza czytelniejszy i łatwiejszy do utrzymania kod.

I tak chyba powinno być. Ustawiasz jakieś opcje, tworzysz nowy obiekt i nakazujesz mu działać. To, jak teraz to jest zaimplementowane sugeruje, że można zmienić te właściwości podczas wykonywania metody Find, a to by było bez sensu. To tak jakby w podróży rakietą na Księżyc w połowie drogi zmienić środek transportu na tramwaj.

Jeszcze co do tej metody IsValid, czemu to metoda, a nie właściwość?

Zmiany typu żadnej akurat tu nie ma. :slight_smile:

To takie dziwne te nawyki, pierwszy raz z takim rozróżnieniem się spotykam. Ja zawsze używam this - daje mi to na pierwszy rzut oka informację o tym czy odwołuję się do metody instancyjnej czy statycznej albo czy do pola klasy czy argumentu metody.

Hmm... a możesz teraz (tak na szybko) dodać jeszcze opcje do ignorowania samogłosek, spółgłosek, znaków używanych w działaniach matematycznych oraz nawiasów?

Tak naprawdę nie chodziło mi o to, żebyś to zaimplementował tylko zobaczył, że coś w Twoim kodzie jest nie tak. Aby dodawać nowe opcje rozbudowujesz drabinkę ifów. Teraz jeszcze dodałeś zagnieżdżoną pętlę w pętli głównej. Sprawdzanie tych wszystkich warunków i ta dodatkowa pętla sprawiają, że program działa wolniej. Ale czy to jest konieczne? Przecież o tym, jak należy przetwarzać każdy wiersz, wiadomo już przed uruchomieniem metody Find. Dlaczego zatem sprawdzać te warunki w każdym kroku pętli od nowa?

Powinieneś raczej przed uruchomieniem metody Find wstrzyknąć do obiektu klasy DuplicateFinder algorytm, za pomocą którego przetworzysz każdy wiersz. Algorytm będzie raz skonfigurowany, więc nie trzeba będzie sprawdzać za każdym razem wszystkich opcji. Poza tym dodanie nowej opcji nie będzie wymagało modyfikowania starego kodu, a jedynie dodania nowego algorytmu. Ergo - będzie łatwiej i wydajniej. Słyszałeś o czymś takim jak wzorzec projektowy strategia?


(Tomek Matz) #18

Jeśli uznać, że jeden return powoduje, że kod jest nieczytelny to faktycznie masz rację :stuck_out_tongue:

Wciąż się nie zgadzam. Tworzenie nowego obiektu w każdym zdarzeniu (click, selectedindexchanged itd.) zamiast po prostu podmiany wartości jednej zmiennej tego obiektu przy użyciu właściwości to lekka przesada. Twoje argumenty mają sens, bo usuwając te set-y zabezpieczamy się przed niepoprawnym użyciem tej klasy. Z drugiej jednak strony skazujemy się na ciągłe tworzenie nowego obiektu. Pytanie co jest lepsze? To już chyba kwestia własnej oceny. Jeśli kod będzie napisany z głową to nie nastąpi przypadkowa podmiana wartości którejś ze zmiennych w trakcie wykonywania metody Find.

Słuszna uwaga.

Faktycznie, nieprecyzyjnie się wyraziłem. Miałem na myśli niejawne rzutowanie.

Mógłbyś wrzucić fragment kodu, żebym mógł sprawdzić, czy to faktycznie będzie wydajniejsze rozwiązanie?


(somekind) #19

Chodziło mi bardziej o nadmiarowy kod związany z polami i właściwościami.

A co do tego nieszczęsnego return:

if (true)

    return true;

else

    return false;

Sam przyznaj, że wygląda to raczej dziwnie niż nieczytelnie.

To przyzwolenie czy nawet skazanie się na wystąpienie efektu ubocznego. Jakiś kod, być może zupełnie gdzie indziej wywołany nagle zmieni coś w obiekcie i to wszystko się wywali. Dopóki Ty będziesz pisał ten kod i dopóki będziesz o tym pamiętał, to nic złego się nie stanie. Ale w prawdziwych programach pisanych w pracy takie coś to skazanie się na problemy.

I jest nieeleganckie - obiekt powinien być tworzony po kliknięciu w przycisk wywołujący akcję na czas jednego zadania. Nie ma sensu istnienie tego obiektu ani przedtem ani później.

A co do kontrolek użytkownika - interfejs powinien być "wyłączany" (wszystkie checkboxy, comboboxy, itd.) na czas operacji i wznawiany po jej zakończeniu.

Serio mi nie wierzysz, że wywoływanie jednej ściśle określonej metody jest "tańsze" niż sprawdzanie kilku czy więcej warunków w każdym kroku pętli? I że łatwiej napisać nową metodę implementującą jakiś algorytm przetwarzający wiersz niż modyfikować ify?

Mógłbym wrzucić kod, ale dopiero jak wrócę z gór za jakieś 10 dni. :wink:


(Tomek Matz) #20

Ten argument mnie przekonuje. W tym programie rzeczywiście mogę tak zrobić.

W momencie, gdy zostanie naciśnięty przycisk Znajdź i metoda Find nie dokończy działania, to ponowne wciśnięcie tego przycisku nie spowoduje żadnej akcji. Całkowicie wyłączać kontrolek nie chciałem. Niech sobie ktoś tam klika. Myślałem jedynie, czy nie zmienić etykiety ze Znajdź na Przerwij i tym samym zmienić akcję danego przycisku, ale to już tak w wolnej chwili, bo to taki duperel.

To szkoda, bo byłem ciekaw innego spojrzenia na ten problem. No ale wypoczywaj tam :slight_smile: Anyway jak wrócisz to jak będziesz miał chwilę to usiądź do tego, bo problem wciąż będzie aktualny. BTW patrzyłeś na ten link, co wcześniej wkleiłem odnośnie usuwania znaków diaktrycznych? Czy znasz może jakiś lepszy sposób jak sobie z tym poradzić (bo to dziś dla mnie była niezła łamigłówka)?

Nowy link do programu: http://www.speedyshare.com/files/29658968/DuplicateFinder.zip

Nowy link do zdjęcia programu: http://i55.tinypic.com/118m5nk.png

using System;

using System.Text;

using System.IO;

using DuplicateFinder.MyDelegates;

using DuplicateFinder.MyEventArgs;

using DuplicateFinder.FileProcessingLogic;


namespace DuplicateFinder

{

    public class DuplicateFinder

    {

        public event ProgressChangedHandler ProgressChanged;


        public DuplicateFinder(string inputFilePath, string outputFilePath, string logFilePath, Encoding fileEncoding)

        {

            InputFilePath = inputFilePath;

            OutputFilePath = outputFilePath;

            LogFilePath = logFilePath;

            FileEncoding = fileEncoding;

        }


        public string InputFilePath { get; private set; }

        public string OutputFilePath { get; private set; }

        public string LogFilePath { get; private set; }

        public Encoding FileEncoding { get; private set; }

        public bool IsValid

        {

            get

            {

                return (!string.IsNullOrEmpty(InputFilePath)

                && File.Exists(InputFilePath)

                && FileEncoding != null

                && !string.IsNullOrEmpty(OutputFilePath)

                && Directory.Exists(Path.GetDirectoryName(OutputFilePath))

                && !string.IsNullOrEmpty(Path.GetFileName(OutputFilePath))

                && Path.HasExtension(OutputFilePath)

                && !string.IsNullOrEmpty(LogFilePath)

                && Directory.Exists(Path.GetDirectoryName(LogFilePath))

                && !string.IsNullOrEmpty(Path.GetFileName(LogFilePath))

                && Path.HasExtension(LogFilePath)

                );

            }

        }


        public static string GetDefaultOutputDirectoryPath(string inputFilePath)

        {

            string result = string.Empty;


            try

            {

                result = Path.GetDirectoryName(inputFilePath);

            }

            catch (Exception ex) { }


            return result;

        }


        public static string GetDefaultOutputFilePath(string outputDirectoryPath, string inputFilePath)

        {

            string result = string.Empty;


            try

            {

                if (Directory.Exists(outputDirectoryPath))

                {

                    result = Path.Combine(

                        outputDirectoryPath,

                        string.Format("{0}{1}{2}", Path.GetFileNameWithoutExtension(inputFilePath), "Result", Path.GetExtension(inputFilePath))

                        );

                }

            }

            catch (Exception ex) { }


            return result;

        }


        public static string GetDefaultLogFilePath(string outputFilePath)

        {

            string result = string.Empty;


            try

            {

                result = Path.Combine(

                    Path.GetDirectoryName(outputFilePath),

                    string.Format("{0}{1}", Path.GetFileNameWithoutExtension(outputFilePath), "Log.txt")

                    );

            }

            catch (Exception ex) { }


            return result;

        }


        public DuplicateFinderResult Find(bool storeCopyInRAM,

            bool ignoreCase,

            bool ignoreWhitespace,

            bool ignoreDigits,

            bool ignorePunctuationMarks,

            bool ignoreDiacriticalMarks)

        {

            DuplicateFinderParameters parameters = new DuplicateFinderParameters(InputFilePath, OutputFilePath, LogFilePath, FileEncoding,

                storeCopyInRAM, ignoreCase, ignoreWhitespace, ignoreDigits, ignorePunctuationMarks, ignoreDiacriticalMarks);


            FileProcessor fileProcessor = FileProcessorFactory.CreateFileProcessor(parameters);

            fileProcessor.ProgressChanged += new ProgressChangedHandler(fileProcessor_ProgressChanged);


            return fileProcessor.Process();

        }


        protected void OnProgressChanged(ProgressChangedEventArgs args)

        {

            if (ProgressChanged != null)

                ProgressChanged(this, args);

        }


        protected void fileProcessor_ProgressChanged(object sender, ProgressChangedEventArgs args)

        {

            OnProgressChanged(args);

        }

    }

}

-- Dodane 31.07.2011 (N) 21:01 --

Wprowadziłem kilka zmian w programie (powyższy link został zaktualizowany) :slight_smile: Przede wszystkim przebudowany został kod całej aplikacji, żeby było łatwiejsze jej modyfikowanie. Pojawiły się także dwie nowe opcje w GUI. Jedna pozwala na określenie folderu, w którym ma zostać zapisany wynikowy plik, a druga pozwala określić, czy przy przetwarzaniu pliku powinna być używana w większym stopniu pamięć operacyjna, czy też dysk twardy. Rozwiązanie oparte na dysku twardym jest rozwiązaniem o wiele mniej wydajnym, ale pozwoli na przetwarzanie większych plików na komputerach, które posiadają niewystarczającą ilość pamięci operacyjnej. W przypadku rozwiązania opartego na większym wykorzystaniu pamięci operacyjnej zmniejszyłem znacząco jej użycie. Z takich drobnych zmian dodałem w podsumowaniu informację o ilości pustych wierszy, a w folderze z plikiem wynikowym tworzony jest oprócz niego log. Dodałem także wyświetlanie komunikatów błędów i poprawiłem pasek postępu (nie działał prawidłowo).