Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Rozmieszczanie w bloku pamięci nowych gałęzi drzewa



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
AndyBo



Dołączył: 12 Cze 2016
Posty: 5

PostWysłany: Sob Lut 11, 2017 12:44 pm  OP    Temat postu: Rozmieszczanie w bloku pamięci nowych gałęzi drzewa Odpowiedz z cytatem Pisownia

Drzewo Judy dla kluczy 32-bitowych działa tak, że bierze kolejne bajty klucza od najstarszego i tworzy czteropoziomowe drzewo gdzie na każdym poziomie jest 256 wskaźników na niższy poziom. Tak więc dla liczby 0x2378cd12 root wskazuje na tablicę 256 wskaźników, tam wskaźnik o indeksie 0x23 wskazuje na tablicę 256 wskaźników, tam wskaźnik o indeksie 0x78... itd.
Dla 32 bitów bloki są 1024 bajtowe i potrzeba 4 takie poziomy; dla 64 bitów bloki są 2 kiB i potrzeba 8 takich poziomów.
To działa dobrze, gdy ilość gałęzi jest bliska 256. Ale nieefektywnie gdy wynosi 1 czy 2.
Więc kompresujemy poziom, tak że piszemy ilość:2, następnie bajty klucza i wskaźniki: 17,ptr, 31, ptr
Drzewo:
     .
/ \
/ \
17 31
/ \ |
5 35 4
jak to umieszczać w pamięci? co gdy z 17 jeszcze dodane 21? albo do 31 14? Mam segment wielkości 4096 bajtów lub 65536 bajtów. Nie opłaca się jednego segmentu na każde dwie gałęzie, może w jednym segmencie wiele gałęzi ale będzie tam wiele rozrastających się rekordów. Problem podobny do umieszczenia w bazie rekordu, który się rozrośnie.
Gdy mam w bloku rekordy różnej wielkości, to umieszczam tak, że umieszczam je od końca, przed nimi kurcząca się przerwa, z na początku liczba - ilość rekordów i wskaźniki w bloku na nie.
[Count=3, begin0,begin1,begin2,<przerwa> rec1, rec1, rec2]
ale co gdy się rozrastają?
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sob Lut 11, 2017 12:56 pm      Temat postu: Odpowiedz z cytatem Pisownia

Hej,
poczytaj o implementacji struktur drzewiastych... na przykład tutaj...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
AndyBo



Dołączył: 12 Cze 2016
Posty: 5

PostWysłany: Sob Lut 11, 2017 1:27 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Nie wiem czy znajdę, bo nie chodzi mi o implementację w pamięci gdzie za pomocą new[] przydzielam i daję wskaźnik, ale o bloki o wielkościach będących potęgami dwójki, częściowo puste, i wymieniane te blok na dysk. Choć link ciekawy, zobaczę czy jest tam coś.
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sob Lut 11, 2017 1:32 pm      Temat postu: Odpowiedz z cytatem Pisownia

z tego co widzę, to chyba masz problem z właściwą implementacją struktury drzewa... poczytaj troszkę... chyba brakuje Ci podstaw ciut... powodzenia... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.18591 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |