Czy jest szybsza implementacja TList?

Question

Moja aplikacja intensywnie korzysta z TList, więc zastanawiałem się, czy istnieją jakieś alternatywne implementacje, które są szybsze lub zoptymalizowane dla konkretnego przypadku użycia.

Znam o RtlVCLOptimize.pas 2.77, który ma zoptymalizowane implementacje kilku metod TList.

Ale chciałbym wiedzieć, czy jest tam coś jeszcze. Nie wymagam też, aby był to potomek TList, potrzebuję tylko funkcji TList, niezależnie od tego, w jaki sposób jest ona zaimplementowana.

Jest całkiem możliwe, biorąc pod uwagę raczej podstawowe funkcje TList, że nie ma wiele miejsca na ulepszenia, ale nadal chcielibyśmy to sprawdzić, stąd to pytanie.

edytuj: W moim przypadku użycia nie są sortowane żadne listy. Istnieje wiele list z wieloma różnymi elementami. Wymieniłem TList z moją własną klasą, aby rejestrować liczbę połączeń Dodaj/Usuń i liczbę elementów. Zgłasza (toatal dla wszystkich list):

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012 

Mogę również dowiedzieć się, jaka jest najwyższa liczba elementów na jednej liście.

Nie mam żadnego szczególnego problemu. Zastanawiam się tylko, czy istnieje sposób, aby przyspieszyć jego działanie, ponieważ z tymi liczbami wynikałoby nawet małe ulepszenie.

Answer 1

Jednym z największych wąskich gardeł, jakie znam o TList, jest Delete/Extract na dużej liście. Usunięcie pozycji [0] jest dużo wolniejsze niż usunięcie pozycji [liczba-1] z powodu ruchu pamięci, który następuje po niej.

Dla exemple, na liście zawierającej 65536 elementy:

while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete 

for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec 

Więc jeśli masz TList z milionów elementów, usunięcie elementu niskim indeksie mogą być kosztowne z punktu widzenia wydajności.Należy również pamiętać, że posiadanie listy, która nie jest posortowana, powoduje, że bardzo powoli znajduje się w niej element. IndexOf jest bardzo powolny na dużej liście. Możesz rozważyć utrzymanie sortowania listy.

Ponadto, biorąc pod uwagę, że liczba elementów może być dość duża, warto rozważyć użycie listy TList do przechowywania elementów, co pomoże zmniejszyć koszty związane z usuwaniem/usuwaniem, o których już wspomniałem.

Answer 2

Najszybsza struktura danych zwykle nie jest strukturą danych, ale jest tylko symulacją, która pobiera dane tylko w razie potrzeby, podobnie jak robi to Virtual Treeview. Być może możesz napisać coś w rodzaju TVirtualList, która wywołuje odpowiednie funkcje do zbierania wymaganych danych, gdy żądane są elementy.

Answer 3

Wygląda na to, że robisz dużo dodatków. Nie wiem, ile list jest rozrzuconych, ale jeśli twoje indywidualne listy rosną bardzo duże, możesz chcieć zaimplementować listę, która będzie się szybciej rozwijać.

Spójrz na TList.Grow, która jest wywoływana podczas próby dodania elementu do listy, gdzie wszystkie elementy tablicy są w użyciu, a zobaczysz, że rośnie o 25%. Ma to na celu obniżenie zużycia pamięci do rozsądnego poziomu. Ale jeśli potrzebujesz naprawdę dużych list, utwórz własną klasę potomków i przesuń Grow, aby w drugiej linii zamiast Delta := FCapacity div 4 było napisane Delta := FCapacity. Dzięki temu twoja lista rośnie dwukrotnie za każdym razem, co oznacza mniej reallocs i mniej kopii.

Ale to, co prawdopodobnie cię zabija, to te wszystkie wywołania Usuń. Usuń musi znaleźć element, zanim będzie mógł go usunąć, co pociąga za sobą wywołanie IndexOf, które jest liniowym skanem całej tablicy. Jeśli masz dużą listę i robisz dużo usunięć, to zabije twój występ.

Do czego używasz tych list, szczególnie tych dużych? W zależności od tego, co robisz z nimi, mogą istnieć lepsze struktury danych dla zadania.

Answer 4

Czy korzystasz z procedury powiadamiania? Jeśli nie, zrób własną implementację TList. Z powodu procedury Notify TList.Clear (która jest wywoływana podczas destrukcji) jest operacją O (n). Metoda TList.Clear wywołuje SetCount, który z kolei wywołuje Delete dla wszystkich zawartych w nim elementów, więc w przypadku każdego usuniętego elementu zostanie wywołana procedura Notify. Jeśli nie chcesz przesłonić metody Notify, możesz dostosować procedurę SetCount, aby nie wywoływać Delete. Dzięki temu zaoszczędzisz czas 15.766.012 - 10.630.000 = 5.136.012 Usuń połączenia.

Uwaga: uzyskany przyrost wydajności nigdy nie będzie tak duży, jak uzyskany zysk, sortując listę i optymalizując procedurę usuwania, jak sugeruje Mason Wheeler. Chyba że lista zawiera bardzo małą liczbę pozycji, a funkcja porównywania zajmuje dużo czasu.