2

Basically I have a Dictionary<Guid, Movie> Movies collection and search for movies using Guid, which is basically movie.Guid. It works great, but I also want to be able to search the same dictionary using movie.Name without looping through each element.

Is this possible or do I have to create another Dictionary<K, V> for this?

Joan Venge
  • 315,713
  • 212
  • 479
  • 689
  • Do you expect searching on other fields in the future? – Larsenal Oct 14 '11 at 20:57
  • If you're filling the dictionary from a database, you're much better of filtering in your database query. – jrummell Oct 14 '11 at 20:59
  • @Larsenal, no but who knows if something comes up but unlikely. – Joan Venge Oct 14 '11 at 21:03
  • @jrummell: I use an xml file that has all the serialized data that I deserialize at startup. – Joan Venge Oct 14 '11 at 21:04
  • 1
    Are you going to be doing *exact* name matching, or do you expect to be able to search for partial name matches? It seems unlikely that anyone is going to search on "Terminator 3: The Rise Of The Machines". Also, why use a GUID as a unique identifier as opposed to a Universal Product Code, or other standard identifier used specifically for media? – Eric Lippert Oct 14 '11 at 21:08
  • @Joan You may be best off having an internal database that you wipe-and-populate on load from your xml file. It may seem heavyweight, but it's pretty simple to set up (at least in Java, can't imagine it's hard to set up in C#). – corsiKa Oct 14 '11 at 21:09
  • 3
    Why do you care about performance in Mem. data? how much entry do you have? 100M? 1G? – L.B Oct 14 '11 at 21:11
  • @Eric: Thanks, I will use exact name matching. This is so that I will have some file which is temporary where it contains a user's list of watched movies and when they watched it. I am gonna parse this file but the only way AFAIK for me to transfer this file from that state with references to my own `Movie` values is to get the movie by exact name. But for users in the actual app, they will be able to search by inexact name and it will find all that partially matches. As for Guid, that's what someone suggested in another question. Basically I described the problem here (cont) – Joan Venge Oct 14 '11 at 21:18
  • http://stackoverflow.com/questions/7732033/whats-the-best-way-to-save-movie-objects-inside-other-files-and-associate-them-w Is there a better way to store them? Also I don't have any UPC codes for the movies myself, and none I could find in the website that I parsed to make my own collection. – Joan Venge Oct 14 '11 at 21:19
  • @glowcoder: I am not sure what you mean a DB that I wipe and populate? You mean only create a `Dictionary` on app startup? – Joan Venge Oct 14 '11 at 21:20
  • @Joan I mean don't use the dictionary at all. Store the data in a database and query that instead of a dictionary. – corsiKa Oct 14 '11 at 21:21
  • @L.B: It's not much data but I was wishing to have symmetrical implementation if that makes sense, so was wondering about this. – Joan Venge Oct 14 '11 at 21:21
  • @glowcoder: OK I see what you mean, but that wouldn't give me O(1), right? – Joan Venge Oct 14 '11 at 21:21
  • I did a (probably bad) two-way mapping collection using a pair of dictionaries [here](http://stackoverflow.com/questions/5382299/retrieval-of-items-from-custom-collection/5382893#5382893), it might give you an idea *if* you decide to do that in light of critiques and considerations offered in comments. – Anthony Pegram Oct 14 '11 at 21:24
  • @Joan it very well could give you O(1). If you have proper indexing, you can get (what will seem to you) to be O(1) for complete matches, and still providing very good lookup times for parital matches (like searching for "Terminator" or "Police Academy" when the actual matches are different). Simply put, *databases were made for this* kind of activity. Why not leverage the experience they had trying to solve this problem? :-) – corsiKa Oct 14 '11 at 21:46
  • @Joan Venge, I hope your next question is not "How can I search some-text in title/summary". Since it may invalidate all of these discussions. – L.B Oct 14 '11 at 21:47
  • @glowcoder, you could I suppose. I am just not experienced with DBs. Although I heard that they have some files that provide DB like interaction, right? – Joan Venge Oct 14 '11 at 21:55
  • @L.B: lol no, I will just loop through each item for that. – Joan Venge Oct 14 '11 at 21:55
  • 1
    @Joan Kind of. Look for http://en.wikipedia.org/wiki/SQL_Server_Compact - it seems to (I'm not a C# guy, I'm a Java guy) have everything you're looking for in a lightweight database. – corsiKa Oct 14 '11 at 22:40
  • @glowcoder: Thanks man, I use linq a lot too so for me the source of the data is not that important as the syntax is the same, just except in some places. – Joan Venge Oct 14 '11 at 22:52

8 Answers8

3

Just have two Dictionaries, one of them having the guid as its key and the other with the name as its key.

MAK
  • 26,140
  • 11
  • 55
  • 86
1

If you don't want to look at every element, you need to index it the other direction. This means another Dictionary to get O(1).

Larsenal
  • 49,878
  • 43
  • 152
  • 220
  • Thanks, how do you mean by index it the other direction? – Joan Venge Oct 14 '11 at 21:04
  • In order to get the lookup in O(N), you need an "index" which in this case is done with a Dictionary. The phrase 'in the other direction' was a poor way to describe it. – Larsenal Oct 14 '11 at 21:10
1

You could search with the Values property:

dictionary.Values.Where(movie => movie.Name == "Some Name")

You'll lose the efficiency of a key based look up, but it will still work.

Aaron McIver
  • 24,527
  • 5
  • 59
  • 88
jrummell
  • 42,637
  • 17
  • 112
  • 171
1

You can't use that dictionary to do that search with anything like the same efficiency. But you can easily just run a LINQ query against your dictionary's Values property, which is just collection of the Movie values. 

var moviesIWant = From m in movieLookup.Values
                  Where m.Name == "Star Wars"
                  Select m

Some thoughts:

  • When you find your answer though, you would not have the guids, unless they were also a property of movie.
  • For a small dictionary, this is just fine. For large and repeated searches, you should consider the creation of other dictionaries keyed on the other values you wish to search on. Only in this way would you achieve the speed of a guid lookup comparable to your original dictionary.

You could create another dictionary keyed by Name. Once you've done this, you could search this dictionary by it's key and it would have the same super-efficiency of your original dictionary, even for a very large dictionary.

var moviesByName = movieLookup.Values.ToDictionary(m => m.Name, m => m)
Patrick Karcher
  • 22,995
  • 5
  • 52
  • 66
1

You can iterate across the variables but then you arnt getting the constant-time searching value in a dictionary (because of the way that the keys are hashed.) The answer above regarding using two dictionarys to hash references to your object may be a good solution if you dont have too many objects to reference.

jtm001
  • 371
  • 2
  • 3
1

Since dictionaries are for one-way mapping you can't get keys from values.

You'll need two dictionaries.

There is also a suggestion: You can use a custom hash function for keys instead of GUIDs and store Movie Names hash as keys. Then you can actually perform two way search in your dictionary.

fardjad
  • 20,031
  • 6
  • 53
  • 68
  • Thanks, that's an interesting idea. How would you implement a hash for strings? Use string.GetHashCode()? – Joan Venge Oct 14 '11 at 21:24
  • I would use Cryptography MD5 hash class and use `String.ToBase64()` and `Text.Encoding.GetBytes()` methods for byte <--> string convertions. – fardjad Oct 14 '11 at 21:27
  • Thanks, that seems cool. Would there be any performance overhead with using these? – Joan Venge Oct 14 '11 at 21:30
  • 1
    I don't think so, when you want to search for a key by name, you just need to calculate it's hash **one time** and find that hash in your dictionary. And for each item you want to add, you should calculate the movie name hash. – fardjad Oct 14 '11 at 21:33
1

Rather than using two dictionaries, you'd be much better off using one container class that has two dictionaries inside it.

Some guy named Jon came up with a partial solution to this (which you could easily build upon), leaving his code here: Getting key of value of a generic Dictionary?

Community
  • 1
  • 1
corsiKa
  • 81,495
  • 25
  • 153
  • 204
  • Thanks but this would only work by providing a `Guid` or `Movie` in my case right? Not `Guid` and `Name`, but very interesting idea. – Joan Venge Oct 14 '11 at 21:09
  • Ah I see. I thought you wanted to search either by `Guid` or `Movie`. Well in that case, not exactly, but I would still apply the same principle: use them inside a container class and encapsulate your logic there. – corsiKa Oct 14 '11 at 21:10
  • Thanks, that's an interesting idea I might implement but the `BiDictionary` is cool either way. – Joan Venge Oct 14 '11 at 21:22
0

No I don't believe it is possible. You'll have to use another dictionary.

If you are going to want to search on more movie attributes you may be better off moving the data down to a database and use that for querying. That is what databases are good for after all.

Kevin Holditch
  • 5,165
  • 3
  • 19
  • 35