What performance consideration (for sorting) are there in .NET regarding various List Types? Arrays? Other?

What performance consideration (for sorting) are there in .NET regarding various List Types? Arrays? Other?

What options are there when choosing a list type to use to hold large amounts of data? And what are the advantages of one of the other in a quick sort-time is required?

And, besides sorting, where would performance be a consideration?

curiouswebsterSoftware EngineerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Miguel OzSenior Software EngineerCommented:
It depends what you call "large" and what are you planning to do with the data.
For holding data that I just need to enumerate my preference is a generic list.
If I can group per a certain criteria or Search Key then my preference is to use a generic dictionary. Searching per key is a way faster than a List but it takes slightly longer to add/delete things to it, but most times we use data for reading then it becomes handy to have a dictionary. (The link also contains some performance comments)

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
kaufmed   ( ⚆ _ ⚆ )Commented:
For data structures there are always the following concerns:

    * Memory required/used
    * Write time
    * Read time

Different data structures will optimize each (or multiple) of these in different ways. For example, a list is easy to append to--just call the Add method. A dictionary is also easy to insert into--also call the Add method. But in order to read an item from a list, you either need to already know that item's index, or you have to search the list; in order to read an item from a dictionary, you simply need to know that item's key. Reading from a list is at worst O(n), where n is the size of the list. Reading from a dictionary is O(1), because every item's key is hashed, and when you pass the key in for searching, it is again hashed and that hashed value tells the dictionary exactly where the item is. It doesn't mater how many items are in the dictionary, it takes the same amount of time to hash any key.

As far as sorting, there are countless methods of sorting--each with its own pros and cons. (There's even a sort--an educational one, mind you, where you continually randomize the items, and after each randomization you check if the result is sorted. It's an absurd sort only used when discussing big-O notation.) Sorts also optimize in terms of memory and speed. Some sorts are fast, but require additional memory to complete the sort; some sorts maintain the relative order of identical items, others don't (i.e. "stable sort"). Array.Sort and List.Sort use a combination of algorithms--heapsort for smaller lists, and quicksort algorithm for larger lists.

On a different note, implementing a sorting algorithm (other than those already implemented by the Framework) isn't usually a thing. Common wisdom is to worry about performance when its time to worry about performance. You don't want to spend three weeks implementing a fancy sorting algorithm only to save 86 milliseconds (I mean, unless you're writing a real-time system where milliseconds count).
curiouswebsterSoftware EngineerAuthor Commented:
curiouswebsterSoftware EngineerAuthor Commented:
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
.NET Programming

From novice to tech pro — start learning today.