Do jakich zastosowań nadają się drzewa czerwono-czarne?
Najogólniej pisząc, drzewa czerwono-czarne są dynamiczną strukturą umożliwiającą szybkie wyszukiwanie i modyfikowanie danych. Część dalsza wkrótce.
benchmark 00 tablicowej implementacji drzew czerwono czarnych
Kilka postów wcześniej zobowiązałem się przedstawić bencznarki i pomiary czasu implementacji tablicowej drzew czerwono - czarnych . Pokażę zatem, czy implementacja tablicowa naprawdę działa szybciej, o ile szybciej i w jakich sytuacjach możemy uzyskać przyspieszenie względem szablonów takich jak std::set i QMap. Benczmark 00 dotyczy wersji beta 0.00v. Na potrzeby tego bencznarku napisałem specjalny program i specjalny skrypt powłoki bash. Skrypt kompiluje, optymalizuje i profiluje kod bibliotek, kod drzewa czerwono czarnego i kod samego bencznmarku. Do kompilacji i profilowania został wykorzystany kompilator g++, więcej szczegółów kompilacji można wyczytać w pliku bench00.sh. Do pobrania: kod źródłowy bencznarku (pobierz i zapisz jako bench00.cpp) Do pobrania: skrypt ułatwiający uruchomienie testu (pobierz i zapisz jako bench00.sh) Wszystkie testy w benchmarku 00 są przeprowadzane na 32bitowym typie bez znaku unsigned int. Zapewne pomiary czasu na większym typie, np. n
Komentarze
Prześlij komentarz