Czy List.Insert ma jakieś kary za wydajność?

Question

Biorąc pod uwagę listę:

List<object> SomeList = new List<object>(); 

Czy idzie:

SomeList.Insert(i, val); 

Vs.

SomeList.Add(val); 

Czy są jakieś kary za wyniki? Jeśli tak, jak to zależy od:
- indeks wstawiania
- - iSomeList.Count - Wielkość listy

Answer 1

klasie Lista jest generyczny odpowiednik klasy ArrayList. Implementuje ogólny interfejs IList, używając tablicy, której rozmiar jest dynamicznie zwiększany zgodnie z wymaganiami.

(source)

ten sposób, że dane wewnętrzne są przechowywane w postaci tablicy, a więc jest prawdopodobne, że aby wykonać insert będzie trzeba przenieść wszystkie elementy powyżej, aby zrobić miejsce, a tym samym jego złożoność jest O (N), natomiast add jest (zamortyzowanym) działaniem O (1) o stałym czasie, więc tak.

Podsumowanie - Tak, prawie zawsze będzie wolniej, a będzie wolniej, im większa będzie twoja lista.

Answer 2

W przypadku wątpliwości, należy wykonać empiryczną eksperyment:

List<object> SomeList = new List<object>(); 

     Stopwatch sw = new Stopwatch(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Insert(0, String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 
     sw.Reset(); 

     SomeList = new List<object>(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Add(String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 

Wstaw trwa 2800ms na moim komputerze; Dodanie trwa 0,8 ms. Więc tak, Insert jest znacznie mniej wydajny.

Answer 3

Oczywiście, że tak.

Ponieważ List<T> jest wspierany przez tablicę, każda operacja do wstawienia na początku listy musi przenieść (lub skopiować) wszystkie inne elementy tablicy. Operacja dodająca do końca listy będzie występować w stałym czasie, niezależnie od liczby pozycji na liście.

Answer 4

Moja pierwsza myśl to "tak, jest kara za wykonanie, ponieważ Insert musi przenieść wszystkie pozycje z listy na jedno miejsce, aby zrobić miejsce na nowy przedmiot" - ale potem przeczytałem to pytanie ostrożniej. Więc:

W ogólnym, Insert trwa (możliwie dużo) więcej czasu, ponieważ musi przenieść wszystkie elementy już na liście, aby zrobić miejsce dla nowego elementu, więc jest to O (n) operacji na długość listy (jeśli lista zostanie wypełniona do pojemności, będzie również wymagać zmiany rozmiaru, ale to wciąż operacja O (n)). Z drugiej strony Add po prostu dołącza nowy element bez potrzeby przenoszenia czegokolwiek, dzięki czemu jest szybszy - operacja O (1) (chyba że lista wymaga zmiany rozmiaru, jak wyżej).

W tym konkretnym przykładzie, gdzie lista jest pusta na początku, nie będzie różnicy w wydajności.

Oczywiście wszystko to jest rodzajem dyskusji, ponieważ powinieneś wybrać metody w oparciu o swoje intencje 10, chyba że masz udokumentowany problem z wydajnością.

Answer 5

Dla pustej listy nie jest inaczej.

Jednak w przypadku innych elementów musi być wolniejszy *, ponieważ do wstawienia z przodu cała tablica podkładowa musi zostać przesunięta o jeden w prawo.

* Z wyjątkiem przypadków, gdy Add powoduje zwiększenie wartości Capacity.

Answer 6

Zdaję sobie sprawę, że odpowiedź została już dokładnie wyjaśniona, ale chciałbym zaznaczyć, że ta informacja jest dostępna w dokumentacji MSDN.

The documentation for List<T>.Insert() stanowi:

tej metody jest to O (n), działanie, gdzie n jest Count.

The documentation for List<T>.Add() stanowi:

Jeśli liczba jest mniejsza niż moc ta metoda O (1) działanie. Jeśli pojemność musi zostać zwiększona, aby pomieścić nowy element, ta metoda staje się operacją O (n), gdzie n oznacza liczbę.

Jeśli zdarzy ci się z tym pytaniem, ponieważ masz do sytuacji, w której chcesz wykonać częściej przyczynia się do przodu i odwrocie listy, a następnie odpowiednie struktury danych do wykorzystania jest Deque.

Stephen Cleary zapewnił dobrą realizację deque tutaj: http://nitodeque.codeplex.com/