Come faccio ad avere chiave precedente da SortedDictionary?

Question

Ho dizionario contenente coppie di valori fondamentali.

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

Voglio ottenere precedente coppia chiave-valore da un valore chiave nota. Nel caso di cui sopra, se ho tasto 4, quindi come posso ottenere <2,20>?

Answer 1

E 'difficile da implementare in modo efficiente con un SortedDictionary<TKey, TValue> dal momento che è implementato come un albero binario di ricerca che non espone predecessori o successori.

Si potrebbe naturalmente solo enumerare ogni KeyValuePair fino a trovare il tasto "conosciuto". Con un po 'di LINQ, questo sarebbe simile (assumendo che la chiave esiste sicuramente e non è la prima chiave):

SortedDictionary<int, int> dictionary = ...
int knownKey = ...

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                            .Last();

Se questi presupposti non sono titolari, si potrebbe fare:

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                                 .Cast<KeyValuePair<int, int>?>()
                                 .LastOrDefault();

(Controllare che maybePreviousKvp != null per accertare che il precedente KeyValuePair è stato recuperato con successo.)

Ma questo non sta per essere efficace a tutti.

---

Se possibile, è consigliabile utilizzare un SortedList<TKey, TValue> invece (ovviamente, questo non può essere possibile se non si può prendere i suoi inserti più lenti ed eliminazioni). Questa chiave efficiente supporti di raccolta e recupero di valore per ordinato Indice di quanto è implementato come un array growable. Poi la query diventa semplice come:

SortedList<int, int> dictionary = ...
int knownKey = ...

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1;

// if "known" key exists and isn't the first key
if(indexOfPrevious >= 0)
{
   // Wrap these in a KeyValuePair if necessary
   int previousKey = dictionary.Keys[indexOfPrevious];
   int previousValue = dictionary.Values[indexOfPrevious];      
}

IndexOfKey esegue una ricerca binaria sui tasti-list, in esecuzione in tempo O(log n). Tutto il resto deve essere eseguito in un tempo costante, il che significa l'intera operazione dovrebbe essere eseguito in tempo logaritmico.

---

In caso contrario, si dovrà implementare te stesso / trovare una collezione BST che non espone predecessori / successori.

Answer 2

Sono stato anche alla ricerca di una risposta a questo problema, e ho pensato che una soluzione migliore di tutte le risposte qui è quello di utilizzare il TreeDictionary<K, V> dal C5 Collezioni ( GitHub / NuGet ), che è un'implementazione di un albero rosso-nero

.

Ha Predecessor / TryPredecessor e WeakPredessor / TryWeakPredecessor metodi (così come i metodi equivalenti per successori) che fa esattamente ciò che si desidera.

Ad esempio:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

// applied to the dictionary itself, returns KeyValuePair<int,int>
var previousValue = dictionary.Predecessor(4);
Assert.Equals(previousValue.Key, 2);
Assert.Equals(previousValue.Value, 20);

// applied to the keys of the dictionary, returns key only
var previousKey = dictionary.Keys.Predecessor(4);
Assert.Equals(previousKey, 2);

// it is also possible to specify keys not in the dictionary
previousKey = dictionary.Keys.Predecessor(3);
Assert.Equals(previousKey, 2);

Answer 3

KeyValuePair<int, int> lookingForThis = dictionary
  .Reverse()
  .SkipWhile(kvp => kvp.Key != 4)
  .Skip(1)
  .FirstOrDefault();

Answer 4

Si potrebbe ciclo attraverso il dizionario e tenere traccia dei valori, immagino. Qualcosa di simile a questo:

public int GetPreviousKey(int currentKey, SortedDictionary<int, int> dictionary)
{
    int previousKey = int.MinValue;
    foreach(KeyValuePair<int,int> pair in dictionary)
    {
        if(pair.Key == currentKey)
        {
            if(previousKey == int.MinValue)
            {
                throw new InvalidOperationException("There is no previous key.");
            }
            return previousKey;
        }
        else
        {
            previousKey = pair.Key;
        }
    }
}

Tuttavia, questa è un'operazione piuttosto strano da richiedere. Il fatto che ne avete bisogno potrebbe essere puntato verso un problema con il vostro disegno.

Answer 5

Dictionary<TKey,TValue> è non ordinato, quindi non c'è precedente cosa per qualche elemento. Invece è possibile utilizzare SortedDictionary<TKey,TValue> .

EDIT:. Spiacente ho letto il titolo unico LOL

Se Sono d' uso LINQ:

int givenKey = 4;
var previousItem = dict.Where((pair, index) => 
                                   index == dict.Count || 
                                   dict.ElementAt(index + 1).Key == givenKey)
                       .FirstOrDefault();

Answer 6

Io preferirei usare LINQ se è questo il caso ... provare questo sarà sicuramente il lavoro

SortedDictionary<int,int> dictionary = new SortedDictionary<int,int>();
dictionary.add(1, 33);
dictionary.add(2, 20);
dictionary.add(4, 35);

int SelectedKey = 4;

var ResutValue = ( from n in dictionary    
               where n.Key < TheSelectedKey
               select n.Value).Last();

this.txtResult.Text = ResultValue.ToString();

Answer 7

Che ne dici di questo? I havent provato, però, ma dovrebbe dare qualcosa per iniziare a pensare in questa direzione. Speranza che aiuta.

        int input = 4;
        List<int> lKeys = dictionary.Keys.ToList();
        int reqIndex = lKeys.IndexOf(input) - 1;
        int reqAnswer = dictionary[reqIndex];

di prova per le altre condizioni, come se (reqIndex! = -1), ecc ..