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?

do góry

Dnia Sat, 26 May 2012 21:40:16 +0200, Borneq napisal:

> 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?

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

do góry

Użytkownik "Edek Pienkowski" <e...@g...com> napisał w
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
będzie długa lista, a może być drzewo lub cykle.

do góry

Dnia Sat, 26 May 2012 22:51:06 +0200, Borneq napisal:

> Użytkownik "Edek Pienkowski" <e...@g...com> napisał w
> 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
> będzie długa lista, a może być drzewo lub cykle.

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

do góry

Dnia Sat, 26 May 2012 22:51:06 +0200, Borneq napisal:

> Użytkownik "Edek Pienkowski" <e...@g...com> napisał w
> 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
> będzie długa lista, a może być drzewo lub cykle.

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

do góry

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/

do góry