CODEWITHSUNDEEP
c#collectionsperformance
Kamil Dhuleshia
Kamil Dhuleshia

Reputation: 347

Fastest and most efficient collection type in C#

I am building an application which will require a collection to hold about 10k of Strings.

Collection will be used as queue.

So was looking through different collection types in C# but could not figure out which one has best performance in regards to speed of doing Put and Get operation in Queue. Also should be capable of not allowing duplicates in the Queue/Collection.

EDIT based on the comments..

Any existing collection will be helpful. Or a custom collection which could out perform any existing collection will be great.

Thanks

Upvotes: 16

Views: 39103

Answers (3)

ChrisWue
ChrisWue

Reputation: 19070

There is the OrderedDictionary class which keeps the insertion order but allows you to look up values by key.

Upvotes: 9

Kasper Holdum
Kasper Holdum

Reputation: 13373

Do you mind spending O(2n) memory? You could use a Queue<> in combination with a Dictionary<,>. The queue would handle the queue and dequeue operations and the dictionary would ensure unique entries. A simple wrapper class could combine those two, and it would give you O(log n) queue and dequeue times.

Example:

public class SetQueue<T>
{
    private readonly Dictionary<T, bool> duplicates = new Dictionary<T, bool>();
    private readonly Queue<T> queue = new Queue<T>();

    public bool Enqueue(T item)
    {
        if (!duplicates.ContainsKey(item))
        {
            duplicates[item] = true;

            queue.Enqueue(item);

            return true;
        }

        return false;
    }

    public T Dequeue()
    {
        if (queue.Count >0)
        {
            var item = queue.Dequeue();
            if (!duplicates.ContainsKey(item))
                throw new InvalidOperationException("The dictionary should have contained an item");
            else
                duplicates.Remove(item);

            return item;
        }

        throw new InvalidOperationException("Can't dequeue on an empty queue.");
    }
}

An insert into this custom data structure check if the dictionary already contains the item. This operation uses the ContainsKey method which is a O(log n) operation. If the item was already contained in the data structure than the method exits. If the item isn't contained, then the item will be inserted into the queue which is a constant O(1) operation. It will also be added to the dictionary. When the count of the dictionary is less than the capacity this will approach a constant, O(1) insertion time as well. The total queue time will therefore be O(log n).

The same thing goes the dequeuing method.

This solution is basically the same as the built-in data structure OrderedDictionary, however, since this solution uses generic there is no overhead in boxing/unboxing in it's operations making it wastely faster.

Upvotes: 8

Sanjeevakumar Hiremath
Sanjeevakumar Hiremath

Reputation: 11273

If you are looking for High performance Put & Get while checking for uniqueness (duplicate checking) but order doesnt matter (not a queue) then use HashSet<T>

If Queue feature is more important then use a Queue<T>

I dont think there is anything which offer both.

Upvotes: 20

Related Questions