[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

High performance sorted list in C# (200,000+ items)

Posted on 2004-11-06
3
Medium Priority
?
1,419 Views
Last Modified: 2008-01-09
I am writing a charting application that receives real time updates - financial quotes to be specific. I need to keep track of every quote that comes in and in the order it occurred.  I get these quotes out of order, and I have to put them in order.  I have used a SortedList, but found it is WAY too slow.  What is the absolute fastest way I could keep track of these items and keep them sorted?  The SortedList hangs up the application while it is managing incoming data - should I implement something that uses multithreading to perform the sorting?

Thanks,

Eric
0
Comment
Question by:ericdotnet
3 Comments
 
LVL 3

Accepted Solution

by:
djwillms earned 2000 total points
ID: 12518704
Solution #1 - (Id really recommend do this one since its the easiest)
Dont dismiss a relation database such as MS SQL Server. MS SQL Server has the concept of RAM only based temporary tables.
Just create a table with a time stamp column, and index the timestamp column. Then, select * from table order by timestamp. This way there will be almost zero cost related to sorting the list of information.  You will also find that you can do a few thousand inserts per second into the relational database, even WITH the indexed column, hopefully this is fast enough. Also, consider installing MSDE or sql server on the machine that receives the data so that there is no network bandwidth latency. Here is an example of a memory (ram) temporary table :

DECLARE @OrderCounts TABLE(ProductID int, OrderCount int)

INSERT INTO @OrderCounts
SELECT ProductID, COUNT(DISTINCT OrderID)
FROM [Order Details]
GROUP BY ProductID
ORDER BY COUNT(DISTINCT OrderID) DESC

SELECT COUNT(ProductID), OrderCount
FROM @OrderCounts
GROUP BY OrderCount
ORDER BY OrderCount DESC

Solution #2
I would use an unsorted collection, or array for capturing the data as it comes in, and then at the exact moment you need it, sort the list into a new collection/array (using the quicksort algorithm) and then use the new sorted array /collection. Using this method you wont have any overhead in capturing the data.  And you will only have to sort the data the most minimal number of times.

Solution #3
*Gulp* Get ready for a huge programming / debugging session.
To get the highest performance out of your application and minimize the cost of inserting data, and minimize the cost of retrieving sorted information, I would recommend creating a new class that inherits from system.collections and make it use a self balancing binary tree algorithm for storing data internally.


Also note this statment from microsoft visual studio help:
"Enumerating through a collection is intrinsically not a thread-safe procedure. Even when a collection is synchronized, other threads could still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection during the entire enumeration or catch the exceptions resulting from changes made by other threads."
Based on that I wouldnt try to use a collection if you *must* make it multi-threaded to get more performance.


Also, note that relational database indexes are a dirivative of Self balancing binary trees. I believe they are Self balancing compressed hashing N-Trees algorithms.
0
 

Author Comment

by:ericdotnet
ID: 12589164
djwillms, Thank you!  That was alot of very useful information, I very much appreciate it.

Thanks!

Eric
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
Introduction to Processes
Loops Section Overview

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question