CYFROWY BARON • PROGRAMOWANIE • Zobacz wątek - Usuwanie duplikatów z dużych list adresów > 100K

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

dział ogólny

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

Nowy postprzez Darek_C++ » piątek, 4 lutego 2011, 17:13

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 :)
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » piątek, 4 lutego 2011, 18:54

Zamiast mapy, użyj std::set.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » piątek, 4 lutego 2011, 21:00

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/ ?
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » piątek, 4 lutego 2011, 21:32

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).
C++ Reference - opis wszystkich klas STL-a i funkcji C.

Za ten post autor polymorphism otrzymał podziękowanie od:
Darek_C++
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » piątek, 4 lutego 2011, 21:51

polymorphism napisał(a):(set jest kontenerem uporządkowanym, przechowującym unikalne wartości).
No to o to chodziło 8-)
---------
Działa w wypadku liczb, ale jak chce władować "stringi" :

KOD cpp:     UKRYJ  
        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
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » piątek, 4 lutego 2011, 22:59

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 ?
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » piątek, 4 lutego 2011, 23:22

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


Kwestia ustawień forum. Już to zmieniłem.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » piątek, 4 lutego 2011, 23:32

Mam taki kod:
KOD cpp:     UKRYJ  
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 ?
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » sobota, 5 lutego 2011, 11:44

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! :shock: 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.?
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » sobota, 5 lutego 2011, 12:31

polymorphism napisał(a):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.

polymorphism napisał(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.?

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."
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » sobota, 5 lutego 2011, 13:39

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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » sobota, 5 lutego 2011, 13:57

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.
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » sobota, 5 lutego 2011, 16:15

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  
 TStringList *Lista = new TStringList();

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

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

 delete Lista;
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Darek_C++ » sobota, 5 lutego 2011, 17:01

Ten sposób jest znacznie wolniejszy:
KOD cpp:     UKRYJ  
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.
Avatar użytkownika
Darek_C++
Elektrowied
Elektrowied
 
Posty: 454
Dołączył(a): piątek, 25 lipca 2008, 14:33
Podziękował : 66
Otrzymał podziękowań: 4
System operacyjny: Windows XP Pro SP2
Kompilator: Turbo Explorer C++
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » sobota, 5 lutego 2011, 17:12

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.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

Następna strona

  • Podobne tematy
    Odpowiedzi
    Wyświetlone
    Ostatni post

Powrót do Ogólne problemy z programowaniem

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zalogowanych użytkowników i 17 gości

cron