Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Faza odśmiecania Mark a stos
8 views
Skip to first unread message
Borneq
May 26, 2012, 3:40:16 PM5/26/12
to
Faza zaznaczania żywych obiektów osiągalnych z rootów może wyglądać tak:
bierzemy po kolei rooty, dla każdego wywołujemy procedurę która ustawia bit
zaznaczenia w obiekcie. Obiekty mogą mieć pola wskazujące na inne obiekty,
dla każdego wskaźnika obiektu wywołujemy procdurę rekurencyjnie. Działa
dotąd aż osiągnie zaznaczony obiekt, wtedy się cofa i wybiera inny wskaźnik.
Jednak jest problem. Obiekty mogą być połączone w długą listę, przeglądając
tę listę, cały czas pogłębiał będzie się stos. Jak uniknąć niekontrolowanego
rozrostu stosu?
bierzemy po kolei rooty, dla każdego wywołujemy procedurę która ustawia bit
zaznaczenia w obiekcie. Obiekty mogą mieć pola wskazujące na inne obiekty,
dla każdego wskaźnika obiektu wywołujemy procdurę rekurencyjnie. Działa
dotąd aż osiągnie zaznaczony obiekt, wtedy się cofa i wybiera inny wskaźnik.
Jednak jest problem. Obiekty mogą być połączone w długą listę, przeglądając
tę listę, cały czas pogłębiał będzie się stos. Jak uniknąć niekontrolowanego
rozrostu stosu?
Edek Pienkowski
May 26, 2012, 4:43:39 PM5/26/12
to
Dnia Sat, 26 May 2012 21:40:16 +0200, Borneq napisal:
W starych czasach stosy paliły się tak długo jak to było potrzebne. Ale
w czasach dzisiejszych powiedziałbym, że to kwestia iteracji a nie rekurencji.
Tylko kwestia sprawdzenia czy lepiej najpierw wszerz czy najpierw wgłąb.
Edek
w czasach dzisiejszych powiedziałbym, że to kwestia iteracji a nie rekurencji.
Tylko kwestia sprawdzenia czy lepiej najpierw wszerz czy najpierw wgłąb.
Edek
Borneq
May 26, 2012, 4:51:06 PM5/26/12
to
Użytkownik "Edek Pienkowski" <edek.pi...@gmail.com> napisał w
wiadomości news:jprf9r$1eu$1...@inews.gazeta.pl...
będzie długa lista, a może być drzewo lub cykle.
wiadomości news:jprf9r$1eu$1...@inews.gazeta.pl...
> W starych czasach stosy paliły się tak długo jak to było potrzebne. Ale
> w czasach dzisiejszych powiedziałbym, że to kwestia iteracji a nie
> rekurencji.
> Tylko kwestia sprawdzenia czy lepiej najpierw wszerz czy najpierw wgłąb.
Zamiana na iterację to nie taka prosta sprawa, po wskaźniku nie wiadomo że
> w czasach dzisiejszych powiedziałbym, że to kwestia iteracji a nie
> rekurencji.
> Tylko kwestia sprawdzenia czy lepiej najpierw wszerz czy najpierw wgłąb.
będzie długa lista, a może być drzewo lub cykle.
Edek Pienkowski
May 26, 2012, 5:20:48 PM5/26/12
to
Dnia Sat, 26 May 2012 22:51:06 +0200, Borneq napisal:
mamy: lista (lub set) obiektów sprawdzanych llll (nie: sprawdzonych,
sprawdzanych).
Bierzemy pierwszy pointer zawarty w dowolnym obiekcie llll,
jeżeli ostatni to mark i usunąć z listy.
No i ten pointee jak ma więcej niż jeden pointer (i nie mark) to dodajemy
do llll i sprawdzamy pointer. I tak w kółko.
Lista może trochę urosnąć to fakt, ale mniej jest pointerów
niż dowolnej treści obiektów w tym pointerów. W zasadzie to prawie
jest pushdown automaton czyli prawie ze stosem, ale mamy set pointerów
a nie stos wywołań, czyli na pewno lepiej. Lista czy tablica
to nie problem, to jeden obiekt w llll albo jeden link do przodu w liście.
Gorsze są drzewa, ale tu jest log n jeżeli są zbalansowane. Dlatego nie
jest do końca dla mnie oczywiste że wgłąb, wredne niezbalansowane drzewa mogą
powodować długą listę.
Edek
Edek
sprawdzanych).
Bierzemy pierwszy pointer zawarty w dowolnym obiekcie llll,
jeżeli ostatni to mark i usunąć z listy.
No i ten pointee jak ma więcej niż jeden pointer (i nie mark) to dodajemy
do llll i sprawdzamy pointer. I tak w kółko.
Lista może trochę urosnąć to fakt, ale mniej jest pointerów
niż dowolnej treści obiektów w tym pointerów. W zasadzie to prawie
jest pushdown automaton czyli prawie ze stosem, ale mamy set pointerów
a nie stos wywołań, czyli na pewno lepiej. Lista czy tablica
to nie problem, to jeden obiekt w llll albo jeden link do przodu w liście.
Gorsze są drzewa, ale tu jest log n jeżeli są zbalansowane. Dlatego nie
jest do końca dla mnie oczywiste że wgłąb, wredne niezbalansowane drzewa mogą
powodować długą listę.
Edek
Edek
Edek Pienkowski
May 26, 2012, 5:22:42 PM5/26/12
to
Dnia Sat, 26 May 2012 22:51:06 +0200, Borneq napisal:
firey
May 27, 2012, 9:00:37 AM5/27/12
to
a po co wogole odsmiecac - ze skopiuje swoj watek
z warsztatu (czasem tam pisze ale pewnie jak zwykle
jakis moderacki glup sie do mnie dowali:
Cytat: Kos w Dzisiaj o 12:52:16
> Mi za młodu nie przeszkadzało, a teraz po prostu przestałem bałaganić :)
nie dla ciebie wiec wyspa skarbów i przygody
w gaszczu przedziwnych rzeczy w roznych
miejscach (dobrych komixow, starych gier pod
jakies emulatory, sourcow i niedokonzconych gier
posciaganych z jakichs blogow, moich wlasnych
notatek/postow sprzed lat, fotek cyknietych przez siebie albo wyslanych
przez jakies dziewuchy z netu,
ebokow i archiwow stronek, czasem dziwnych 'Tony
Smith costam about hadron 8-costam
way sedonions, octonions and supersymetry', starych
powiesci w formacie txt (poematy eliota, 'a shopshire
lad') itd)
Dla mnie wyjatkowa przyjemnosc plynie z posiadania
wielu takich takich wysypisk ze skarbami a ich system mam dosyc rozbudowany
(przy czym paroletni system ciagle dobrze dziala (pozatym ze stary i miele
po swapie) nigdy jeszcze nie reinstalowalem)
Ciagle powiekszam te archiwa przegladajac neta
(ostatnio czytalem np notki rega i costam sciagnalem przy czym zwykle sporo
czasu mija nim ktoras z tych rzeczy odpale albo poczytam - ale jak sie trafi
odnalezc
taką skrzynie na dnie morza po pieciu latach i w niej cos
b ciekawego to jest to super rzecz (przez to ze jest na
pol albo na zapomniana ale nie calkiem, jakies wspomnienie jest i 'ulezala
sie')
Za to bardzo zaluje jak cos strace, kiedys 10 lat temu pare tygodni pisalem
roguelika pod linucha i choc
naklepalem pewnie ze 2-3 tys linijek i był tam tylko szary lasek, chata i dwu
ochlajusow - kumpli mojego
kumpla ze studiow, ktorzy szukali korkociagu butelki
wina to darze takie stare kawalki takim milym
sentymentem ze czasem o tym utraconym kiepskim kawalku kodu jeszcze mysle.
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
z warsztatu (czasem tam pisze ale pewnie jak zwykle
jakis moderacki glup sie do mnie dowali:
Cytat: Kos w Dzisiaj o 12:52:16
> Mi za młodu nie przeszkadzało, a teraz po prostu przestałem bałaganić :)
nie dla ciebie wiec wyspa skarbów i przygody
w gaszczu przedziwnych rzeczy w roznych
miejscach (dobrych komixow, starych gier pod
jakies emulatory, sourcow i niedokonzconych gier
posciaganych z jakichs blogow, moich wlasnych
notatek/postow sprzed lat, fotek cyknietych przez siebie albo wyslanych
przez jakies dziewuchy z netu,
ebokow i archiwow stronek, czasem dziwnych 'Tony
Smith costam about hadron 8-costam
way sedonions, octonions and supersymetry', starych
powiesci w formacie txt (poematy eliota, 'a shopshire
lad') itd)
Dla mnie wyjatkowa przyjemnosc plynie z posiadania
wielu takich takich wysypisk ze skarbami a ich system mam dosyc rozbudowany
(przy czym paroletni system ciagle dobrze dziala (pozatym ze stary i miele
po swapie) nigdy jeszcze nie reinstalowalem)
Ciagle powiekszam te archiwa przegladajac neta
(ostatnio czytalem np notki rega i costam sciagnalem przy czym zwykle sporo
czasu mija nim ktoras z tych rzeczy odpale albo poczytam - ale jak sie trafi
odnalezc
taką skrzynie na dnie morza po pieciu latach i w niej cos
b ciekawego to jest to super rzecz (przez to ze jest na
pol albo na zapomniana ale nie calkiem, jakies wspomnienie jest i 'ulezala
sie')
Za to bardzo zaluje jak cos strace, kiedys 10 lat temu pare tygodni pisalem
roguelika pod linucha i choc
naklepalem pewnie ze 2-3 tys linijek i był tam tylko szary lasek, chata i dwu
ochlajusow - kumpli mojego
kumpla ze studiow, ktorzy szukali korkociagu butelki
wina to darze takie stare kawalki takim milym
sentymentem ze czasem o tym utraconym kiepskim kawalku kodu jeszcze mysle.
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
0 new messages