Професионална програма
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 3981 Точки

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

 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
MartinBG avatar MartinBG 3981 Точки

Индекса, който подаваш като параметър за инсърта не е достъпен директно, а трябва да се итерира до елемента преди него, което е бавна операция.

 

EDIT:

Нямам възможност да правя тестове в момента, но очаквам инсърт в началото на BigList-а да е доста по-бърз от инсърт в средата (което при до 2 мил. елемента стига до индекс 1 мил.), защото мястото на инсърта ще бъде достигнато по-бързо, а самият инсърт е на практика "безплатен".

0
28/06/2017 15:59:51
Dimo99 avatar Dimo99 1 Точки

Еми доколкото знам BigList не е свързан списак, а въже, което означава, че намирането на индекса би трябвало да отнема O(log N) операции, което би трябвало да е по-бързо от листа, който за да инсъртне на позиция 1 мил. при 2 мил. елемента трябва да премести 1 мил. елемента с една позиция напред. Във самата статия е казано, че добавянето е бързо навсякъде в BigList, а не само в началото или в края:

 The BigList<T> class, however, allows for fast insertions and deletions anywhere in the list.

0
28/06/2017 17:11:40
MartinBG avatar MartinBG 3981 Точки

Да, изказах се неподготвен по-горе :)

BigList-a действително не е свързан списък и по-горните ми предположения не са верни.

 

Прегледах му набързо Source кода и новото ми предположение е, че се бави заради често ребалансиране на дървото при толкова интензивни инсърти на последователни числа.

1
Dimo99 avatar Dimo99 1 Точки

Да точно така е. Благодаря много. Тук тествам с инсърт на рандом позиция https://pastebin.com/XAbZE40z и в действителност BigList е по-бърз, както се очаква.

0