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

Posted on 2004-11-06
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?


Question by:ericdotnet
    LVL 6

    Expert Comment

    LVL 3

    Accepted Solution

    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
    FROM [Order Details]
    GROUP BY ProductID

    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.

    Author Comment

    djwillms, Thank you!  That was alot of very useful information, I very much appreciate it.



    Featured Post

    How to improve team productivity

    Quip adds documents, spreadsheets, and tasklists to your Slack experience
    - Elevate ideas to Quip docs
    - Share Quip docs in Slack
    - Get notified of changes to your docs
    - Available on iOS/Android/Desktop/Web
    - Online/Offline

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    fizzArray3  challenge 1 48
    withoutTen challenge 14 69
    Fix45 challenge 15 67
    java  and programming certification ? 4 35
    This is about my first experience with programming Arduino.
    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.
    An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
    Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

    745 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

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now