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

[Kamil Skalski]

Dnia niedziela, 15 maja 2005 01:53, Michal Moskal napisał:
> On 5/14/05, Piotr Kalinowski <pitkali w interia.pl> wrote:
> > Witam,
> >
> > Mam pytanie odnośnie struktury danych, jaką jest lista. Ale nie chodzi
> > mi o stałą listę Nemerle. Jestem ciekaw, czy istnieje możliwość, aby
> > gdzieś w bibliotece Nemerle znalazło się coś takiego, jak "mutable list"
>
> Istnieje.
>
> > (jak to po polsku opisać? :).
>
> Lista ulotna ;-)
>
> > .NET tego nie ma, a jednak wydaje mi się,
> > że czasem taka nieposortowana kolekcja o zmiennym rozmiarze i możliwości
> >  modyfikowania jej struktury w czasie stałym się przydaje.
>
> Mi też się tak wydaje, aczkolwiek nie jestem pewny co do wersji 2.0.

Jeśli dobrze rozumiem to System.Collections.Generics.List to właśnie coś 
takiego (S.C.ArrayList tak samo, tylko że w wersji nie polimorficznej)

>
> > (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.

>
> > 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 :-)

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

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

>
> Just please commit.
>
> BTW, jest lista devel-pl w nemerle.org, gdzie można pisać po polsku. To
> lepsze miejsce na tego typu maile, niż mój adres. Pomimo tego, że nie
> ma tam ruchu, to jednak ktoś ją czyta :-)

-- 
Kamil Skalski
http://nazgul.omega.pl