3
\$\begingroup\$

Suppose I have data coming from different sources that tells me information about a large group of stores that has the following (just an example):

Necessary to define what store we're dealing with:

  • Store_Name (String)
  • Location (String)

Store characteristics:

  • Square_Feet (Double)
  • No_Employees (Double)
  • Years_Open (Double)
  • ... (Whatever else)

And the structure of the program I'm working with is such that we will always get the first 2 (defining) characteristics and one or more of the store-specific characteristics. My goal is to conglomerate all the characteristics for each of the specific stores together.

To do this, I have created the following class:

Public Class StoreChars
    Public Property Square_Feet as Double = 0
    Public Property No_Employees as Double = 0
    Public Property Years_Open as Double = 0
    ...
End Class

And then, in my program, I have created the following:

Dim StoreData As New Dictionary(Of Tuple(Of String, String), StoreChars)

The key being the Store_Name and Location as the defining tuple.

So, now, in my code, supposing I just got some data together with the defining characteristics for a set of stores (might be some, might be all... we don't know if we've seen these before or not even), my loop to put in that data looks as follows:

For Each PieceOfInfo in ReturnedData
   Dim TupleKey As New Tuple(Of String, String)(PieceOfInfo.Store_Name,
                                                PieceOfInfo.Location)

   If Not StoreData.ContainsKey(TupleKey) Then
        StoreData.Add(TupleKey, New StoreChars With 
                                {
                                 .Square_Feet = PieceOfInfo.Square_Feet
                                     ... (whatever else we got) ...
                                })
   Else
        StoreData(TupleKey).Square_Feet = PieceOfInfo.Square_Feet
                     ... (whatever else we got) ...
   End If
Next

But this seems to be very slow and I'm wondering if it isn't overly-processor-intensive to create a tuple in each loop, check the existence as a key, etc, but I can't think of a better way to do this.

The other solution I was thinking of was to create a Dictionary(Of String, Dictionary(Of String, StoreChars)). That would eliminate having to create a Tuple with each loop, but it would mean having to check existence of the keys in 2 separate dictionaries.

If there is a better way to do this, I would LOVE to hear what it is because I find myself having to program solutions like this fairly often!

Also, even though I wrote this code in VB, I'm just as comfortable with a C# solution - I'm just currently working in a VB environment.

\$\endgroup\$
13
  • 1
    \$\begingroup\$ One suggestion I can make is rather than calling StoreData.ContainsKey you could call StoreData.TryGetValue. This way you don't have to do a 2nd lookup in your Else block. \$\endgroup\$
    – Jeff
    Dec 18, 2013 at 14:40
  • 1
    \$\begingroup\$ You should use a smaller unique identifier for each store instead of the combination of the store name and location. Besides, is it not possible to have two stores in one location? I know of a place with a Dunkin Donuts, "Subway", and a convenience store/gas station/car wash. Single address. \$\endgroup\$ Dec 18, 2013 at 14:47
  • 1
    \$\begingroup\$ I would include Name and Location in StoreChars, override GetHashCode and Equals, and use a HashSet for the collection. Or use a KeyedCollection with an indexer for the composite key. \$\endgroup\$
    – Blam
    Dec 18, 2013 at 14:55
  • 1
    \$\begingroup\$ This link is really close (see my answer) but the key is composite Int rather than string. I use this in production and it is fast. But it does use a bit of memory as under the covers a KeyCollection seems to use two indexes. stackoverflow.com/questions/9328852/… \$\endgroup\$
    – Blam
    Dec 18, 2013 at 15:21
  • 1
    \$\begingroup\$ Why would you ever declare number of employees a double? \$\endgroup\$
    – svick
    Dec 18, 2013 at 17:37

5 Answers 5

2
\$\begingroup\$

Turns out I had a String, String KeyedCollection in my archive

using System.Collections.ObjectModel;

namespace KeyCollStringString
{
    class Program
    {
        static void Main(string[] args)
        {
            StringStringO ss1 = new StringStringO("Sall","John");
            StringStringO ss2 = new StringStringO("Sall", "John");
            if (ss1 == ss2) Console.WriteLine("same");
            if (ss1.Equals(ss2)) Console.WriteLine("equals");
            // that are equal but not the same I don't override = so I have both features

            StringStringCollection stringStringCollection = new StringStringCollection();
            // dont't have to repeat the key like Dictionary
            stringStringCollection.Add(new StringStringO("Ringo", "Paul"));
            stringStringCollection.Add(new StringStringO("Mary", "Paul"));
            stringStringCollection.Add(ss1);
            //this would thow a duplicate key error
            //stringStringCollection.Add(ss2);
            //this would thow a duplicate key error
            //stringStringCollection.Add(new StringStringO("Ringo", "Paul"));
            Console.WriteLine("count");
            Console.WriteLine(stringStringCollection.Count.ToString());
            // reference by ordinal postion (note the is not the long key)
            Console.WriteLine("oridinal");
            Console.WriteLine(stringStringCollection[0].GetHashCode().ToString());
            // reference by index
            Console.WriteLine("index");
            Console.WriteLine(stringStringCollection["Mary", "Paul"].GetHashCode().ToString());
            Console.WriteLine("foreach");
            foreach (StringStringO ssO in stringStringCollection)
            {
                Console.WriteLine(string.Format("HashCode {0} String1 {1} String2 {2} ", ssO.GetHashCode(), ssO.String1, ssO.String2));
            }
            Console.WriteLine("sorted by date");
            foreach (StringStringO ssO in stringStringCollection.OrderBy(x => x.String1).ThenBy(x => x.String2))
            {
                Console.WriteLine(string.Format("HashCode {0} String1 {1} String2 {2} ", ssO.GetHashCode(), ssO.String1, ssO.String2));
            }
            Console.ReadLine();
        }
        public class StringStringCollection : KeyedCollection<StringStringS, StringStringO>
        {
            // This parameterless constructor calls the base class constructor 
            // that specifies a dictionary threshold of 0, so that the internal 
            // dictionary is created as soon as an item is added to the  
            // collection. 
            // 
            public StringStringCollection() : base(null, 0) { }

            // This is the only method that absolutely must be overridden, 
            // because without it the KeyedCollection cannot extract the 
            // keys from the items.  
            // 
            protected override StringStringS GetKeyForItem(StringStringO item)
            {
                // In this example, the key is the part number. 
                return item.StringStringS;
            }

            //  indexer 
            public StringStringO this[string String1, string String2]
            {
                get { return this[new StringStringS(String1, String2)]; }
            }
        }

        public struct StringStringS
        {   // required as KeyCollection Key must be a single item
            // but you don't reaaly need to interact with Int32Int32s
            public readonly String String1, String2;
            public StringStringS(string string1, string string2) { this.String1 = string1.Trim(); this.String2 = string2.Trim(); }
        }
        public class StringStringO : Object
        {
            // implement you properties
            public StringStringS StringStringS { get; private set; }
            public String String1 { get { return StringStringS.String1; } }
            public String String2 { get { return StringStringS.String2; } }
            public override bool Equals(Object obj)
            {
                //Check for null and compare run-time types.
                if (obj == null || !(obj is StringStringO)) return false;
                StringStringO item = (StringStringO)obj;
                return (this.String1 == item.String1 && this.String2 == item.String2);
            }
            public override int GetHashCode() 
            {
                int hash = 17;
                // Suitable nullity checks etc, of course :)
                hash = hash * 23 + String1.GetHashCode();
                hash = hash * 31 + String2.GetHashCode();
                return hash;
            }
            public StringStringO(string string1, string string2)
            {
                StringStringS stringStringS = new StringStringS(string1, string2);
                this.StringStringS = stringStringS;
            }
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Blam, I truly loved your solution, but I have to admit it was just above my head... I'm going through the code now and still trying to wrap my head around it... I ended up going with tinstaafl's solution since it seemed to be the easiest solution that actually made sense to me... I am intent to learn your method, though, because it seems to be great programming practice. THANK YOU FOR YOUR HELP AND GUIDANCE!!! \$\endgroup\$ Dec 18, 2013 at 19:20
  • \$\begingroup\$ Given @svick's comment to Blam's solution, your answer seems to be the best, most concise... Albeit slightly over my head... But that I shall remedy!! THANK YOU!!! \$\endgroup\$ Dec 19, 2013 at 14:56
  • 2
    \$\begingroup\$ Could you provide an explanation of your solution, and not just the code? \$\endgroup\$ Feb 25, 2016 at 20:00
5
\$\begingroup\$

If you're stuck with Tuple<T1,T2> as a key, you want to provide an IEqualityComparer<Tuple<T1,T2>> implementation in the constructor of your dictionary.

If you can change the TKey type, you might want to provide a custom class that implements IEquatable<T>.

The problem with the current code is that comparison between keys of type Tuple<string, string> is not efficient.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks, Ken, I'm not in any way stuck with the Tuple, though. It's just what I thought would be the best solution. As for your suggestions, could you maybe help point me in the right direction for what you would consider being the best / most efficient solution (I'm guessing that would be the custom class implementing IEquatable - That is BRAND NEW to me... I'm not even sure how I'd use that) \$\endgroup\$ Dec 18, 2013 at 14:59
  • 1
    \$\begingroup\$ Why do you say that comparing Tuples with the default comparer is not efficient? \$\endgroup\$
    – svick
    Dec 18, 2013 at 17:44
  • \$\begingroup\$ @svick see stackoverflow.com/questions/21084412/… \$\endgroup\$
    – nawfal
    May 19, 2014 at 13:13
4
\$\begingroup\$

I take it you are mostly concerned with efficiency in this question (because your code already works).

Instead of using the built-in Tuple (which is a reference type), create a custom struct or struct-based Tuple so that you save on heap allocations. Allocating and GC'ing a new heap object per lookup is indeed expensive.

Be sure to override the equality members.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you so much for the reply, usr. Unfortunately, this is BRAND NEW territory for me... Do you know of any suggestions / resources that could help point me in the right direction to do that? \$\endgroup\$ Dec 18, 2013 at 15:00
  • 1
    \$\begingroup\$ @JohnBustos maybe you should start by looking at the difference between class and struct (google.com/…). They are conceptually similar. It is not that hard to create a custom tuple. It is even easier to create a specialized struct: struct Key { string Store_Name; string Location; } (this is a sketch). If you've got any specific problems just post another comment. \$\endgroup\$
    – usr
    Dec 18, 2013 at 15:11
  • \$\begingroup\$ Thanks SO MUCH, creating the custom key struct does makes sense - And you're saying that creating a struct the same way I am now creating a tuple will save on memory allocation... That makes sense too!! - The part that kind of still catches me is "overriding the equality members"... How / where would I do that? Also, if you were programming a solution to a situation such as mine, would you do it this way or would you do something completely different (like maybe one of the other solutions posted)? \$\endgroup\$ Dec 18, 2013 at 15:42
  • 2
    \$\begingroup\$ I would do it this way and I have done it this way. Override GetHashCode and make the struct implement IEquatable<MyStruct>. That way the dictionary will call your code to determine equality. \$\endgroup\$
    – usr
    Dec 18, 2013 at 15:44
0
\$\begingroup\$

Another way to do this, is to add the store name and location to the StoreChars class and override the gethashcode function. You can combine the store name and location and create a hashcode to use as the key and the storechars object as the value:

Public Class StoreChars
    Public Property Store_Name As String = ""
    Public Property Location As String = ""
    Public Property Square_Feet As Double = 0
    Public Property No_Employees As Double = 0
    Public Property Years_Open As Double = 0
    Public Overrides Function GetHashCode() As Integer
        Return (Store_Name & Location).GetHashCode
    End Function
End Class

Use it something like this:

Dim StoreData As Dictionary(Of Integer, StoreChars)
For Each PieceOfInfo In ReturnedData
    Dim TempChars As New StoreChars With
        {
            .Store_Name = PieceOfInfo.Store_Name,
            .Location = PieceOfInfo.Location,
            .Square_Feet = PieceOfInfo.Square_Feet,
            .No_Employees = PieceOfInfo.No_Employees,
            .Years_Open = PieceOfInfo.Years_Open
        }
    'If using the hashcode is bothersome you could use 
    'Dim tempkey As String = PieceOfInfo.Store_Name & PieceOfInfo.Location
    Dim tempkey As Integer = TempChars.GetHashCode
    If StoreData.ContainsKey(tempkey) Then
        StoreData(tempkey) = TempChars
    Else
        StoreData.Add(tempkey, TempChars)
    End If
Next

This assumes the properties in pieceofinfo will have have at least a default value and not be nothing.

Creating a new storechars is mainly for readability and maintenance, You could optimize it by creating the hashcode separately from the store name and location strings then adding the other data separately. Since the hashcode is an integer it would probably be more efficient to store it than a tuple.

Here's a revision without the extra object:

For Each PieceOfInfo In ReturnedData
    'If using the hashcode is bothersome you could use 
    'Dim tempkey As String = PieceOfInfo.Store_Name & PieceOfInfo.Location
    Dim tempkey As Integer = (PieceOfInfo.Store_Name & PieceOfInfo.Location).GetHashCode
    If StoreData.ContainsKey(tempkey) Then
        Using StoreData(tempkey)

            .Store_Name = PieceOfInfo.Store_Name
            .Location = PieceOfInfo.Location
            .Square_Feet = PieceOfInfo.Square_eet
            .No_Employees = PieceOfInfo.No_Employees
            .Years_Open = PieceOfInfo.Years_Open
        End Using
    Else
        StoreData.Add(tempkey, New StoreChars With
        {
            .Store_Name = PieceOfInfo.Store_Name,
            .Location = PieceOfInfo.Location,
            .Square_Feet = PieceOfInfo.Square_Feet,
            .No_Employees = PieceOfInfo.No_Employees,
            .Years_Open = PieceOfInfo.Years_Open
        })
    End If
Next
\$\endgroup\$
8
  • \$\begingroup\$ Would this be more efficient? Because, in effect, you're creating a new StoreChars with each loop (even if one already exists) then running the GetHashCode on it to see if it already exists whereas with the original code, you're only creating a tuple... \$\endgroup\$ Dec 18, 2013 at 19:01
  • \$\begingroup\$ I think I'm catching on and this seems to be making the most amount of sense to me... So, if I understand correctly, you would, in your loop, do something like tempkey = (PieceOfInfo.Store_Name & PieceOfInfo.Location).GetHashCode then there wouldn't be a need to create the new object unless needed? ... that really does sound pretty genius to me if it works that way in real life - No tuples, no implementing IEquatable, none of that scary stuff!! :) \$\endgroup\$ Dec 18, 2013 at 19:14
  • 1
    \$\begingroup\$ Doing it like this is a very bad idea, because GetHashCode is not guaranteed to be unique. \$\endgroup\$
    – svick
    Dec 19, 2013 at 14:18
  • \$\begingroup\$ Darn it, @svick... I just read more into it and that makes sense too... Sorry, tinstaafl... I thought this was the best solution, but it turns out not.... \$\endgroup\$ Dec 19, 2013 at 14:55
  • 1
    \$\begingroup\$ @tinstaafl No, it won't. There are only 2^32 ints, but there are infintely many strings. So, there is a chance (though probably quite small) that two different strings will have the same hash code. \$\endgroup\$
    – svick
    Dec 19, 2013 at 16:04
-2
\$\begingroup\$

You may like to create a Store class that holds all the properties of the store as

  • We are not using the key components individually.
  • Also, every class needs to have one purpose.

Then, we can create the dictionary as below

  • Dictionary(Of String, Store)
  • Key = StoreName & Location

Also, you may simply use Pascal case in variables, using underscore to seperate words is an old convention.

Using concatenated string (StoreName & Location) as the key doesn't seem to be very elegant but it is a simple solution and we don't need to override the GetHashCode method in our class as well.

\$\endgroup\$
5
  • \$\begingroup\$ Are you saying that the dictionary key should be a concatenation of the two strings? I think that's a bad advice. \$\endgroup\$
    – svick
    Dec 18, 2013 at 21:20
  • \$\begingroup\$ Can you please explain why? I understand that solution doesn't seem to be very elegant but it results in less code and is also very simple to implement. \$\endgroup\$ Dec 19, 2013 at 13:04
  • \$\begingroup\$ The main problem I have with that is that if everything is a string, then you have almost no type checking, so it's very easy to make a mistake by using the wrong string. Using Tuple would be somewhat better and a custom type would be best. \$\endgroup\$
    – svick
    Dec 19, 2013 at 13:37
  • \$\begingroup\$ I think this is not relevant at all. Yes, generally speaking we should not use strings in code as typo may result in bugs that are hard to find but neither are we embedding any strings here nor are we changing any string values here. Whether you use two string variables or single variable, it doesn't make is more error prone. \$\endgroup\$ Dec 19, 2013 at 15:01
  • \$\begingroup\$ Also, if you don't have any proper answer that explains why solution is bad, please undo the negative voting that you have done. \$\endgroup\$ Dec 19, 2013 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.