È possibile eseguire una corrispondenza di stringa parziale su una chiave di stringa del dizionario?

Question

Ho un Dictionary<string, List<int>> nel mio codice che sto utilizzando nel modo seguente:

Key   Values 
2011-07-15 1, 2, 3 
2011-07-20 4, 5, 6 
2010-02-11 7, 8, 9 

Il mio codice deve essere in grado di interrogare per tutti i valori corrispondenti a una particolare stringa nella chiave. Ad esempio, se avessi la sottostringa 2011-07, dovrebbe restituire i valori {1, 2, 3, 4, 5, 6}. Una sottostringa di 11 dovrebbe restituire tutti gli ID da 1-9.

Qualcuno può consigliare un modo conciso per raggiungere questo obiettivo? O fornire una migliore struttura dati per il recupero di queste informazioni?

Answer 1

farei un metodo di estensione:

public static class DictionaryExt 
{ 
    public static IEnumerable<T> PartialMatch<T>(this Dictionary<string, T> dictionary, string partialKey) 
    { 
     // This, or use a RegEx or whatever. 
     IEnumerable<string> fullMatchingKeys = 
      dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey)); 

     List<T> returnedValues = new List<T>(); 

     foreach (string currentKey in fullMatchingKeys) 
     { 
      returnedValues.Add(dictionary[currentKey]); 
     } 

     return returnedValues; 
    } 
} 

Il "costo" di aggiungere valori al dizionario non cambierebbe, ma il costo di recupero sarebbe stato superiore, ma solo quando sai che sei andando con una partita parziale.

Btw, sono sicuro che è possibile trasformare questo in una singola espressione Lambda, ma il concetto rimane lo stesso.

Modifica: nell'esempio, questo metodo restituisce 2 elenchi di valori, ma è possibile modificarlo per unire gli elenchi. Ecco il metodo di estensione si potrebbe fare:

public static IEnumerable<T> PartialMatch<T>(
    this Dictionary<string, IEnumerable<T>> dictionary, 
    string partialKey) 
{ 
    // This, or use a RegEx or whatever. 
    IEnumerable<string> fullMatchingKeys = 
     dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey)); 

    List<T> returnedValues = new List<T>(); 

    foreach (string currentKey in fullMatchingKeys) 
    { 
     returnedValues.AddRange(dictionary[currentKey]); 
    } 

    return returnedValues; 
} 

Edit 2: Vieni a pensarci bene, si potrebbe anche rendere più generico. Con il metodo di estensione successiva, sarebbe lavorare su qualsiasi dizionario, fino a quando si fornisce un comparer che controllare cosa si intende per "corrispondenza parziale":

public static IEnumerable<TValue> PartialMatch<TKey, TValue>(
    this Dictionary<TKey, IEnumerable<TValue>> dictionary, 
    TKey partialKey, 
    Func<TKey, TKey, bool> comparer) 
{ 
    // This, or use a RegEx or whatever. 
    IEnumerable<TKey> fullMatchingKeys = 
     dictionary.Keys.Where(currentKey => comparer(partialKey, currentKey)); 

    List<TValue> returnedValues = new List<TValue>(); 

    foreach (TKey currentKey in fullMatchingKeys) 
    { 
     returnedValues.AddRange(dictionary[currentKey]); 
    } 

    return returnedValues; 
} 

Answer 2

Un modo conciso sarebbe utilizzare la Mappa multivalore.

Ad esempio:

Dictionary<string, Dictionary<string, List<int>> 

Perché non si memorizza il 2011-07 come una chiave e 15 per la chiave di dizionario interno e 1,2,3 come valori.

mappa ["2011-07"] ["15"] = {1,2,3};

se si desidera solo 2011-07 è possibile ottenere tutto all'interno dell'altro dizionario di traversal.

map["2011-07"] // sarebbe tornato u 1,2,3,4,5,6

e se si vuole andare in un giorno specifico, 2011-07-15, questo sarebbe tornare u solo 1,2,3

foreach(var element in map["2011-07"]){ 

    var values = element.values; // and you can append them to a list. 

} 

se avete bisogno di anno/mese/giorno, avrete bisogno di dizionari multilivello. oppure è possibile utilizzare anche l'albero .

Answer 3

Se il Dizionario utilizza gli hash interni, si è fuori di sorte, poiché stringhe simili producono hash dissimili. Ho appena implementato la soluzione a questo requisito durante il fine settimana in C, un test di intervista/compiti a casa. Ho usato un array ordinato come struttura sottostante: inserti costosi, ma ricerche veloci (usando la ricerca binaria). Per trovare tutte le voci con la chiave che inizia con un prefisso, troverei la prima, poi la prossima, la successiva ... Per la sottostringa generale, cioè non solo il prefisso, la mia soluzione non funzionerebbe. In questo momento non so cosa suggerire per la ricerca "sottostringa generale".

Answer 4

Si potrebbero avere tre dizionari. Anno mese giorno.

Nota che quando aggiungi elementi a tre dizionari, NON stai duplicando gli articoli.

Quando si estrae gli elementi utilizzando due tasti, è possibile utilizzare il metodo Estensione LINQ Intersect() per ottenere gli elementi che corrispondono a entrambi i tasti (Usa Intersect nei due set di risultati).

Avvertenza, in questo modo non si otterrebbe il codice di esecuzione più veloce.

Answer 5

Siete alla ricerca di risposte concise. Senza indicizzazione di fantasia a basso livello per il testo (di cui non conosco le classi specializzate .Net), penso che il dizionario sia ancora la soluzione migliore. Query con qualcosa del tipo:

myDictionary.Where (kvp => kvp.Key.Contains ("11")). SelectMany (kvp => kvp.Value);

Devi cercare tra tutti i tasti per una sottostringa generalizzata, in ogni caso, senza una magia piuttosto interessante (non fornita da .Net), quindi LINQ non dovrebbe farti molto male qui.