[nem-pl] Re: [Nemerle] struktura danych - lista

[Michal Moskal]

On 5/15/05, Kamil Skalski <nazgul at nemerle.org> wrote:
> > > (Właściwie to jestem pewien, że by MI się przydała ;) Mam na sumieniu
> > > bibliotekę C++ do zarządzania historią wiadomości ekg i najbardziej
> > > odpowiednią strukturą do trzymania listy wiadomości jest w moim odczuciu
> > > lista wiązana. No bo jak modyfikuje listę, która trzyma 70 000
> > > wiadomości o łącznej objętości kilku mega (a kolega, który pisze UI ma
> > > tego kilkanaście mega ;), to złożoność O(n) dla większości użytkowników
> > > może nie być zadowalająca, zwłaszcza, jeśli istnieje tak prosta i
> > > oczywista alternatywa...)
> >
> > Ja bym pewnie użył drzewa. No ale ja jestem inny ;) A lista taka była
> > mi kiedyś potrzebna do drzew dominatorów czy jakieś postaci SSA, nie
> > pamiętam.
> 
> Ej, no to typowy std::vector jest. W Nemerle mamy Nemerle.Collections.Vector
> kótry choć ograniczony ma symulować możliwości S.C.G.List.

Lista łączona ma to do siebie, że można wstawiać elementy w jej
środku, w czasie stałym. Vector oczywiście tej własności nie posiada.

> > > Jeśli powinienem napisać o tym gdzieś indziej - powiedz :) Jeśli
> > > uważasz, że to raczej element na osobną bibliotekę, którą powinienem
> > > sobie napisać i być może umieścić gdzieś na BerliOSie lub SF - też
> > > chciałbym wiedzieć ;)
> >
> > Nie, trunk/lib/ będzie w porządku. Powinniśmy uruchamiać testy z
> > lib/tests/ co jutro obiecuję zrobić. Więc razem z klasą wskazany byłby
> > plik z testami (przykłady w ncc/testsuite/positive/).
> 
> Do lib to może powinniśmy od razu unit testy zaprzągnąć. Nie żeby nasz test.n
> sobie nie radził, ale trzeba poszerzać spektrum używanych technologii i ja
> chętnie nauczę się korzystania z unit testów - przyda się w przyszłości na
> pewno :-)

Można i tak.

> > > Mógłbym nawet pokazać przykładową implementację, którą skleciłem pisząć
> > > program na laboratorium z algorytmów. To taka lista wiązana,
> > > dwukierunkowa, z iteratorem do chodzenia po niej. Iterator implementuje
> > > IEnumerator, ale jednocześnie property Current pozwala też na zapis do
> > > węzła, iterator potrafi chodzić nie tylko do przodu i ponadto
> > > modyfikować strukturę listy (dodawać elementy, usuwać je, itp.)
> >
> > Super!
> 
> No więc to jest tak, że my mamy niezły chaos z tymi bibliotekami. Bo jeszcze
> jest N.C.LinkedList - może dałoby się podmienić jej implementację na tą nową,
> o której mówi Piotr?

Ten LinkedList to jest stos pod inną nazwą. Nie bardzo mi się to
podoba, ale nie wiem czy możemy to ot tak sobie zmienić, może ktoś
tego używa?

> > > Wewnętrznie ma trzy rodzaje węzłów (w postaci wariantu). Nie sądziłem,
> > > że kiedyś napiszę listę używającą wartowników początka i końca, ale
> > > potrzebowałem trzech stanów dla iteratora, aby mógł zachowywać się tak
> > > samo przebiegając w każdą ze stron. Jest więc Head, Body i Tail. Tylko
> > > Body przechowuje elementy. Pusta lista ma węzły Head i Tail, wskazujące
> > > na siebie nawzajem (acz funkcja Empty() sprawdza tylko, czy Head.first
> > > wskazuje na ogon).
> > >
> > > To by było na tyle. Jeśli uważasz, że jednak któraś struktura .NETa jest
> > > w stanie służyć, za taką listę, to chętnie się o tym dowiem ;)
> 
> Taki szczegół techniczny - do opisu rodzaju węzła pewnie lepiej użyć enuma -
> nie tworzy dodatkowych klas i jest szybszy.

Niekoniecznie.

enum Kind { |A|B }
class Node {
  k : Kind;
  data : 'a; ...
}

zajmuje więcej pamięci niż

variant Node {
  | A { data:'a }
  | B
}

(znaczy nawet element A zajmuje teraz mniej pamięci).

-- 
   Michal Moskal,
   http://nemerle.org/~malekith/