[BCB C++] Liczenie lini \r\n danych z dużych pliku

[Darek_C++]

Witam ponownie,
tym razem chciał bym się dowiedzieć jaki będzie optymalny sposób na szybkie policzenie ile plik ma linii danych \r\n

[Cyfrowy Baron]

A to już chyba wymaga przetworzenia pliku, więc najprościej jest go wczytać do klasy THashedStringList i sprawdzić wartość Count. THashedStringList działa tak samo jak TStringList, ale jest szybszy.

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

#include "inifiles.hpp"
THashedStringList *hList = new THashedStringList;
 hList->LoadFromFile("c:\\test.txt");
 ShowMessage(hList->Count);

U mnie lista zwróciła liczbę linii dla pliku tekstowego o rozmiarze 60 MB = 496672 linii w mniej niż 1 sekundę, ale TStringList też był równie szybki i z pomiaru czasu wykonywani zadania wynika, że zrealizował je dokładnie w tym samym czasie średnio 220 milisekund. W pliku pomocy jest napisane, że dla dużych plików THashedStringList może być szybszy.

[polymorphism]

Nie no, z tym THashedStringList do liczenia linii to lekka przesada. Użyj strumienia ifstream i metody ignore.

[Darek_C++]

Z tego co wyczytałem:
istream& ignore( int ile=1, int do=EOF );
- ignoruje `ile' znaków ze strumienia lub aż do `do'.
Wiec nie wiem jak tą metodę mogę wykorzystać do policzenia linii pliku

[polymorphism]

Ustaw 'ile' na INT_MAX, 'do' na \n, wtedy ignore będzie "skakać" po liniach. Wykombinuj jakąś pętlę i zadanie rozwiązane.

[Cyfrowy Baron]

TStringList i THashedStringList są dużo szybsze od ignore, dlatego zaproponowałem takie rozwiązanie. Oto kody, które testowałem na pliku kodowanym w Unicode:

THashedStringList, czas wykonywania zadania dla pliku 60 MB - 496672 linii, średnio 220 milisekund:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

 clock_t start, end;
 start = clock();
 char Buf[255];

 TStringList *hList = new TStringList;
 hList->LoadFromFile("c:\\test.txt");

 Edit2->Text = hList->Count; // liczba linii

 delete hList;

 end = clock();
 sprintf(Buf, "%f", (end - start) / CLK_TCK);
 Edit1->Text = (String)Buf; // czas wykonywania zadania

ifstream ignore, czas wykonywania zadania dla pliku 60 MB - 496672 linii, średnio 1.34 sekund:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

 clock_t start, end;
 start = clock();
 char Buf[255];

 ifstream infile("c:\\test.txt", ios::in);

 int ile = -1;

 while(infile.ignore( INT_MAX, '\n' ))
 {
  ile += 1;
 }

 Edit2->Text = ile; // liczba linii

 end = clock();
 sprintf(Buf, "%f", (end - start) / CLK_TCK);
 Edit1->Text = (String)Buf;// czas wykonywania zadania

Dla tego samego pliku przy kodowaniu ANSI, co zmniejszyło rozmiar pliku do 30 MB, ale liczba linii się nie zmieniła, czas dla THashedStringList = 220 milisekund, dla ifstream ignore = 703 milisekund, czyli ifstream lepiej sobie radzi z plikami kodowanymi w ANSI, ale i tak jest wolniejsze od THashedStringList. Jak widać zmniejszenie rozmiaru pliku - nie liczby linii - nie wpłynęło na szybkość działania THashedStringList.

Gdy podwoiłem liczbę linii do 993345, co spowodowało zwiększenie rozmiaru pliku kodowanego w ANSI do 60 MB, czas wykonywania zadania w obydwu przypadkach się podwoił: THashedStringList = 450 milisekund, ifstream = 1.43 sekund.

[polymorphism]

Mierzyłeś wersje release? U mnie ignore ~194483 linie robi w ~400ms, plik ma 52MB. Coś dziwne wydaje mi się, żeby analiza pliku i konstruowanie listy (alokacje pamięci) THashedStringList było parokrotnie szybsze od czytania do i z bufora strumienia.

[Cyfrowy Baron]

Sprawdzałem na Debug, ale na Release THashedStringList i tak jest szybszy, co ciekawe czas na Release dla THashedStringList nie zmienił się, podczas gdy dla ifstream skrócił się do 922 ms (60 MB - 496672 linii).
W przypadku ifstream jest pętla, która prawdopodobnie powoduje opóźnienia. THashedStringList analizuje plik podczas wczytywania, a więc już wtedy zbiera informacje i przechowuje w zmiennej Count o liczbie linii jaka sądzę, gdyż bez zwracania liczby linii a tylko z samym wczytaniem pliku, czas się nie zmienia. Podczas gdy wczytanie pliku przez ifstream jest niezauważalne, czyli plik nie jest analizowany, więc opóźnienie powstaje na algorytmie odczytującym liczbę linii. Gdyby zastosować do ifstream inną metodę zliczania, wtedy mogłoby to być znacznie szybsze.

U mnie ignore ~194483 linie robi w ~400ms, plik ma 52MB.

Jak widać znaczenie nie ma rozmiar pliku lecz liczba linii. Po zmniejszeniu linii tekstu do 194483 ifstream zwraca liczbę linii dla pliku kodowanego w ANSI w 203ms, a THashedStringList w 94ms. Dla pliku kodowanego w Unicode: ifstream = 375 ms, a THashedStringList = 110 ms.

[polymorphism]

(...) co ciekawe czas na Release dla THashedStringList nie zmienił się, podczas gdy dla ifstream skrócił się do 922 ms (60 MB - 496672 linii).

Sprawa prosta. Biblioteki VCL dołączasz już skompilowane, w LIB-ach. ifstream, jak i inne składniki STL-a, jest kompilowany razem z programem, dlatego różnice między debug a release są dość duże.

W przypadku ifstream jest pętla, która prawdopodobnie powoduje opóźnienia. THashedStringList analizuje plik podczas wczytywania, a więc już wtedy zbiera informacje i przechowuje w zmiennej Count o liczbie linii

Błędny wniosek, ponieważ pętla z ifstream robi to samo, czyli czyta plik i zlicza liczbę znaków \n. Według mnie spowolnienie spowodowane jest ilością wywołań różnych funkcji na bajt pliku.

Tu zredukowałem liczbę wywołań i od razu lepiej, prawie dwa razy szybsze _{(testowałem na laptopie, który ma raczej wolny dysk)}:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

ifstream ifs("plik", ios::binary);

size_t n = 0;
char data[4096];
size_t c;

while((c = ifs.read(data, sizeof(data)).gcount()) > 0)
{
        for(size_t i = 0; i < c; ++i)
                if(data[i] == '\n') ++n;
}

cout << n << '\n';

Jak widać znaczenie nie ma rozmiar pliku lecz liczba linii.

Mylisz się. Rozmiar pliku ma znaczenie, ponieważ każdy bajt pliku musi zostać odczytany w celu znalezienia znaku końca linii. Oczywiście w przypadku THashedStringList ilość linii będzie miała jakieś odzwierciedlenie w czasie ładowania, bo na każdą linie przypada stworzenie elementu listy i wstawienie go w odpowiednie miejsce.

[Darek_C++]

Sam też dokonał porównania czasu liczenia dla wielkość pliku 7,42 MB lini 102522 kompilacja Release_Build:

Ostatnia metoda polymorphism:
102520 Czas: 1.578000
102520 Czas: 1.562000
102520 Czas: 1.547000
102520 Czas: 1.547000
-----
Pokazuje o dwie linie mniej niż faktycznie jest w tym pliku

=============================
Metoda CB z TStringList:
102522 Czas: 0.093000
102522 Czas: 0.062000
102522 Czas: 0.063000
102522 Czas: 0.079000
------
Metoda CB z THashedStringList:
102522 Czas: 0.079000
102522 Czas: 0.062000
102522 Czas: 0.062000
102522 Czas: 0.078000

Drugi plik 37,1 MB
Ostatnia metoda polymorphism:
512600 Czas: 7.625000
512600 Czas: 8.500000
512600 Czas: 9.031000

Metoda CB z THashedStringList:
512610 Czas: 0.406000
512610 Czas: 0.375000
512610 Czas: 0.359000

Rożnica jest ogromna i metoda polymorphism błędnie w jakimś miejscu zlicza faktyczną liczbę linii
Dla innego pliku jest jeszcze większy błąd zliczania linii
102466 Czas: 1.453000
102522 Czas: 0.078000 < tyle też pokazuje EditPlus po wczytaniu tego pliku

[polymorphism]

Sam też dokonał porównania czasu liczenia dla wielkość pliku 7,42 MB lini 102522 kompilacja Release_Build:

Ostatnia metoda polymorphism:
102520 Czas: 1.578000
...

To w sekundach jest?! Jeśli tak, to na czym Ty to testowałeś, jeśli u mnie na dość wolnym laptopie 52MB plik przerabiał w ~200ms _{(na stacjonarnym poniżej 100ms)}?!

metoda polymorphism błędnie w jakimś miejscu zlicza faktyczną liczbę linii

Poprawiłem błąd. Warunek był zły - założyłem, jak się okazało błędnie, że przy czytaniu ze strumienia, który ma już ustawioną flagę eof, zostanie ustawiona flaga fail, co doprowadza do zakończenia pętli. A tu d.upa, read po napotkaniu końca pliku od razu ustawia eof i fail, przez co ostatni niepełny bufor był pomijany.

[Darek_C++]

Tak w sekundach i takie różnice są dla wszystkich testowanych plików ;
Na Pentium 4 2.8 GHz z 2G RAM OS: Windows XP Pro SP3;
U mnie liczone jest tak jak napisałem źle przy czym liczba linii z metody z THashedStringList i TStringList dla tego samego pliku testowego są zgodne z tym co pokazuje EditPlus;

W poprawionym kodzie brakuje czegoś:

[C++ Error] UnitTestowy.cpp(296): E2451 Undefined symbol 'data'

[polymorphism]

Tak w sekundach i takie różnice są dla wszystkich testowanych plików ;
Na Pentium 4 2.8 GHz z 2G RAM OS: Windows XP Pro SP3;

No to nie ma innej opcji, robisz coś źle. Wynik jest totalnie niewiarygodny, nawet w zestawieniu z tym, co ja i Baron podaliśmy:

• Ja_(pc) --> 0,095 (52MB) 547,36 MB/s
• Ja_(laptop) --> 0,2 (52MB) 260 MB/s
• Baron --> 0,922 (60MB) 60,48 MB/s (wersja z ignore)
• Ty --> 1,578 (7,42MB) 4,7021 MB/s !!!

Zatem jeśli masz tak kiepską przepustowość, to jakim cudem ze TStringList osiągasz poniżej 93ms?!

---

Co do liczby linii, poprawiłem kod i zmieniłem wcześniejszy post.

[Darek_C++]

Takim kodem:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

void __fastcall TForm4::Button5Click(TObject *Sender)
{
        if(OpenTextFileDialog1->Execute())
        {
                 clock_t start, end;
                 start = clock();
                 char Buf[255];

                String plik = OpenTextFileDialog1->FileName;

                ifstream ifs(plik.c_str(), ios::binary);

                size_t n = 0;
                char data[4096];
                size_t c;

                while((c = ifs.read(data, sizeof(data)).gcount()) > 0)
                {
                                for(size_t i = 0; i < c; ++i)
                                                if(data[i] == '\n') ++n;
                }
                end = clock();
                sprintf(Buf, "%f", (end - start) / CLK_TCK);
                Memo1->Lines->Add((String) n +" Czas: "+ (String)Buf);

        }
}
//---------------------------------------------------------------------------

void __fastcall TForm4::Button6Click(TObject *Sender)
{
        if(OpenTextFileDialog1->Execute())
        {

                 clock_t start, end;
                 start = clock();
                 char Buf[255];

                String plik = OpenTextFileDialog1->FileName;
                TStringList *hList = new TStringList;
                //THashedStringList *hList = new THashedStringList;
                hList->LoadFromFile(plik);

                int n = hList->Count; // liczba linii

                end = clock();
                sprintf(Buf, "%f", (end - start) / CLK_TCK);

                delete hList;

                Memo3->Lines->Add((String) n +" Czas: "+ (String)Buf);

        }
}

Takie mam wyniki z tego kodu powyżej:
512609 Czas: 7.875000
512609 Czas: 7.781000
512609 Czas: 7.781000

CB
512610 Czas: 0.344000
512610 Czas: 0.328000
512610 Czas: 0.344000

[polymorphism]

Kod jak kod, tu raczej o ustawienia kompilatora chodzi. Niby masz release, ale wyniki jak debug.

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

cout << n << '\n';

To jest zbędne, bo i tak nic nie wyświetli.

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

...
end = clock();
...

delete hList;

Jak liczysz czas tworzenia listy, to licz też czas jej usunięcia.