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

[Darek_C++]

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.

[polymorphism]

Później może wrzucę jakiś kod. Może, bo jakieś cuda się dzieją 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!

[polymorphism]

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  �

KOD cpp:   �  POKAŻ  �

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.

[Cyfrowy Baron]

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

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...

[Darek_C++]

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.

[Darek_C++]

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.

[polymorphism]

Kod który wcześniej podałem też nie daje rady?

[Darek_C++]

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ć

[Darek_C++]

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 .

[polymorphism]

No to git. Pewnie możnaby nieco przyspieszyć kod używając mapowania pliku zamiast strumienia, ale tu już pobaw się sam z tym.