[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

How-to find Dictionary items by partial key matching?

Posted on 2007-10-04
8
Medium Priority
?
5,414 Views
Last Modified: 2008-01-09
I am developing an application which operates with items of some sort (assume that each Item is represented by class MyItem). Now i have to add to my app the following functionality: the ability to find item by keyword(s). I have made conclusion to implement internally such functionality by using multi keyed dictionary where value of each dictionary item is MyItem class. when using great C5 collections library this looks like
C5.HashDictionary<C5.HashBag<string>, MyItem>
I can rapidly find item by specifying the exact bag of item's keywords. But the problem is that i don't know how-to find all items in dictionary by specifying non-exact ba of keywords. For example if item's bag of keys is "key1, key2" i want to find it by specifying only "key1". Is this possible?
0
Comment
Question by:latsubs
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 21

Expert Comment

by:surajguptha
ID: 20018066
Iterate through all the items in the dictionary and find all keys that contains the partial key using string.Contains() function
0
 
LVL 22

Assisted Solution

by:JimBrandley
JimBrandley earned 300 total points
ID: 20018151
According to the documentation, you can do that by creating your own IEqualityComparer, but you will need to do it carefully.

1. You need to select a wildcard indicator that is a character or string that CANNOT appear in a candidate key.

2. You need to consider that it will stop searching as soon as the first match is found. So, if you have two keys:
"key1, key2"
"key1, key3"

and you search for: "key1*" (assuming the asterisk is your chosen wildcard), it will never locate the item with "key1, key3".

Jim
0
 

Author Comment

by:latsubs
ID: 20018424
now i'm starting to think that it wasn't brigth idea to implement searching using multikeyed dictionary. i'm considering switching to generic List and implementing keyword also as generic string List in MyItem class. then i can easily get needed items by using anonymous delegate:

private class Item
        {
            public Item()
            {
                keys = new System.Collections.Generic.List<string>();
                name = String.Empty;
            }

            public Item(string[] keys, string value) : this()
            {
                this.keys.AddRange(keys);
                this.name = value;
            }

            public System.Collections.Generic.List<string> keys;
            public string name;
        }

private void Test()
        {
            System.Collections.Generic.List<string> keysToSearch = new System.Collections.Generic.List<string>();
            keysToSearch.Add("key1");
            keysToSearch.Add("key3");

            System.Collections.Generic.List<Item> items = new System.Collections.Generic.List<Item>();
            items.Add(new Item(new string[] { "key1", "key2" }, "item1"));
            items.Add(new Item(new string[] { "key1", "key3" }, "item2"));
            items.Add(new Item(new string[] { "key2", "key3" }, "item3"));

            System.Collections.Generic.List<Item> foundItems = items.FindAll(delegate(Item item)
            {
                bool contains = false;

                foreach (string keyToSearch in keysToSearch)
                {
                    contains = item.keys.Contains(keyToSearch);

                    if (!contains)
                    {
                        return false;
                    }
                }

                return contains;
            });

            foreach (Item foundItem in foundItems)
            {
                System.Diagnostics.Trace.WriteLine(foundItem.name);
            }
        }

the next thing to implement would be hashing.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 37

Accepted Solution

by:
gregoryyoung earned 1200 total points
ID: 20018644
I don't think that will work with a HashBag Brandley ... I think he would want to move to an ISortedDictionary

while using a different equality comparer is interesting it will only work if they hash the same.

In general one should be using a hash for exact matches and a tree type structure (such as TreeDictionary in c5 or a skip list) if you want to do partial match searches. The reason for this is that the partial search on a hash table is O(n)

Note the key is the move to the TreeDictionary ....

IEnumerable<T> Filter(Fun<T,bool> predicate) could work great for you but unfortunately it will also be O(n) ... If you aren't searching off of your key this would make ALOT of sense. Since you are going off of your key I am afraid I don't see support in their tree dictionary (although it would be pretty easy to add).


0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 20018656
If your above code is ok for you performance wise (O(n)) then just use IEnumerable<T> Filter(Fun<T,bool> predicate) defined on DictionaryBase in c5 to do the same thing with a predicate
0
 
LVL 22

Expert Comment

by:JimBrandley
ID: 20018863
Thanks Greg.

Jim
0
 

Author Comment

by:latsubs
ID: 20020028
currently the performance is ok. i have made test with 150k items - searches are made instantly.
but if i need more performance in future what should i do?
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 20020141
use a custom (or modify their binary tree o support, ah the wonder of open source) ...

When doing a non-kyed or predicate search (i.e. I have no idea) I am forced to do a linear walk (all items in a hash table or all items in a tree) ...

If however my field being searched is in the form XXX* and its my KEY I can use a binary tree to find the root (if any) that partially matches XXX  nodes below this node will match XXX*. I can find this node as a binary search O(log n) and can search nodes below ...

If you want I can go through a partial match seach (or probably write you a method for the sorteddictionary very quickly) but its pretty straight forward to implement ... consider the following tree (in ascii notation)

mom
   dad
         cat
              aardvark
              bob
         dog
   pink
         open
         young


if we search for d*... we visit mom, then left->dad which meets d* ... all d* nodes will be under dad. This is true at any level and with *lots* of nodes can save us alot of time (lots: read millions+ or a slow processor :))

Cheers,

Greg
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
This article shows how to deploy dynamic backgrounds to computers depending on the aspect ratio of display
This video shows how to quickly and easily deploy an email signature for all users in Office 365 and prevent it from being added to replies and forwards. (the resulting signature is applied on the server level in Exchange Online) The email signat…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses
Course of the Month20 days, 2 hours left to enroll

873 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question