Come trovare il punto tra le due chiavi nel dizionario ordinato

Question

Ho un dizionario ordinato che contiene punti di dati misurati come coppie chiave / valore. Per determinare il valore per dati non misurati punto che voglio estrapolare il valore tra due chiavi note utilizzando un'interpolazione lineare dei valori corrispondenti. Capisco come calcolare il punto dati non misurati una volta che ho le due coppie chiave / valore che è compresa tra. Quello che non so è come trovare le chiavi che si trova tra. C'è un modo più elegante di una (funzione / interrogazione sto pensando LINQ) "per" ciclo di capire quale due tasti mie bugie del punto di dati tra?

Answer 1

Qualcosa di simile potrebbe funzionare:

 dic.Keys.Zip(dic.Keys.Skip(1), 
              (a, b) => new { a, b })
         .Where(x => x.a <= datapoint && x.b >= datapoint)
         .FirstOrDefault();

Questa traverse essi chiavi utilizzando il fatto che essi sono ordinate e confronta tutti i due tasti si susseguono in ordine -. Dal momento che LINQ è pigro una volta a trovare la prima partita l'attraversamento si fermerà

Answer 2

I C # risposte standard sono tutti O (N) complessità. A volte basta solo un piccolo sottoinsieme di una piuttosto grande raccolta differenziata. (Quindi non sei iterazione tutte le chiavi) C # collezioni standard non vi aiuterà qui. E una soluzione è come segue: http://www.itu.dk/research/c5/ Utilizzare l'IntervalHeap nella C5 collezioni biblioteca. Questa classe supporta un metodo getRange () e si ricerca lo StartKey con O (log N) complessità e iterate la gamma con O (N) complessità. Che sarà sicuramente utile per i grandi insiemi di dati, se le prestazioni sono critiche. per esempio. Spatial Partitioning nel gioco

Answer 3

Possibile che stai chiedendo di seguire:

myDictionary.Keys.Where(w => w > start && w < end)

Answer 4

ciclo regolare dovrebbe essere ok qui:

IEnumerable<double> keys = ...; //ordered sequence of keys
double interpolatedKey = ...;

// I'm considering here that keys collection doesn't contain interpolatedKey

double? lowerFoundKey = null;
double? upperFoundKey = null;

foreach (double key in keys)
{
    if (key > interpolatedKey)
    {
        upperFoundKey = key;
        break;
    }
    else
        lowerFoundKey = key;
}

E 'possibile farlo in C # con LINQ con il codice più breve, ma meno efficace:

double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey);
double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);

Per efficacemente con LINQ dovrebbe avere un metodo che si chiama finestra in F # con parametro 2. restituirà un IEnumerable di coppie adiacenti di raccolta keys. Mentre questa funzione non è presente in LINQ regolare ciclo foreach dovrebbe essere ok.

Answer 5

Non credo che ci sia una funzione su SortedDictionary che permette di trovare gli elementi in tutto quello che vi serve più veloce di elementi iterazione. (+1 a soluzione BrokenGlass)

Per essere in grado di trovare gli oggetti più veloci è necessario passare a qualche altra struttura. Cioè SortedList fornisce funzionalità simili, ma permette di indicizzare la sua consegna delle chiavi e quindi è possibile utilizzare serach binaria per trovare il campo.