Czy istnieje jakiś praktyczny sposób, aby struktura połączonego węzła była niezmienna?

Postanowiłem napisać pojedynczo połączoną listę i miałem plan, aby wewnętrzna struktura połączonego węzła była niezmienna.

Wpadłem jednak na przeszkodę. Powiedz, że mam następujące połączone węzły (z poprzednich addoperacji):

1 -> 2 -> 3 -> 4

i powiedz, że chcę dołączyć 5.

Aby to zrobić, ponieważ węzeł 4jest niezmienny, muszę utworzyć nową kopię 4, ale zastąpić jej nextpole nowym węzłem zawierającym 5. Problem polega na tym, że 3odwołuje się do starego 4; ten bez dołączonego 5. Teraz muszę skopiować 3i zastąpić jego nextpole, aby odwołać się do 4kopii, ale teraz 2odwołuje się do starego 3...

Innymi słowy, aby zrobić dodatek, cała lista wydaje się wymagać skopiowania.

Moje pytania:

• Czy moje myślenie jest prawidłowe? Czy jest jakiś sposób na wykonanie append bez kopiowania całej struktury?

• Najwyraźniej „Skuteczna Java” zawiera zalecenie:

  Klasy powinny być niezmienne, chyba że istnieje bardzo dobry powód, aby je modyfikować ...

  Czy to dobry argument za zmiennością?

Nie sądzę, że jest to kopia sugerowanej odpowiedzi, ponieważ nie mówię o samej liście; to oczywiście musi być modyfikowalne, aby dostosować się do interfejsu (bez robienia czegoś takiego, jak utrzymywanie nowej listy wewnętrznie i pobieranie jej za pomocą gettera. Jednak przy drugiej przemyśleniu nawet to wymagałoby pewnej mutacji; byłoby to po prostu ograniczone do minimum). Mówię o tym, czy elementy wewnętrzne listy muszą być niezmienne.

Dzięki listom w językach funkcjonalnych prawie zawsze pracujesz z głową i ogonem, pierwszym elementem i resztą listy. Przygotowywanie jest o wiele bardziej powszechne, ponieważ, jak się domyślasz, dołączanie wymaga skopiowania całej listy (lub innych leniwych struktur danych, które nie przypominają dokładnie połączonej listy).

W imperatywnych językach dodawanie jest znacznie częstsze, ponieważ ma tendencję do bycia bardziej naturalnym semantycznie i nie przejmujesz się unieważnianiem odniesień do poprzednich wersji listy.

Jako przykład, dlaczego poprzedzanie nie wymaga kopiowania całej listy, rozważ:

2 -> 3 -> 4

Przygotowanie a 1daje:

1 -> 2 -> 3 -> 4

Pamiętaj jednak, że nie ma znaczenia, czy ktoś nadal trzyma odniesienie na 2początku swojej listy, ponieważ lista jest niezmienna, a linki prowadzą tylko w jedną stronę. Nie ma sposobu, aby powiedzieć, że 1jest, nawet jeśli masz tylko odniesienie 2. Teraz, jeśli dołączysz 5jedną z list, będziesz musiał wykonać kopię całej listy, ponieważ w przeciwnym razie pojawiłaby się również na drugiej liście.

Masz rację, dołączanie wymaga skopiowania całej listy, jeśli nie chcesz mutować żadnych węzłów w miejscu. Ponieważ musimy ustawić nextwskaźnik (teraz) od drugiego do ostatniego węzła, który w niezmiennym ustawieniu tworzy nowy węzeł, a następnie musimy ustawić nextwskaźnik od trzeciego do ostatniego węzła i tak dalej.

Myślę, że podstawowym problemem tutaj nie jest niezmienność, ani też appendoperacja nie jest odradzana. Oba są w porządku w swoich domenach. Mieszanie ich jest złe: naturalny (skuteczny) interfejs dla niezmiennej listy podkreślał manipulację na początku listy, ale w przypadku list zmiennych często bardziej naturalne jest budowanie listy przez kolejne dodawanie elementów od pierwszej do ostatniej.

Dlatego sugeruję, abyś zdecydował: czy chcesz mieć interfejs efemeryczny czy trwały? Czy większość operacji tworzy nową listę i pozostawia dostępną niezmodyfikowaną wersję (trwałą), czy piszesz taki kod (efemeryczny):

list.append(x);
list.prepend(y);

Oba wybory są w porządku, ale implementacja powinna odzwierciedlać interfejs: trwała struktura danych korzysta z niezmiennych węzłów, podczas gdy efemeryczna potrzebuje wewnętrznej zmienności, aby faktycznie spełnić obietnice dotyczące wydajności, jakie niesie. java.util.Listinne interfejsy są efemeryczne: implementacja ich na niezmiennej liście jest niewłaściwa i w rzeczywistości stanowi zagrożenie dla wydajności. Dobre algorytmy na zmiennych strukturach danych często różnią się od dobrych algorytmów na niezmiennych strukturach danych, więc ubranie niezmiennej struktury danych jako zmiennej (lub odwrotnie) zachęca do złych algorytmów.

Chociaż lista trwała ma pewne wady (brak wydajnego dołączania), nie musi to stanowić poważnego problemu podczas programowania funkcjonalnego: Wiele algorytmów można skutecznie sformułować, zmieniając sposób myślenia i używając funkcji wyższego rzędu, takich jak maplub fold(aby wymienić dwa stosunkowo prymitywne) ) lub poprzedzenie wielokrotnie. Co więcej, nikt nie zmusza cię do korzystania tylko z tej struktury danych: gdy inni (efemeryczni lub wytrwali, ale bardziej wyrafinowani) są bardziej odpowiedni, skorzystaj z nich. Powinienem również zauważyć, że trwałe listy mają pewne zalety w przypadku innych obciążeń: dzielą się swoimi ogonami, co może oszczędzać pamięć.

Jeśli masz pojedynczo połączoną listę, będziesz pracować z przodu, jeśli będzie więcej niż z tyłu.

Języki funkcjonalne, takie jak prolog i haskel, zapewniają łatwe sposoby uzyskania elementu przedniego i reszty tablicy. Dołączanie z tyłu jest operacją O (n) z kopiowaniem każdego węzła.

Jak zauważyli inni, masz rację, że niezmienna pojedynczo połączona lista wymaga skopiowania całej listy podczas wykonywania operacji dołączania.

Często można skorzystać z obejścia implementacji algorytmu pod względem cons(poprzedzających) operacji, a następnie raz odwrócić ostateczną listę. To wciąż musi skopiować listę raz, ale narzut złożony jest liniowy na całej długości listy, podczas gdy wielokrotne używanie append pozwala łatwo uzyskać kwadratową złożoność.

Listy różnic (patrz np. Tutaj ) są interesującą alternatywą. Lista różnic zawija listę i zapewnia operację dołączania w stałym czasie. Zasadniczo pracujesz z opakowaniem tak długo, jak potrzebujesz go dołączyć, a następnie po zakończeniu konwertujesz z powrotem na listę. Jest to w pewien sposób podobne do tego, co robisz, gdy używasz a StringBuilderdo skonstruowania łańcucha, a na końcu otrzymujesz wynik jako String(niezmienny!) Przez wywołanie toString. Jedną różnicą jest to, że a StringBuilderjest zmienna, ale lista różnic jest niezmienna. Ponadto, kiedy konwertujesz listę różnic z powrotem na listę, nadal musisz zbudować całą nową listę, ale znowu musisz to zrobić tylko raz.

Implementacja niezmiennej DListklasy, która zapewnia podobny interfejs jak w przypadku Haskella, powinna być dość łatwa Data.DList.

Musisz obejrzeć ten świetny film z 2015 React conf przez Immutable.js Stwórcy Lee Byron. Da ci wskazówki i struktury, aby zrozumieć, jak zaimplementować skuteczną niezmienną listę, która nie powiela treści. Podstawowe pomysły są następujące: - o ile dwie listy używają identycznych węzłów (ta sama wartość, ten sam następny węzeł), używany jest ten sam węzeł - gdy listy zaczynają się różnić, w węźle rozbieżności tworzona jest struktura, która utrzymuje wskaźniki następny konkretny węzeł każdej listy

Ten obraz z samouczka reagowania może być wyraźniejszy niż mój zepsuty angielski:

To nie jest wyłącznie Java, ale sugeruję przeczytanie tego artykułu o niezmiennej, ale wydajnej indeksowanej trwałej strukturze danych napisanej w Scali:

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

Ponieważ jest to struktura danych Scala, można go również używać z Javy (z nieco większą gadatliwością). Opiera się on na strukturze danych dostępnej w Clojure, i jestem pewien, że oferuje również bardziej „rodzimą” bibliotekę Java.

Również uwaga na temat budowania niezmiennych struktur danych: zwykle potrzebujesz czegoś w rodzaju „Konstruktora”, który pozwala „mutować” strukturę danych „w budowie” poprzez dołączanie do niej elementów (w ramach jednego wątku); po zakończeniu dołączania wywołujesz metodę na obiekcie „w budowie”, takim jak .build()lub .result(), który „buduje” obiekt, co daje niezmienną strukturę danych, którą możesz bezpiecznie udostępnić.

Podejściem, które czasem może być pomocne, byłoby posiadanie dwóch klas obiektów przechowujących listy - obiektu listy do przodu z finalodniesieniem do pierwszego węzła na liście z łączem do przodu i początkowo zerowego braku finalodniesienia, który (gdy nie jest -null) identyfikuje obiekt listy odwrotnej, przechowujący te same elementy w odwrotnej kolejności, oraz obiekt listy odwróconej w finalodniesieniu do ostatniej pozycji listy odwróconej i początkowo zerowej nie-końcowej referencji, która (gdy nie jest -null) identyfikuje obiekt listy forward zawierający te same elementy w odwrotnej kolejności.

Przygotowanie elementu do listy przewijania lub dołączenie elementu do listy odwrotnej wymagałoby jedynie utworzenia nowego węzła, który łączy się z węzłem zidentyfikowanym przez finalodniesienie i utworzenia nowego obiektu listy tego samego typu co oryginał, z finalodniesieniem do tego nowego węzła.

Dołączenie elementu do listy przewijania lub przechodzenie do listy odwrotnej wymagałoby posiadania listy przeciwnego typu; za pierwszym razem, gdy robi się to z konkretną listą, powinna utworzyć nowy obiekt przeciwnego typu i zapisać referencję; powtórzenie akcji powinno ponownie wykorzystać listę.

Należy zauważyć, że stan zewnętrzny obiektu listy będzie uważany za taki sam, niezależnie od tego, czy odniesienie do listy typu przeciwnego jest puste, czy identyfikuje listę przeciwnego rzędu. Nie byłoby potrzeby wprowadzania żadnych zmiennych final, nawet przy użyciu kodu wielowątkowego, ponieważ każdy obiekt listy zawierałby finalodwołanie do pełnej kopii jego zawartości.

Jeśli kod w jednym wątku tworzy i buforuje odwróconą kopię listy, a pole, w którym ta kopia jest buforowana, nie jest ulotne, możliwe, że kod w innym wątku może nie widzieć listy w pamięci podręcznej, ale będzie to jedyny niekorzystny efekt z tego wynika, że ​​drugi wątek musiałby wykonać dodatkową pracę, budując kolejną odwróconą kopię listy. Ponieważ takie działanie w najgorszym przypadku pogorszyłoby wydajność, ale nie wpłynęłoby na poprawność, a ponieważ volatilezmienne same w sobie powodują obniżenie wydajności, często lepiej jest, aby zmienna była nieulotna i akceptowała możliwość sporadycznych operacji zbędnych.