GetCSV optymalizacja interface'u

Obiecałem kontynuowanie wątku o CSV, a dokładniej wykorzystać prostą funkcję do pokazania jednego ze sposobów optymalizacji od strony interface'u, jak i od strony algorytmów. Kazałem na kolejny odcinek troszkę poczekać, ale z czasem tak jest, że nie jest on z gumy i zdarza się, iż trzeba odłożyć pewne działania na później. Ponieważ nie chciałem odkładać tego w nieskończoność, to właśnie czytają Państwo kolejny odcinek z naszego cyklu.

Zacznijmy od zdefiniowania tego, co chcemy zrobić:

• chcemy zoptymalizować algorytm
• chcemy by mógł być on porównywalny
• chcielibyśmy uniezależnić funkcję od źródła z którego pobieramy dane.

Tak więc zacznijmy od ostatniego punktu, dzięki czemu uzyskamy realizację punktu drugiego. Punkt pierwszy w tym odcinku będzie jedynie zaznaczony.

Po przyjrzeniu się jak działa nasza funkcja z poprzedniego odcinka, możemy zauważyć, że dane przekazywane są w postaci wskaźnika na pamięć z ciągiem znaków do analizy. Następnie przeszukujemy dane poruszając się po nich za pomocą kolejnych iteracji wskaźnika. Czy to czegoś nie przypomina? Otóż, wskaźnik w tym wypadku pełni rolę iteratora. Tak więc po bliższym przyjrzeniu się problemowi, widzimy, iż zamiast przekazywać wskaźnik, przekażmy po prostu iterator ustawiony na pierwszy element zbioru.

Chcemy optymalizacji czasowej kosztem objętości, dlatego proponuję użycie template'ów. Stąd deklaracja funkcji naszej wygladać będzie następująco:

template <class xstream>
tlistarr GetCSV(TStreamIterator<xstream> &iter, char arecsep);

Definicja iteratora znajduje się natomiast w pliku kacstream.h Zdefiniowane tam zostały podstawowe operacje, takie jak:

• inkrementacja
• przypisanie
• sprawdzenie iteratora
• wyłuskanie danej

Parametrem szablonu klasy jest class xstream, która musi mieć zdefiniowane dwie metody:

 const char *First();
 const char *Next();

Jednym z przykładów klasy, używanej przez xstream jest klasa opakowująca zwykłą tablicę z tekstem. Ktoś by mógł powiedzieć, że jedynie napisaliśmy trochę kodu by uzyskać coś przypominającego wskaźnik, który jest typem wbudowanym w kompilator. Otóż nic bardziej mylnego. Zdefiniowaliśmy interface, który możemy wykorzystać do dowolnego typu, ba - możemy później go optymalizować. Dlatego stworzyłem również drugą klasę - opakowującą obsługę pliku (w pliku kacfilestream.h). W obu przypadkach jedyna optymalizacja jaką zastosowałem to taka, że wszystkie metody zdefiniowane są wewnątrz definicji Pozwoli to kompilatorowi na wstawienie tych operacji bezpośrednio w kod. Inne optymalizacje na tym etapie pomijam, bo na początku ma to po prostu zadziałać!

Tak więc część główna programu wygląda następująco:

int main()
{
#ifdef MYMEMSTREAM
    TKacConstMemStream strm(testarr);
    TStreamIterator<TKacConstMemStream> itr(strm);
#else
    TKacFileStream strm("test.csv");
    TStreamIterator<TKacFileStream> itr(strm);
#endif
    tlistarr x;
    double dt;
    time_t t1;
    t1 = time(NULL);
    x = GetCSV(itr, ';');

    dt = difftime(time(NULL), t1);
    std::cout<<"Operację wykonano w "<<dt<<" sek.\n";
    return 0;
}

W zależności, czy chcemy przetestować dane czytane z pamięci, czy z pliku, kompilujemy z odpowiednią definicją. Jak widzimy stworzenie iteratora to:

TStreamIterator<WYBRANYTYP> itr(OBIEKT);

Sama funkcja GetCSV natomiast poza deklaracją zmieniła się minimalnie - w zasadzie zamieniliśmy wskaźnik lact na iterator iter. Cała reszta w przykładzie jest bez zmian. To po to, by móc później porównać optymalizacje.

Z rozpędu pomyślałem, że może pokazać jak w prosty sposób można przyśpieszyć tę funkcję niewielkim nakładem pracy. Przykład taki znajdą Państwo w pliku getcsv_kacz1.cpp. Po szybkiej analizie algorytmu, łatwo dojść do przekonania, że jedną z małooptymalnych operacji na pewno będzie dodawanie znaku do bufora:

lsbuf += ZNAK;

Jak to zmienić? Najprostsze rozwiązanie - użyć bardziej optymalnego kontenera niż std::string. Skorzystałem tu z std::stringstream. Potrzebne są niewielkie zmiany. Na przykład linia dodawania znaku przyjmie postać:

lsbuf << ZNAK;

Nie jest to najbardziej optymalne rozwiązanie, ale daje (tam gdzie testowałem) ok 20% przyśpieszenie kodu.

Na tym kończę dziś odcinek. Oczywiście kod testowy jest do popbrania TU, natomiast jeśli ktoś ma jakieś uwagi lub pytania, proszę skorzystać z formularza kontaktowego.

Pozdrawiam
Tomasz Kaczanowski

2014-06-17 19:44:11