Posty

Wyświetlanie postów z sierpień, 2017

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

metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy

Kod nieprzetestowany albo nie działa w ogóle, albo nie działa poprawnie - i tak było w przypadku tej implementacji drzew czerwono - czarnych . Dlatego napisałem specjalny kod do przetestowania. Metodyka jaką przyjąłem polega na testowaniu porównawczym. Trzy takie same programy, oparte jednak na innych implementacjach drzew czerwono - czarnych , muszą dać takie same wyniki. W celu przetestowania zaprojektowałem 15 procedur. Każda procedura, w przybliżeniu, testuje kolejną metodę z tej implementacji, a także analogiczne metody z implementacji w std::set i QMap. Kolejność wywoływania procedur jest losowa, a także losowa jest kolejność wybierania implementacji, co powinno wykluczyć błędy ujawniające się tylko przy określonej kolejności, np. po wywołaniu metody sort, która kompletnie reorganizuje ułożenie węzłów w pamięci. Oczywiście niektóra kolejność wywoływania procedur jest błędna z założenia, np. po wywołaniu metod: insert, remove, nie można wywoływać metod z przed

kod źródłowy C++ drzewa czerwono czarnego wrsja beta 0.00v

Zamieszczam do pobrania kod źródłowy implementacji na tablicy drzewa czerwono czarnego w postaci szablonu C++. Kod został sformatowany przy pomocy hilite . Implementacja jest dostępna pod poniższym linkiem: Kod źródłowy drzewa czerwono - czarnego wersja beta 0.00v Pobierz powyższy kod i zapisz najlepiej jako plik nagłówkowy rb_tree.h Jeśli znajdziesz jakieś błędy w kodzie, albo będziesz miał pomysły na udoskonalenie lub przyspieszenie, zapraszam do podzielenia się wszystkim w komentarzach. Mam nadzieję jednak, że Twoja aplikacja dzięki tej implementacji będzie działa bezbłędnie i nieco szybciej. Wkrótce zamieszczę instrukcje z przykładami jak można używać tej biblioteki.

Zalety i wady implementacji drzew czerwono czarnych na tablicy

Opisywana implemetnacja drzew czerwono - czarnych na tej stronie została zrealizowana w oparciu o ciągły obszar pamięci , innymi słowy, w oparciu o tablicę elementów . Taki obszar pamięci można zapewnić przy pomocy odpowiedniego allocatora. Przykładowymi allocatorami mogą być: struktura QVector z biblioteki QT, std::vector z biblioteki standardowych szablonów w C++, a nawet std::array i QVarLengthArray. Można też samodzielnie obudować zwykłą tablicę klasą C++ i przekazać tę klasę jako parametr szablonu RBTree. Dla wygody zostały przygotowane trzy gotowe allocatory. Zatem już na pierwszy rzut oka widać, że ta implementacja drzew czerwono czarnych nie jest standardowa, ponieważ zwykle spotykamy się w praktyce i w literaturze z implementacją na wskaźnikach. Z implemetnacją na ciągłym obszarze pamięci wiąże się szereg zalet i wad. Zalety implementacji na tablicy W pobieżnych testach implementacja na tablicy działa szybciej. Rzadziej jest wywoływana funkcja malloc, jest mniejszy na

Licencja i warunki używania wszelkiego oprogramowania na tej stronie.

To jest kod open-source, jest jednak rozprowadzany na innej licencji niż typowe licencje open-source. Jeśli poniższa licencja Tobie nie odopowiada, to skasuj ten kod ze swojego komputera. Możesz ten kod pobrać z mojej strony internetowej, możesz go czytać możesz go używać nieodpłatnie w swoich programach, możesz go zmieniać, jednak pod kilkoma warunkami i w określonych poniżej ramach. Zanim zaczniesz cokolwiek robić z wykorzystaniem tego kodu zapoznaj się z opisem. Niektóre cechy tego kodu, można łatwo uznać za błędy. Możesz ten kod pobrać z mojej strony internetowej, nie możesz rozprowadzać tego kodu ani w oryginalne, ani po zmianach, ani w całości, ani we fragmentach, ani obcym, ani znajomym.  Jeśli rozprowadzasz wesję skompilowaną tego kodu, nie musisz udostępniać źródła, ani mnie informować, ani nic płacic. Jeśli jednak mnie poinformujesz, to zrobię Ci małą reklamę, napiszę że Twój program korzysta z tego kodu, opublikuję Twój e-mail i link do strony Twojego programu.  Jeśli

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.                  

Wyzwanie - wydajny uporządkowany zbiór w C++

      Dużo jest dostępnych bibliotek C++ implementujących uporządkowany zbiór z możliwością modyfikowania i wyszukiwania (i nie tylko) w czasie Log(N), gdzie N jest ilością danych przechowywanych w zbiorze. Szablony  takie jak std::set, std::map, QMap z biblioteki standardowej i biblioteki QT, oferują taką możliwość.  Szablony te oferują taką możliwość dzięki temu, że zostały zaimplementowane w oparciu o strukturę danych nazywaną drzewami czerwono -czarnymi (ang red -black trees ). Strukturami o podobnych możliwościach są drzewa AWL, B-Drzewa, 2-3-4 drzewa, a także po prostu wszelkie drzewa wyszukiwań (nie koniecznie wyszukiwań binarnych) z dowolnym mechanizmem równoważenia.       Drzewa bez  mechanizmu równoważenia nie zawsze gwarantują szybkie wyszukiwe, modyfikowanie (i kilka innych operacji) w czasie logarytmicznym Log(N). Gdy dane do drzewa nie są wstawiane w kolejności losowej, to drzewa bez mechanizmu balansowania mogą mieć bardzo duże głębokości lub mogą wręcz zdegenerować