Czy listy połączone powinny zawsze mieć wskaźnik ogona?

Moje zrozumienie...

Zalety:

• Wstawianie na końcu to O (1) zamiast O (N).
• Jeśli lista jest listą podwójnie połączoną, usunięcie z końca również oznacza O (1) zamiast O (N).

Niekorzyść:

• Zajmuje trywialną ilość dodatkowej pamięci: 4-8 bajtów .
• Osoba wdrażająca musi śledzić ogon.

Patrząc na te zalety i wady, nie rozumiem, dlaczego lista połączona unikałaby używania wskaźnika ogona. Czy czegoś brakuje?

Masz rację, wskaźnik ogona nigdy nie boli i może jedynie pomóc. Jednak zdarza się, że wcale nie jest potrzebny wskaźnik ogona.

Jeśli do implementacji stosu używana jest lista połączona, wskaźnik ogona nie jest potrzebny, ponieważ można zagwarantować, że wszystkie operacje dostępu, wstawiania i usuwania będą odbywać się na czele. Biorąc to pod uwagę, i tak można użyć podwójnie połączonej listy ze wskaźnikiem ogona, ponieważ jest to standardowa implementacja w bibliotece lub platformie, a pamięć jest tania, ale nie jest potrzebna .

Listy połączone są bardzo często trwałe i niezmienne. W rzeczywistości w funkcjonalnych językach programowania takie użycie jest wszechobecne. Wskaźniki ogona łamią obie te właściwości. Jeśli jednak nie zależy ci na niezmienności lub wytrwałości, włączenie wskaźnika ogona ma bardzo niewielką wadę.

Rzadko używam wskaźnika ogona do list połączonych i częściej używam list pojedynczo połączonych, gdy wystarczający jest podobny do stosu wzorzec wstawiania i usuwania (lub po prostu liniowe usuwanie od środka). Jest tak, ponieważ w moich typowych przypadkach użycia wskaźnik ogona jest w rzeczywistości drogi, podobnie jak przekształcenie pojedynczo połączonej listy w podwójnie połączoną listę jest drogie.

Często moje częste użycie pojedynczej listy może przechowywać setki tysięcy połączonych list, które zawierają tylko kilka węzłów list. Generalnie też nie używam wskaźników do list połączonych. Zamiast tego używam indeksów do tablicy, ponieważ indeksy mogą być 32-bitowe, np. Zajmują połowę 64-bitowego wskaźnika. Zasadniczo również nie przydzielam węzłów listy pojedynczo, a zamiast tego po prostu używam dużej tablicy do przechowywania wszystkich węzłów, a następnie używam 32-bitowych wskaźników, aby połączyć węzły ze sobą.

Jako przykład wyobraź sobie grę wideo wykorzystującą siatkę 400 x 400 do podziału miliona cząstek, które poruszają się i odbijają od siebie, aby przyspieszyć wykrywanie kolizji. W takim przypadku dość skutecznym sposobem przechowywania jest przechowywanie 160 000 pojedynczo połączonych list, co w moim przypadku przekłada się na 160 000 32-bitowych liczb całkowitych (~ 640 kilobajtów) i jedną 32-bitową liczbę całkowitą na cząsteczkę. Teraz, gdy cząstki poruszają się po ekranie, wystarczy zaktualizować kilka 32-bitowych liczb całkowitych, aby przenieść cząstkę z jednej komórki do drugiej, w następujący sposób:

... z nextindeksem („wskaźnikiem”) węzła cząstki służącym albo jako indeks następnej cząstki w komórce, albo następnej wolnej cząstki do odzyskania, jeśli cząstka umarła (w zasadzie implementacja darmowej listy przy użyciu indeksów):

Usunięcie liniowego czasu z komórki nie jest w rzeczywistości narzutem, ponieważ przetwarzamy logikę cząstek poprzez iterację przez cząstki w komórce, więc podwójnie połączona lista po prostu dodałaby narzut w rodzaju, który nie jest korzystny w wszystko w moim przypadku tak samo, jak ogon w ogóle mnie nie skorzysta.

Wskaźnik ogona podwoiłby użycie pamięci przez siatkę, a także zwiększył liczbę braków pamięci podręcznej. Wymaga również wstawienia, aby gałąź wymagała sprawdzenia, czy lista jest pusta, a nie bez gałęzi. Utworzenie podwójnie połączonej listy podwoiłoby narzut listy każdej cząstki. W 90% przypadków korzystam z list połączonych, dotyczy to takich przypadków, a więc przechowywanie wskaźnika ogona byłoby stosunkowo dość drogie.

Tak więc 4-8 bajtów w rzeczywistości nie jest trywialne w większości kontekstów, w których przede wszystkim używam list połączonych. Chciałem tam po prostu włożyć chip, ponieważ jeśli używasz struktury danych do przechowywania mnóstwa elementów, to 4-8 bajtów nie zawsze może być tak pomijalne. Właściwie używam połączonych list, aby zmniejszyć liczbę przydzielanych pamięci i wymaganą ilość pamięci, w przeciwieństwie do, powiedzmy, przechowywania 160 000 dynamicznych tablic, które rosną dla siatki, która miałaby wybuchowe użycie pamięci (zwykle jeden wskaźnik plus dwie liczby całkowite przynajmniej na komórkę siatki wraz z przydziałami sterty na komórkę siatki, w przeciwieństwie do tylko jednej liczby całkowitej i zerowej przydziału sterty na komórkę).

Często zdarza się, że wiele osób sięga po połączone listy ze względu na ich ciągły czas związany z usunięciem przodu / środka i wstawieniem przodu / środka, gdy LL są często złym wyborem w tych przypadkach z powodu ogólnego braku ciągłości. Tam, gdzie LL są dla mnie piękne z punktu widzenia wydajności, to zdolność do przenoszenia jednego elementu z jednej listy do drugiej poprzez manipulowanie kilkoma wskaźnikami i możliwość uzyskania struktury danych o zmiennej wielkości bez alokatora pamięci o zmiennej wielkości (ponieważ każdy węzeł ma jednolity rozmiar, możemy użyć darmowych list, np.). Jeśli każdy węzeł listy jest indywidualnie alokowany w stosunku do alokatora ogólnego przeznaczenia, zwykle wtedy listy połączone są znacznie gorsze w porównaniu z alternatywami, a „

Sugerowałbym zamiast tego, że w większości przypadków, w których listy połączone służą jako bardzo skuteczna optymalizacja w stosunku do prostych alternatyw, najbardziej przydatne formy są zazwyczaj pojedynczo połączone, potrzebują tylko wskaźnika głównego i nie wymagają alokacji pamięci ogólnego przeznaczenia na węzeł i zamiast tego często może po prostu przydzielić pamięć już przydzieloną na węzeł (np. z dużej tablicy już przydzielonej wcześniej). Również każda SLL przechowuje w tych przypadkach bardzo małą liczbę elementów, takich jak krawędzie połączone z węzłem graficznym (wiele małych połączonych list w przeciwieństwie do jednej ogromnej połączonej listy).

Warto również pamiętać, że mamy obecnie mnóstwo pamięci DRAM, ale jest to drugi najwolniejszy dostępny rodzaj pamięci. Nadal mamy około 64 KB na rdzeń, jeśli chodzi o pamięć podręczną L1 z 64-bajtowymi liniami pamięci podręcznej. W rezultacie te małe bajty oszczędności mogą naprawdę mieć znaczenie w krytycznym dla wydajności obszarze, takim jak powyższa karta SIM, gdy zostaną pomnożone miliony razy, jeśli oznacza to różnicę między przechowywaniem dwukrotnie większej liczby węzłów w linii pamięci podręcznej, czy nie, np.