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

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

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

Cyfrowy Baron napisał(a):Nie rozumiem dlaczego nie skompresowałeś tej listy do RAR lub ZIP..

Nie mogłem, bo ja jej nie zamieściłem, jak tylko podaje jej adres na prośbę polymorphism'a.
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, 18:37

Później może wrzucę jakiś kod. Może, bo jakieś cuda się dzieją :twisted: Wcześniej testowałem algorytm na pliku z 1700000 liniami. Całość wyrabiała się w 8 sekundach. Z kolei plik z adresami, który podał Darek_C++, mieli ponad 3 minuty!
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 polymorphism » niedziela, 6 lutego 2011, 11:31

Ok, coś takiego wydumałem. Nie wiem, czy to działa dobrze, to znaczy, czy nie pojawią się dwa takie same hasze dla dwóch różnych url-i (w CRC32 pojawiały się takie konflikty). Póki co wszystko wskazuje, że działa jak należy.
KOD cpp:     UKRYJ  
class md5hash
{
public:
        char hash[16];

        bool operator<(const md5hash &v)const
        {
                return memcmp(hash, v.hash, 16) < 0;
        }
};

...

ifstream        is("Nearly-1-Million-list-WarezBul.Com.txt",ios::binary);
ofstream        os("output");

set<md5hash> hash_set;
char            line[100000];
MD5             md5;

while(1)
{
        char* p1 = line;
        char* p2 = p1;
        char* p3 = p1 + sizeof(line);

        /* robi to samo co operator>>, tylko bez std::stringa, dodatkowo trim'uje linię */
        while((*p2 = is.rdbuf()->sgetc()) != EOF && strchr(" \t\r\n",*p2))
                is.rdbuf()->sbumpc();

        char* p4 = NULL;
        while((*p2 = is.rdbuf()->sbumpc()) != EOF )
        {
                if(*p2 == '\n')break;
                if(strchr(" \t\r",*p2))
                {
                        if(!p4) p4 = p2;
                }
                else p4 = NULL;
                ++p2;
                if(p2 >= p3)throw "url is too long!";
        }

        if(p4)p2 = p4;
        if(*p2 == EOF && p1 == p2)break;

        if(p2 - p1 > 7 && strncmp("http://",p1,7) == 0)
        {
                md5hash h;

                md5.init();
                md5.update(p1,p2 - p1);
                md5.finalize().get_digest(h.hash);

                if(hash_set.insert(h).second)
                {
                        *p2 = 0;
                        os << p1 << '\n';
                }
        }
}

if(is.good())
{
        cout << "ok, done\n";
}

U mnie wersja release przerabia 846429 url-i w ~3.4 sekundy.
Nie masz wystarczających uprawnień, aby zobaczyć pliki załączone do tego postu.
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 Cyfrowy Baron » niedziela, 6 lutego 2011, 11:48

KOD cpp:     UKRYJ  
MD5             md5;


MD5 - z jakiej biblioteki pochodzi ten typ. gdyż w pomocy nic na ten temat nie mam?



Już widzę, dołączyłeś bibliotekę w załączniku...
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++ » niedziela, 6 lutego 2011, 14:35

Dzięki polymorphism , Twój kod - sposób jest najszybszy. Na moim kompie dla porównania dla pliku wejściowego 214548 linii trwa to:
Zapisano linii: 214542
W czasie: 8,531 s.

8-)
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++ » środa, 11 czerwca 2014, 07:32

Witam ponownie,
temat usuwania duplikatów znowu mam aktualny, czyli nadal chodzi o usunięcie duplikatów liniia danych z dużych plików.

Wczytując do kontenera set<linia_danych> lub map< skrót MD5, linia_danych> jest OK, ale przy "dużych" plikach > 5M linii program już nie daje rady. Znalazłem coś takiego: http://en.wikipedia.org/wiki/External_sorting "For example, for sorting 900 megabytes of data using only 100 megabytes of RAM".

Pytanie, czy tym sposobem mogę usunąć duplikaty, jeśli tak jak to w praktyce mniej więcej zrobić, bo nie do końca rozumiem mechanizm z tego opisu.
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 » środa, 11 czerwca 2014, 09:11

Kod który wcześniej podałem też nie daje rady?
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++ » środa, 11 czerwca 2014, 09:27

Ten z MD5 - TAK ? Przyznam, że mi umknął, więc sprawdzę, ale jak jest oparty na ładowaniu danych do jakiegoś kontenera, to pewnie też przy przekroczeniu pewnej ilości danych przestanie działać.

Jest taki program napisany w delphi: http://www.scrapebox.com/free-dupe-remove "Also it can remove duplicate URL’s and duplicate domains from files as large as 180 Million lines long in just a few seconds.", wiec jakiś sposób na to musi być ;)
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++ » niedziela, 22 czerwca 2014, 19:22

polymorphism napisał(a):Kod który wcześniej podałem też nie daje rady?
Teraz testowałem, że tak powiem "kod rewelacja" daje radę nawet z plikiem zawierającym 21.000.000 lini w pliku wielkości ~ 2,2 GB : Unikalne: 17000000 Czas: 149.324000 sekund. I jestem pewien, że linie były unikalne, bo sam generowałem plik z liniami testowymi po 1.000.000 zmieniając ciąg znaków jaki był zapisany jako linia .
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 » poniedziałek, 23 czerwca 2014, 09:09

No to git. Pewnie możnaby nieco przyspieszyć kod używając mapowania pliku zamiast strumienia, ale tu już pobaw się sam z tym.
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
    LinuxChrome

Poprzednia 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 15 gości

cron