Jak zaprojektować w stl B-drzewo (może być B+), w którym każda stronica będzie drzewem binarnym, ewentualnie hash-table (w celach optymalizacyjnych)?
0
0
Dobrze rozumiem, chcesz mieć b-drzewo drzew binarnych?
0
nalik napisał(a):
Dobrze rozumiem, chcesz mieć b-drzewo drzew binarnych?
Chyba co koło tego: B-drzewo setów, czyli faktycznie set setów.
Ewentualnie może być B-drzewo zrobione z list/tablic z stl: każda stronica z B-drzewa to lista/tablica stl.
0
Po co? Nie bardzo widzę use case i zysk.
0
nalik napisał(a):
Po co? Nie bardzo widzę use case i zysk.
Jest wielka baza posortowana w czasie, np. milion rekordów, z kluczami: t1 < t2 < t3 ...
I teraz ta cała baza ewoluuje w czasie, w taki sposób że ilość pozycji jest zachowana w zasadzie,
zatem całość jakby jedzie z prawa do lewa, ale losowo;
np. element 1 skacze na pozycję 50, a 50 na 40, 40 na 20, itd.
Cała akcja dzieje się jakby w miejscu - w jednym drzewie;
jest pełno modyfikacji tego drzewa - non stop z upływem czasu, ale przyrost jest zerowy (per saldo).
Zatem należy to zoptymalizować po kątem szybkości permanentnych operacji: usuwanie + wstawienie.
Zwyczajne drzewo binarne jest zbyt wolne do tego.
1
Sprawdziłeś, że drzewo binarne jest zbyt wolne czy to teoretyczne gdybanie? Próbowałeś użyć zwyklej, gotowej implementacji bdrzewa np. od Googla, czy wolisz wymyślać koło od nowa?
0
nalik napisał(a):
Sprawdziłeś, że drzewo binarne jest zbyt wolne czy to teoretyczne gdybanie? Próbowałeś użyć zwyklej, gotowej implementacji bdrzewa np. od Googla, czy wolisz wymyślać koło od nowa?
Wiadomo że będzie wolne - sprawdź sobie liczbę operacji na takie ciągłe/wielokrotne usuwanie i wstawianie ponownie.
W B-drzewach jest to szybsze, bo tam po usunięciu/dodaniu elementu zwykle nie potrzeba w ogóle nic robić;
wyważania są tam sporadyczne, a w przypadku takiej niemal zupełnie 'statycznej wersji' = bez zmian rozmiarów drzewa, pewnie w ogóle to nie wystąpi.
0
Kolego Wil, to Ty sobie sprawdź cokolwiek, bo to ty zadajesz pytanie, nie ja.
Masz open sourcowa implementację btree od Googla, użyj, sprawdź, zmierz, podziel się wynikami i nie toretyzuj tylko zrób coś pożytecznego.
0
Jeśli chodzi o performance, to trzeba zdefiniować jakie są wymagania, bez tego zawsze można twierdzić, że jest za wolno.
Szablony STL dają duże możliwości, tylko nie wiem czy potrafią zaspokoić wyrafinowane wymagania co do elastyczności i wydajności ;-)
Możesz trzymać sobie zakresy kluczy i dla każdego zakresu mapę, możesz mieć też indeks, który pozwoli Ci przejść od wartości do zakresu i coś tam zrobić.
std::map< std::pair<int,int>, std::map<int,int>> rangedMap;
std::map< int, std::pair<int,int> > indexToRange;
Szablon:
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;
0
nalik napisał(a):
Kolego Wil, to Ty sobie sprawdź cokolwiek, bo to ty zadajesz pytanie, nie ja.
Masz open sourcowa implementację btree od Googla, użyj, sprawdź, zmierz, podziel się wynikami i nie toretyzuj tylko zrób coś pożytecznego.
Pytanie dotyczy realizacji b-drzewa za pomocą stl.
0
yarel napisał(a):
Jeśli chodzi o performance, to trzeba zdefiniować jakie są wymagania, bez tego zawsze można twierdzić, że jest za wolno.
Szablony STL dają duże możliwości, tylko nie wiem czy potrafią zaspokoić wyrafinowane wymagania co do elastyczności i wydajności ;-)
Możesz trzymać sobie zakresy kluczy i dla każdego zakresu mapę, możesz mieć też indeks, który pozwoli Ci przejść od wartości do zakresu i coś tam zrobić.std::map< std::pair<int,int>, std::map<int,int>> rangedMap; std::map< int, std::pair<int,int> > indexToRange;Szablon:
template< class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T> > > class map;
A może prościej byłoby zrobić set tablic, definiując element=stronica jako struktura zawierająca array o stałym rozmiarze, złożony z adresu do kolejnej stronicy + key?
0
Drzewo binarne jest dobre w wyszukiwaniu w ramach jakiegoś porządku.
Jednak jeśli porządek się zmienia to nie sadzę, by było to dobre rozwiązanie.
Jako, że w zasadzie nie opisałeś na czym polega twój problem (ja widzę tykę enigmatyczny opis i niewiele z niego rozumiem), nie sądzę, że ktoś będzie w stanie pomóc.
0
MarekR22 napisał(a):
Drzewo binarne jest dobre w wyszukiwaniu w ramach jakiegoś porządku.
Jednak jeśli porządek się zmienia to nie sadzę, by było to dobre rozwiązanie.
Jako, że w zasadzie nie opisałeś na czym polega twój problem (ja widzę tykę enigmatyczny opis i niewiele z niego rozumiem), nie sądzę, że ktoś będzie w stanie pomóc.
Interesuje mnie utworzenie B-drzewa w ramach stl.
TBTree <Key_data> bt;
potem to bt ma tu funkcjonować jak set:
bt.insert(data);
bt.find(key);
itd.
...
bt.modify(key, key_new); // to jest tu kluczowe: zmiana klucza ma być ekstremalnie szybka!