Jednym z najbardziej przydatnych przypadków, które znajduję w przypadku list połączonych działających w dziedzinach o krytycznym znaczeniu dla wydajności, takich jak przetwarzanie siatki i obrazów, silniki fizyczne i śledzenie promieni, jest użycie list połączonych, które faktycznie poprawia lokalność odniesienia i zmniejsza alokacje sterty, a czasami nawet zmniejsza użycie pamięci w porównaniu z proste alternatywy.
To może wydawać się kompletnym oksymoronem, który połączone listy mogą zrobić wszystko, ponieważ są znane z tego, że często robią coś przeciwnego, ale mają unikalną właściwość, ponieważ każdy węzeł listy ma ustalony rozmiar i wymagania dotyczące wyrównania, które możemy wykorzystać, aby umożliwić były przechowywane w sposób ciągły i usuwane w stałym czasie w sposób, w jaki rzeczy o zmiennej wielkości nie mogą.
W rezultacie weźmy przypadek, w którym chcemy zrobić analogiczny odpowiednik przechowywania sekwencji o zmiennej długości, która zawiera milion zagnieżdżonych podsekwencji o zmiennej długości. Konkretnym przykładem jest indeksowana siatka przechowująca milion wielokątów (niektóre trójkąty, niektóre czworokąty, niektóre pięciokąty, niektóre sześciokąty itp.), A czasami wielokąty są usuwane z dowolnego miejsca w siatce, a czasami są przebudowywane, aby wstawić wierzchołek do istniejącego wielokąta lub usuń jeden. W takim przypadku, jeśli przechowujemy milion malutkich std::vectors, w końcu mamy do czynienia z alokacją sterty dla każdego pojedynczego wektora, a także z potencjalnie wybuchowym użyciem pamięci. Milion malutkichSmallVectors może nie cierpieć z powodu tego problemu tak bardzo w typowych przypadkach, ale wtedy ich wstępnie przydzielony bufor, który nie jest oddzielnie przydzielany na stertę, może nadal powodować gwałtowne zużycie pamięci.
Problem polega na tym, że milion std::vectorinstancji próbowałoby przechowywać milion rzeczy o zmiennej długości. Rzeczy o zmiennej długości zwykle wymagają alokacji sterty, ponieważ nie mogą być bardzo efektywnie przechowywane w sposób ciągły i usuwane w stałym czasie (przynajmniej w prosty sposób bez bardzo złożonego alokatora), jeśli nie przechowują swojej zawartości gdzie indziej na stercie.
Jeśli zamiast tego zrobimy to:
struct FaceVertex
{
// Points to next vertex in polygon or -1
// if we're at the end of the polygon.
int next;
...
};
struct Polygon
{
// Points to first vertex in polygon.
int first_vertex;
...
};
struct Mesh
{
// Stores all the face vertices for all polygons.
std::vector<FaceVertex> fvs;
// Stores all the polygons.
std::vector<Polygon> polys;
};
... następnie radykalnie zmniejszyliśmy liczbę alokacji sterty i chybień w pamięci podręcznej. Zamiast wymagać alokacji sterty i potencjalnie obowiązkowych błędów pamięci podręcznej dla każdego pojedynczego wielokąta, do którego mamy dostęp, teraz wymagamy alokacji sterty tylko wtedy, gdy jeden z dwóch wektorów przechowywanych w całej siatce przekracza ich pojemność (zamortyzowany koszt). I chociaż krok w kierunku przejścia z jednego wierzchołka do następnego może nadal powodować udział chybień w pamięci podręcznej, wciąż jest to mniejszy niż w przypadku, gdy każdy pojedynczy wielokąt przechowuje oddzielną tablicę dynamiczną, ponieważ węzły są przechowywane w sposób ciągły i istnieje prawdopodobieństwo, że sąsiedni wierzchołek może być dostępne przed eksmisją (zwłaszcza biorąc pod uwagę, że wiele wielokątów doda swoje wierzchołki jednocześnie, co sprawia, że lwia część wierzchołków wielokątów jest idealnie przylegająca).
Oto kolejny przykład:
... gdzie komórki siatki są wykorzystywane do przyspieszania zderzeń cząstek-cząsteczek, powiedzmy, 16 milionów cząstek poruszających się w każdej klatce. W tym przykładzie z siatką cząstek, używając połączonych list, możemy przenieść cząstkę z jednej komórki siatki do drugiej, zmieniając tylko 3 wskaźniki. Wymazywanie z wektora i przesuwanie z powrotem do innego może być znacznie droższe i wprowadzić więcej alokacji sterty. Połączone listy również zmniejszają pamięć komórki do 32 bitów. Wektor, w zależności od implementacji, może wstępnie przydzielić swoją tablicę dynamiczną do punktu, w którym może zająć 32 bajty dla pustego wektora. Jeśli mamy około miliona komórek siatki, to spora różnica.
... i tutaj uważam, że listy z linkami są obecnie najbardziej przydatne, a szczególnie uważam, że odmiana "indeksowanych list połączonych" jest przydatna, ponieważ indeksy 32-bitowe zmniejszają o połowę wymagania dotyczące pamięci łączy na maszynach 64-bitowych i sugerują, że węzły są przechowywane w postaci ciągłej w tablicy.
Często łączę je również z indeksowanymi bezpłatnymi listami, aby umożliwić ciągłe usuwanie i wstawianie w dowolnym miejscu:
W takim przypadku nextindeks wskazuje następny wolny indeks, jeśli węzeł został usunięty, lub następny używany indeks, jeśli węzeł nie został usunięty.
I to jest najważniejszy przypadek użycia, jaki znajduję w przypadku list połączonych w dzisiejszych czasach. Kiedy chcemy przechowywać, powiedzmy, milion pod-sekwencji o zmiennej długości, średnio 4 elementy każda (ale czasami elementy są usuwane i dodawane do jednej z tych sekwencji), połączona lista pozwala nam przechowywać 4 miliony połączone węzły list sąsiadująco zamiast 1 miliona kontenerów, z których każdy jest indywidualnie przydzielony na stertę: jeden gigantyczny wektor, tj. nie milion małych.