Usuwanie duplikatów z dużych list adresów > 100K

[Darek_C++]

Jak wydajnie zrealizować usuwanie duplikatów z dużych list np 100 tysięcy lini adresów w pliku.
- jakim mechanizmem załadować plik i odczytać z niego linia po lini ?
- jakim mechanizmem sprawdzać duplikaty np wczytując do kontenera STL map i przed każdym nowym wczytaniem sprawdzać czy dany ciąg znaków już w nim się znajduje. ?
- no i samo zapisanie w nowym pliku jeszcze zostaje

[polymorphism]

Zamiast mapy, użyj std::set.

[Darek_C++]

A jak do tego kontenera wydajnie wczytać dane z pliku zawierającego tyle lini ?
Przed dodaniem nastęgo "rekordu" odczytanego z linii pliku mam sprawdzać występowanie metodą find http://www.cplusplus.com/reference/stl/set/find/ ?

[polymorphism]

Po prostu wstawiaj do kontenera kolejne linie, on sam będzie sprawdzał, czy już dodałeś element o takiej samej wartości (set jest kontenerem uporządkowanym, przechowującym unikalne wartości).

[Darek_C++]

(set jest kontenerem uporządkowanym, przechowującym unikalne wartości).

No to o to chodziło
---------
Działa w wypadku liczb, ale jak chce władować "stringi" :

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

        set<string> txt;
        set<string>::iterator it;
        txt.insert("link 1");
        txt.insert("link 2");

Wywala błąd [C++ Error] functional(134): E2093 'operator<' not implemented in type 'string' for arguments of the same type

[Darek_C++]

Nie działało z mojej winy, bo nie dodałem:
#include <string>

/* dziwne byłem zalogowany i nie mogłem edytować poprzedniego postu */
-------
OK to wiem już jaki mechanizm wykorzystać by mieć tylko unikalne dane, ale jak to zapisać do pliku ?

[Cyfrowy Baron]

/* dziwne byłem zalogowany i nie mogłem edytować poprzedniego postu */

Kwestia ustawień forum. Już to zmieniłem.

[Darek_C++]

Mam taki kod:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

void __fastcall TForm3::Button3Click(TObject *Sender)
{
        if(OpenTextFileDialog1->Execute())
        {
                float Start = GetTickCount();
                Button3->Enabled = false;
                String nzpliku = OpenTextFileDialog1->FileName;

                ifstream plik(nzpliku.c_str());
                if (!plik.is_open())
                {
                        return;
                }
                set<string> mylinki;
                set<string>::iterator itl;
                string sLine;
                int jj =0;
                while (getline(plik, sLine))
                {
                        mylinki.insert(sLine);
                        jj++;
                }
                Memo1->Lines->Add("Wczytano linii: "+(String)jj);

                String out = ExtractFileDir(Application->ExeName) + "\\Test_out.txt";
                jj =0;

                ofstream oFileOut(out.c_str());
                for (itl=mylinki.begin(); itl!=mylinki.end(); itl++)
                {
                        oFileOut << *itl+"\r\n";
                        jj++;
                }
                oFileOut.close();
                plik.close();
                Button3->Enabled = true;
                float End = GetTickCount();
                Edit1->Text = FloatToStr((End - Start) / 1000) + " s.";

                Memo1->Lines->Add("Zapisano linii: "+(String)jj);

        }
}

Wykonanie:
Wczytano linii: 254279
Zapisano linii: 252812
23,672 s.
---
Wczytano linii: 846429
Zapisano linii: 842429
87,328 s.

Pytanie brzmi czy idzie ten kod poprawić pod kątem wydajności ?

[polymorphism]

Te wyniki, jak sądzę, są robione dla wersji debug. Takie pomiary są mało wiarygodne, ponieważ wersja debug jest z reguły dużo wolniejsza od wersji release. Dla porównania czasy wczytywania 1'700'000 linii:

• debug - 72.6sek
• release - 8.7sek

Wersja release jest 8x szybsza!

Niestety problem, i to poważny, jest w innym miejscu. Tym miejscem jest destruktor, a raczej metoda/algorytm odpowiedzialny za usuwanie elementów z set'a. W wersji release usuwanie trwało 4.3 minuty, zatem wersja debug prawdopodobnie usuwałaby prawie 35 min! Porażka. Ktoś tu dał ciała.

Trzeba do problemu podejść z innej strony. Więc pytanie: co to za adresy, skąd one pochodzą, jak często się zmieniają itd.?

[Darek_C++]

Te wyniki, jak sądzę, są robione dla wersji debug. Takie pomiary są mało wiarygodne, ponieważ wersja debug jest z reguły dużo wolniejsza od wersji release. Dla porównania czasy wczytywania 1'700'000 linii:

U mnie ta różnica jest mała:

Dla Debug_Build:
Wczytano linii: 214541
Zapisano linii: 214541
23,453 s.
---------------
Dla Release_Build:
Wczytano linii: 214541
Zapisano linii: 214541
20,172 s.

Trzeba do problemu podejść z innej strony. Więc pytanie: co to za adresy, skąd one pochodzą, jak często się zmieniają itd.?

Jest to lista adresów serwisów www. Skąd pochodzą nie ma znaczenia, bo chodzi o usunięcie duplikatów niezależnie do źródła danych.

Czasy jakie uzyskałem nie są aż tak duże, ale dla porównania ten program http://www.scrapebox.com/free-dupe-remove robi to znacznieeee szybciej wiec istnieje wydajniejszy algorytm przedmiotowej operacji.... "Also it can remove duplicate URL’s and duplicate domains from files as large as 180 Million lines long in just a few seconds."

[polymorphism]

U mnie ta różnica jest mała:

Coś musisz mieć źle ustawione, bo to nie możliwe, żeby nasze czasy aż tak się różniły (szczególnie że u mnie było kilka razy więcej linii do wczytania).

(...) program http://www.scrapebox.com/free-dupe-remove robi to znacznieeee szybciej wiec istnieje wydajniejszy algorytm przedmiotowej operacji....

Średnio mi się widzi te 180 milionów w parę sekund...

Jeśli możesz, udostępnij listę adresów na potrzeby testów.

[Darek_C++]

Przy kompilacji ustawiłem na Release_Build i tak zbudowałem EXE w katalogu Release_Build. NIc więcej nie zmieniałem.

Przykładowa duża listy do testów: Pobieranie: Nearly-1-Million-list-WarezBul.Com.txt | 59.9 MB
http://hotfile.com/dl/77582400/6b8add6/Nearly-1-Million-list-WarezBul.Com.txt.html
OK 800K linii adresów.

[Cyfrowy Baron]

Wypróbuj TStringList z właściwością Duplicates ustawioną na dupIgnore. Działa tylko z posortowaną listą, więc właściwość Sorted trzeba ustawić na true. Nie testowałem tej listy, więc nie wiem czy jest szybsza od std::set.

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

 TStringList *Lista = new TStringList();

 Lista->Sorted = true;
 Lista->Duplicates = dupIgnore;
 
 Lista->LoadFromFile("nazwa_pliku");

 ListBox1->Items->AddStrings(Lista); // ewentualne przepisanie do ListBox

 delete Lista;

[Darek_C++]

Ten sposób jest znacznie wolniejszy:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

void __fastcall TForm3::Button4Click(TObject *Sender)
{
        if(OpenTextFileDialog1->Execute())
        {
                float Start = GetTickCount();
                Button4->Enabled = false;
                String nzpliku = OpenTextFileDialog1->FileName;
                String out = ExtractFileDir(Application->ExeName) + "\\Test_out4.txt";

                 TStringList *Lista = new TStringList();

                 Lista->Sorted = true;
                 Lista->Duplicates = dupIgnore;

                 Lista->LoadFromFile(nzpliku);
                 Lista->SaveToFile(out);
                 delete Lista;

                Button4->Enabled = true;
                float End = GetTickCount();
                Edit1->Text = FloatToStr((End - Start) / 1000) + " s.";

        }
}

Wykonano dla tej samej listy co poprzednio w 40,436 s.

[Cyfrowy Baron]

http://hotfile.com/dl/77582400/6b8add6/Nearly-1-Million-list-WarezBul.Com.txt.html

Nie rozumiem dlaczego nie skompresowałeś tej listy do RAR lub ZIP. Pliki tekstowe po kompresji zmniejszając się kilkadziesiąt razy. Czy mógłbyś tą listę skompresować i wrzucić do załącznika na forum - patrz dół forum [Dodaj załącznik], bo nie chce mi się ściągać tak dużego pliku skoro mogę mniejszy.