Un modo migliore di O (n ^ 2) per attraversare un dizionario di dizionari.

{"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.

Con questa struttura dati, dovrai effettivamente scorrere tutte le voci per poter trovare gli elementi corrispondenti. Potresti essere in grado di migliorarlo un po 'costruendo una seconda struttura mentre iterate su di essa per prima in modo che invece di O (n ² ) ottieni qualcosa di più simile a O (n log n). Ma questo sarà quanto di meglio si otterrà con questa struttura.

Quello che devi fare è indicizzarlo efficacemente su altre porzioni di dati e risolverle.

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

E ora puoi cercare in una tabella hash o in un dizionario (qualunque sia la tua lingua li chiami) in O (1) tirando su solo Bob. Quindi puoi fare quello che vuoi con gli elenchi Buys and Sells.

Allo stesso modo, faresti cose simili con i Negozi. Ma devi creare la struttura dati corrispondente che corrisponda alle query che vuoi fare contro di essa.

Potresti voler considerare che se stai arrivando al punto di voler essere in grado di eseguire queste query sui dati, potresti dover passare al "prossimo livello" di archiviazione dei dati e metterli in un rapporto Banca dati. Questo ti dà il codice che è progettato per eseguire queste query molto velocemente e ti libera dalla preoccupazione di "oh, ora ho bisogno di costruire questa struttura altra per essere in grado di fare la domanda per "chi sono tutti i clienti in qualche negozio?" in un tempo ragionevole ".

Un modo è dividerli in due elenchi separati (uno per gli acquisti e uno per le vendite), ordinarli per nome e posizione, quindi eseguire una semplice unione.

Ad esempio:

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"])); 

Ora puoi fare un algoritmo di fusione standard, passando in rassegna i due elenchi in tandem. Vedi il mio articolo Unire le sequenze ordinate per l'idea di base.

Questo trasforma la tua O (N ^ 2) in qualcosa come m log m + n log n + 3N , dove m e n sono rispettivamente il numero di acquisti e di vendite, e N è il numero totale di transazioni. Tuttavia, richiede O (N) spazio extra per gli elenchi temporanei.

Un algoritmo O (N) potrebbe essere quello di costruire un nuovo dizionario in cui la chiave è formata dai valori che stai cercando di cercare.

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 è una funzione che restituisce "Acquista" se il suo argomento è "Vendi" o viceversa.

Hai un ciclo O (N) per creare il nuovo dizionario di ricerca e un loop O (N) per scorrere il suo contenuto.

Inoltre, come l'algoritmo nella domanda questo troverà ogni coppia due volte.