eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingFaza odśmiecania Mark a stosRe: Faza odśmiecania Mark a stos
  • Data: 2012-05-26 23:20:48
    Temat: Re: Faza odśmiecania Mark a stos
    Od: Edek Pienkowski <e...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: