CODEWITHSUNDEEP
c#performance
Daniel
Daniel

Reputation: 11064

Best data type for list of <ID, object>?

What's the best data type performance-wise for a list of tuples composed of <ID, object>, such that the IDs are not unique?

For example:

1 tire
1 rim
1 spoke
2 buckle
2 flap
2 bag

What would give the best performance when selecting for ID = 1? I have over a million rows.

Upvotes: 2

Views: 1449

Answers (3)

paparazzo
paparazzo

Reputation: 45106

See the answer from Glorfindel
Contains and Lookup by Key is O(1) (or near) so this is going to be the best speed 

private Dictionary<int, List<object>> dl = new Dictionary<int, List<object>>();
private void AddDL(Int id, Object obj)
{
    if(dl.ContainsKey(id))
       dl[id].Add(obj);
    else 
       dl.Add(id, new List<Object>{obj});
}

Since Int has no hash collisions I think lookup will be 0(1) 

List<Object> myObjs = dl[id];

If you create with an initial capacity > count then even dl.Add is O(1)
So if you have over 1 million unique ID then 

private Dictionary<int, List<object>> dl = new Dictionary<int, List<object>>(1000000);

Same thing with List so may want to start with a capacity.

Upvotes: 1

Glorfindel
Glorfindel

Reputation: 22661

I'd go for Dictionary<int, List<object>>, this guarantees a fast lookup when selecting by ID. Dictionary keys have to be unique, but the List allows you to put more than one object under the same key.

Upvotes: 2

AngularRat
AngularRat

Reputation: 612

You could do something like:

        List<KeyValuePair<int, string>> stuff = new List<KeyValuePair<int, string>>();

        // Populate list with some stuff
        stuff.Add(new KeyValuePair<int, string>(1, "Asdf"));
        stuff.Add(new KeyValuePair<int, string>(1, "wqer"));
        stuff.Add(new KeyValuePair<int, string>(2, "fghj"));
        stuff.Add(new KeyValuePair<int, string>(3, "vnbm"));
        stuff.Add(new KeyValuePair<int, string>(1, "Asdf"));

        // Use linq to get items with certain key
        var results = stuff.Where(x => x.Key == 1).ToList();

I can't guarantee that's the fastest possible way...you could use a sorted list and possibly save a little processor time combing through results. But for most applications, this will work fine because the List and other container classes are relatively efficient.

Upvotes: 0

Related Questions