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

[Michal Moskal]

On 5/14/05, Piotr Kalinowski <pitkali at 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.

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

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

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

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

Just please commit.

BTW, jest lista devel-pl at 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 :-)

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