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>> recordsforeach (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)        {        }    }}
A better way than O(n^2) for traversing a dictionary of dictionaries.
c#;algorithms
{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(n2) 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.