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 add
operacji):
1 -> 2 -> 3 -> 4
i powiedz, że chcę dołączyć 5
.
Aby to zrobić, ponieważ węzeł 4
jest niezmienny, muszę utworzyć nową kopię 4
, ale zastąpić jej next
pole nowym węzłem zawierającym 5
. Problem polega na tym, że 3
odwołuje się do starego 4
; ten bez dołączonego 5
. Teraz muszę skopiować 3
i zastąpić jego next
pole, aby odwołać się do 4
kopii, ale teraz 2
odwoł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.
źródło
CopyOnWritexxx
klasy używane do wielowątkowości. Nikt nie spodziewa się, że kolekcje są niezmienne (chociaż powoduje to pewne dziwactwa)Odpowiedzi:
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ż:
Przygotowanie a
1
daje:Pamiętaj jednak, że nie ma znaczenia, czy ktoś nadal trzyma odniesienie na
2
początku swojej listy, ponieważ lista jest niezmienna, a linki prowadzą tylko w jedną stronę. Nie ma sposobu, aby powiedzieć, że1
jest, nawet jeśli masz tylko odniesienie2
. Teraz, jeśli dołączysz5
jedną z list, będziesz musiał wykonać kopię całej listy, ponieważ w przeciwnym razie pojawiłaby się również na drugiej liście.źródło
Masz rację, dołączanie wymaga skopiowania całej listy, jeśli nie chcesz mutować żadnych węzłów w miejscu. Ponieważ musimy ustawić
next
wskaźnik (teraz) od drugiego do ostatniego węzła, który w niezmiennym ustawieniu tworzy nowy węzeł, a następnie musimy ustawićnext
wskaźnik od trzeciego do ostatniego węzła i tak dalej.Myślę, że podstawowym problemem tutaj nie jest niezmienność, ani też
append
operacja 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):
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.List
inne 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
map
lubfold
(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ęć.źródło
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.
źródło
List
interfejs (chociaż mogę się mylić). Nie sądzę jednak, aby ten kawałek naprawdę odpowiadał na pytanie. Całą listę nadal trzeba będzie skopiować; po prostu przyspieszy dostęp do ostatniego dodanego elementu, ponieważ nie będzie wymagane pełne przejście.java.util.List
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
StringBuilder
do skonstruowania łańcucha, a na końcu otrzymujesz wynik jakoString
(niezmienny!) Przez wywołanietoString
. Jedną różnicą jest to, że aStringBuilder
jest 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
DList
klasy, która zapewnia podobny interfejs jak w przypadku Haskella, powinna być dość łatwaData.DList
.źródło
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:
źródło
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ć.źródło
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
final
odniesieniem do pierwszego węzła na liście z łączem do przodu i początkowo zerowego brakufinal
odniesienia, który (gdy nie jest -null) identyfikuje obiekt listy odwrotnej, przechowujący te same elementy w odwrotnej kolejności, oraz obiekt listy odwróconej wfinal
odniesieniu 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
final
odniesienie i utworzenia nowego obiektu listy tego samego typu co oryginał, zfinal
odniesieniem 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łbyfinal
odwoł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ż
volatile
zmienne 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.źródło