Софтуерно Инженерство
Loading...
+ Нов въпрос
Dimo99 avatar Dimo99 1 Точки

[Data Structures] BigList vs List

Някой може ли да ми обясни защо обикновения List e по-бърз при инсъртване, по средата, както от BigList така и от StringBuilder. Като дори при мен BigList хвърли StackOverflowException при 2 000 000 елемента. Кода, с който тествах: https://pastebin.com/e5ps03zG

0
Структури от данни и алгоритми 29/06/2017 18:12:45
aggeorgiev avatar aggeorgiev 326 Точки

Здравей, ето пример:

BigList<T> differs significantly from List<T> in the performance of various operations,................

източник:

http://submain.com/ghostdoc/samples/themes/flatmain/html/883779987.htm

StringBuilder - е бавен, защото приема чститите, сглобява ги и връща <String>, което очевидно са няколко операции.

Успех!

0
Dimo99 avatar Dimo99 1 Точки

Тази статия не казва ли точно че BigList<T> трябва да е по-бърз от List<T> за всякакво инсъртване различно от инсърътване в края, за големи колекции.В случая аз инсъртвам по средата, което при List<T> би трябвало да има сложност n/2, а при BigList<T> сложността би трябвало да е logN тъй като BigList<T> е въже, но пърформанс тестовете ми не показват това.

0
MartinBG avatar MartinBG 1260 Точки

От същата статия: 

 using an index to get or change one element of a BigList, while still reasonably efficient, is significantly slower than using a plain List

Insert метода, който ползваш в тестовете си използва точно индекс и най-вероятно от там идва забавянето.

0
Dimo99 avatar Dimo99 1 Точки

Не мисля че е така, защото аз не ползвам индекс за да взема някакъв елемент от листа. Аз ползвам индекс за да кажа къде точно в листа искам да ми се инсъртне елемента, което би трябвало да работи по-бързо от обикновения лист.

От статията:

With List<T>, inserting or removing elements from anywhere in a large list except the end is very inefficient -- every item after the point of inserting or deletion has to be moved in the list. The BigList<T> class, however, allows for fast insertions and deletions anywhere in the list.

 

0