A better way than O(n^2) for traversing a dictionary of dictionaries.

Question

I have a Dictionary of Dictionaries that I need to traverse to find two records with various matching parameters. I have two foreach loops to do this which is O(n^2). I am looking for inspiration to find a better way of doing this by using the keys to improve lookup.

Simple example below.

edit: Each record contains many values that I would want to try and match. Below I'm looking for a BUY and a SELL transaction in the records. I would also want to maybe match for the same customer and same location, which are keys in the record dictionary. It is possible that the Dictionary only has "BUY" Transaction values. The record dictionary also contains different value types, like double and int.

<"uniqueRecordIdABC", <"Transaction", "BUY">, <"Location", "Store1">, <"Client", "Bob">>
<"uniqueRecordIdDEF", <"Transaction", "SELL">, <"Location", "Store2">, <"Client", "Bob">>

What I've thought about doing is making the uniqueRecordKey something that I could parse, improving the lookup. IE: 1:BUY:Store1:Bob, 2:SELL:Store2:Bob, but I'm not sure if there is any real benefit to that either.

Example:

Dictionary<string, Dictionary<string, object>> records

foreach (var item in records)
{
    Dictionary<string, object> record = item.Value;   
    string transaction1 = Convert.ToString(record["Transaction"]);
    string name1 = Convert.ToString(record["Client"]);
    string location1 = Convert.ToString(record["Location"]);

    foreach (var item2 in records)
    {
        Dictionary<string, object> record2 = item2.Value;
        string transaction2 = Convert.ToString(record["Transaction"]);
        string name2 = Convert.ToString(record["Client"]);
        string location2 = Convert.ToString(record["Location"]);

        if ((transaction1 == "BUY" && transaction2 == "SELL" || transaction1 == "SELL" && transaction2 == "BUY") &&  name1 == name2 && location1 == location2)
        {
        }
    }
}

Can you explain more how you identify "opposite" records? Traversing values in a dictionary is always O(N) but there may be a better data structure you could use. It's also unclear what role the keys play (if any). — D Stanley
– D Stanley, Commented Nov 10, 2015 at 17:24
Your use case is not clear, as there's nothing in the if I can't tell, but for each entry being 'BUY', you'll always run all the entries being 'SELL'. — Tensibai
– Tensibai, Commented Nov 10, 2015 at 17:26
Iterating the keys to match a value? Seems like you have your dictionaries backwards! — Roman Reiner
– Roman Reiner, Commented Nov 10, 2015 at 17:27
With the information you've given us, this is inherently O(n^2), because if half of your values have "BUY" and half have "SELL", you want to execute the body of your if statement (n^2)/4 times. — Ben Aaronson
– Ben Aaronson, Commented Nov 10, 2015 at 17:47
If you create two Lists - one buy and one sell and sort them by Client, Location you can do this in one pass. — paparazzo
– paparazzo, Commented Nov 10, 2015 at 19:11

user40980 · Accepted Answer · 2015-11-10 19:20:11Z

{"id1": {"Transaction": "BUY",  "Location": "Store1", "Client": "Bob"}}
{"id2", {"Transaction": "SELL", "Location": "Store2", "Client": "Bob"}}
I would also want to maybe match for the same customer and same location, which are keys in the record dictionary.

With this data structure, you will indeed have to iterate over all of it to be able to find the corresponding items. You might be able to improve it somewhat by building a second structure as you iterate over it first so that instead of O(n²) you get something more like O(n log n). But that's going to be about as good as you'll get with this structure.

What you need to do is to effectively index it on other portions of data and work off of those.

{"Client": "Bob", "Buys": [ "id1" ], "Sells": [ "id2" ] }

And, now you can look that up in a hash table or dictionary (whatever your language calls them) in O(1) by pulling up just Bob. Then you can do whatever you want with the Buys and Sells lists.

Similarly, you would do similar things with the Stores. But you need to build the corresponding data structure that matches the queries you want to do against it.

You may wish to consider that if you are getting to the point of wanting to be able to run these queries against the data, you might need to move to the "next level" of storing the data and put it in a relational database. This gives you code that is designed to run these queries really fast and frees you up from worrying about "oh, now I need to build this other structure to be able to do the query for "who are all the customers at some store?" in a reasonable time".

Jim Mischel · Accepted Answer · 2015-11-10 19:29:27Z

One way is to split them into two separate lists (one for buys and one for sells), sort them by name and location, and then do a simple merge.

For example:

var buyList = records.Where(Convert.ToString(records["Transaction"]) == "BUY")
    .OrderBy(Convert.ToString(records["Client"]))
    .ThenBy(Convert.ToString(records["Location"]));
var sellList = records.Where(Convert.ToString(records["Transaction"]) == "SELL")
    .OrderBy(Convert.ToString(records["Client"]))
    .ThenBy(Convert.ToString(records["Location"]));

Now you can do a standard merge algorithm, stepping through the two lists in tandem. See my article Merging sorted sequences for the basic idea.

That turns your O(N^2) into something like m log m + n log n + 3N, where m and n are the number of buys and sells, respectively, and N is the total number of transactions. It does, however, require O(N) extra space for the temporary lists.

Doctor Vermilion Wizard · Accepted Answer · 2015-11-10 19:53:45Z

An O(N) algorithm would be to construct a new dictionary where the key is formed from the values that you're trying to search for.

Dictionary<string, Dictionary<string, object>> records;
Dictionary<Tuple<string,string,string>, Dictionary<string,object>> lookup;

foreach (var record in records.Values)
{
    var key = new Tuple<string,string,string>(record["Client"], record["Location"],record["Transaction"]);
    lookup[key] = record; // this assumes that the composite key is unique
}

foreach(var kvp in lookup)
{
    var key = kvp.Key;
    var altKey = new Tuple<string,string,string>(key.Item1,key.Item2,FlipTransaction(key.Item3));
    if (lookup.ContainsKey(altKey))
    {
        // lookup[altKey] contains the paired transaction.
    }
}

FlipTransaction is a function that returns "Buy" if its argument is "Sell" or vice-versa.

You have an O(N) loop to build the new lookup dictionary and an O(N) loop to iterate through its contents.

Also, like the algorithm in the question this will find each pair twice.

Stack Exchange Network

A better way than O(n^2) for traversing a dictionary of dictionaries.

3 Answers 3

Hot Network Questions

A better way than O(n^2) for traversing a dictionary of dictionaries.

3 Answers 3

Related

Hot Network Questions