Array VS List. Колко по-бавни са листовете ?

Losko 69 Точки

Array VS List. Колко по-бавни са листовете ?

Опитах се да реша задача [Exercises: Arrays and Lists]10. Pairs by Difference. Като използвам Лист, но получих грешка "Лимит време".
Memory: 10.12 MB
Time: 0.406 s
На лекцията за масиви и листове когато попитаха лектора, "Защо след като листовете са по-добри не ползваме само тях." той одговори,
че били по-бавни и ако не ни трябва тяхната функционалност, по-добре да си ползваме масиви... Така и направих и всичко мина ок.
Memory: 9.25 MB
Time: 0.265 s.
Във варианта с масиви в отделен метод си правя масива... тествах ако не ползвам метод и там времето се качи леко.
Memory: 9.26 MB
Time: 0.281 s
Ще оставя линк кум кода като коментирания код е решението с лист.
Ако може някой да каже защо работи почти два пъти по бавно, както и защо метода също оказва влиание след като кода в нго и без него е 100% един и същ ?
http://pastebin.com/Fmsmuizv

Тагове:

09/10/2016 11:23:00 Programming Fundamentals

msmilkoff 338 Точки

Не са бавни, зависи за каква операция говорим. Листът отдолу е просто масив, който се оразмерява, когато се препълни. Например, Add е бърза операция освен в редките случаи на оразмеряване, а Contains е бавна, защото обикаля по всички елементи. На теб май ти се бави, защото правиш два листа и добавяш елементи два пъти, което подсказва че имаме потенциално две оразмерявания минимум, което ти забавя алгоритъма. Вместо да четеш числата като стринг и да ги добавяш в лист, след което да създаваш нов лист и да прехвърляш данните, ползвай:
var nums = Console.ReadLine().Split().Select(int.Parse).ToList(); и виж дали пак ще ти даде лимит време.

09/10/2016 11:39:18

Losko 69 Точки

Ок, По този начин се вписах в условието, но пак е доста по бавно.
"List<int> nums = Console.ReadLine().Split().Select(int.Parse).ToList();"

А този "Select(int.Parse)" От къде идва ... Мисля, че разбирам какво прави, но до лекцията за Масиви и Листове не съм го срещал.

Memory: 10.20 MB
Time: 0.390 s

09/10/2016 11:51:32

msmilkoff 338 Точки

Идва от System.Linq. Общо взето проектира всеки елемент от колекцията в нова форма. В случая го парсва към int, но може и ламбда изрази да му подаваш, примерно да добавя едно към всяко число - Select(n=> n +1). Ще го учите. Засега си го ползвай за парсване, освен ако не искаш да напредеш малко повече от колегите си и да им показваш "фокуси" с LINQ :)))

09/10/2016 11:57:31

Losko 69 Точки

Сега ако кажеш защо и с Метод работи малко-по бързо ... :)

09/10/2016 14:02:07

Покажи всички коментари

kaloyannikov 531 Точки

Lista(отдолу си стои масив) за да може да поддържа оразмеряване си има съответен trade off . Когато капацитета му се запълни се прави нов масив с двойно по-голяма дължина и всички елементи от стария масив се прехвърлят в новия , което може да си представиш при достатъчно много елементи не е бърза операция, макар и да се случва рядко. А обикновения масив си има фиксиран размер още при създаването му.

09/10/2016 11:41:42