CODEWITHSUNDEEP
c#
Oleg Vazhnev
Oleg Vazhnev

Reputation: 24057

am I using Dictionary wrong, it seems it too slow

I've used VS profilier and noticed that ~40% of the time program spends in the lines below. I'm using title1 and color1 because either Visual Studio or Resharper suggested to do so. Are there any perfomance issues in the code below?

Dictionary<Item, int> price_cache = new Dictionary<Item, int>();
....


string title1 = title;
string color1 = color;
if (price_cache.Keys.Any(item => item.Title == title && item.Color == color))
{
    price = price_cache[price_cache.Keys.First(item => item.Title == title11  && item.Color == color1)];

Upvotes: 2

Views: 3937

Answers (5)

vgru
vgru

Reputation: 51204

The problem is that your Keys.Any method iterates through all keys in your dictionary to find if there is a match. After that, you use the First method to do the same thing again.

Dictionary is suited for operations when you already have the key and want to get the value fast. In that case, it will calculate the hash code of your key (Item, in your case) and use it to "jump" to the bucket where your item is stored.

First, you need to make your custom comparer to let the Dictionary know how to compare items.

class TitleColorEqualityComparer : IEqualityComparer<Item>
{
     public bool Equals(Item a, Item b) 
     {
          // you might also check for nulls here
          return a.Title == b.Title && 
              a.Color == b.Color;
     }

     public int GetHashCode(Item obj)
     {
          // this should be as much unique as possible,
          // but not too complicated to calculate
          int hash = 17;
          hash = hash * 31 + obj.Title.GetHashCode();
          hash = hash * 31 + obj.Color.GetHashCode();
          return hash;
     }
}

Then, instantiate your dictionary using your custom comparer:

Dictionary<Item, int> price_cache = 
    new Dictionary<Item, int>(new TitleColorEqualityComparer());

From this point on, you can simply write:

Item some_item = GetSomeItem();
price_cache[some_item] = 5; // to quickly set or change a value

or, to search the dictionary:

Item item = GetSomeItem();
int price = 0;
if (price_cache.TryGetValue(item, out price))
{
    // we got the price
}
else
{
    // there is no such key in the dictionary
}

[Edit]

And to emphasize again: never iterate the Keys property to look for a key. If you do that, you don't need a Dictionary at all, you can simply use a list and get same (even slightly better performance).

Upvotes: 9

Peter
Peter

Reputation: 27934

If you want fast access to your hashtable, you need to implement the GetHashCode and Equals functioning:

public class Item 
{
.....
    public override int GetHashCode()
    {
        return (this.color.GetHashCode() + this.title.GetHashCode())/2;
    }

    public override bool Equals(object o)
    {
        if (this == o) return true;
        var item = o as Item;
        return (item != null) && (item.color == color) &&  (item.title== title) ;
    }

Access you dictionary like:

Item item = ...// create sample item
int price = 0;

price_cache.ContainsKey(item);
price_cache[item];
price_cache.TryGetValue(item, out price);

Upvotes: 1

Fabian Nicollier
Fabian Nicollier

Reputation: 2861

Replace your price_cache.Keys.Any() with price_cache.Keys.SingleOrDefault() and this way you can store the result in a variable, check for nullity and if not you already have the searched item instead of searching for it twice like you do here.

Upvotes: 1

Jess
Jess

Reputation: 8700

As Jesus Ramos suggested (when he said use a different data structure), you could make the key a string that is a concatenation of the title and color, then concatenate the search string and look for that. It should be faster.

So a key could look like name1:FFFFFF (the name, a colon, then the hex of the color), then you would just format the search string the same way.

Upvotes: 1

lmz
lmz

Reputation: 1580

Try using an IEqualityComparer as shown in the sample code on this page: http://msdn.microsoft.com/en-us/library/ms132151.aspx and make it calculate the hash code based on the title and color.

Upvotes: 1

Related Questions