LINQ in SortedList

Question

Sono un novizio completo LINQ, quindi non so se il mio LINQ non è corretta per quello che ho bisogno di fare o se le mie aspettative di prestazioni sono troppo alte.

Ho un SortedList di oggetti, digitato da int; SortedList al contrario di SortedDictionary perché sarò popolano la raccolta con i dati pre-ordinato. Il mio compito è quello di trovare sia la chiave esatta o, se non c'è una chiave precisa, quella con il successivo valore più alto. Se la ricerca è troppo alta per la lista (per esempio tasto più alto è di 100, ma la ricerca di 105), di ritorno nullo.

// The structure of this class is unimportant.  Just using
// it as an illustration.
public class CX
{
    public int KEY;
    public DateTime DT;
}

static CX getItem(int i, SortedList<int, CX> list)
{
    var items =
    (from kv in list
     where kv.Key >= i
     select kv.Key);

    if (items.Any())
    {
        return list[items.Min()];
    }

    return null;
}

Dato un elenco di 50.000 record, chiamando getItem 500 volte richiede circa un secondo e mezzo. Chiamarlo 50.000 volte dura più di 2 minuti. Questa performance sembra molto povera. È il mio LINQ male? Sto aspettavo troppo? Dovrei essere a rotazione la mia funzione di ricerca binaria?

Answer 1

Scrivi ricerca binaria sul proprio può essere difficile.

Fortunatamente, Microsoft ha già scritto una bella robusta uno: Array.BinarySearch<T>. Questo è, infatti, il metodo che utilizza SortedList<TKey, TValue>.IndexOfKey internamente . L'unico problema è che ci vuole un argomento T[], invece di qualsiasi IList<T> (come SortedList<TKey, TValue>.Keys).

Sai una cosa, però? C'è questo grande strumento chiamato Riflettore che ti permette di guardare il codice sorgente di .NET .. .

Check it out:. Un metodo di estensione BinarySearch generica su IList<T>, presi direttamente dal codice riflessa di implementazione Array.BinarySearch<T> di Microsoft

public static int BinarySearch<T>(this IList<T> list, int index, int length, T value, IComparer<T> comparer) {
    if (list == null)
        throw new ArgumentNullException("list");
    else if (index < 0 || length < 0)
        throw new ArgumentOutOfRangeException((index < 0) ? "index" : "length");
    else if (list.Count - index < length)
        throw new ArgumentException();

    int lower = index;
    int upper = (index + length) - 1;

    while (lower <= upper) {
        int adjustedIndex = lower + ((upper - lower) >> 1);
        int comparison = comparer.Compare(list[adjustedIndex], value);
        if (comparison == 0)
            return adjustedIndex;
        else if (comparison < 0)
            lower = adjustedIndex + 1;
        else
            upper = adjustedIndex - 1;
    }

    return ~lower;
}

public static int BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer) {
    return list.BinarySearch(0, list.Count, value, comparer);
}

public static int BinarySearch<T>(this IList<T> list, T value) where T : IComparable<T> {
    return list.BinarySearch(value, Comparer<T>.Default);
}

Questo vi permetterà di chiamare list.Keys.BinarySearch e ottenere il complemento bit a bit negativo dell'indice che si desidera nel caso in cui il tasto desiderato non si trova (il sotto è tratto sostanzialmente retta dalla risposta di tzaman):

int index = list.Keys.BinarySearch(i);
if (index < 0)
    index = ~index;
var item = index < list.Count ? list[list.Keys[index]] : null;
return item;

Answer 2

In primo luogo, la query viene valutato due volte (una volta per Any, e una volta per Min). In secondo luogo, Min richiede che iterate su tutta la lista, anche se il fatto che si tratta di mezzi ordinati che la prima voce sarà il minimo. Dovreste essere in grado di cambiare questo:

if (items.Any())
{
    return list[items.Min()];
}

Per questo:

var default = 
    (from kv in list
     where kv.Key >= i
     select (int?)kv.Key).FirstOrDefault();

if(default != null) return list[default.Value];

return null;

Aggiorna

Perché si sta selezionando un tipo di valore, FirstOrDefault non restituisce un oggetto annullabile. Ho modificato la query per il cast del valore selezionato a un int? invece, permettendo al valore risultante da controllare per null. Auspico, pertanto, questo rispetto all'uso di ContainsKey, come sarebbe tornare true se l'elenco contiene un valore per 0. Per esempio, supponiamo di avere i seguenti valori

0 2 4 6 8

Se si dovesse passare a qualcosa di meno o uguale a 8, poi si otterrebbe il valore corretto. Tuttavia, se si dovesse passare a 9, si otterrebbe 0 (default(int)), che è nella lista, ma non un risultato valido.

Answer 3

Utilizzando LINQ su un SortedList non vi darà il beneficio del genere.

Per ottenere prestazioni ottimali, si dovrebbe scrivere il proprio binario di ricerca.

Answer 4

OK, giusto per dare a questo un po 'più di visibilità - Ecco una versione più concisa della risposta di Adam Robinson:

return list.FirstOrDefault(kv => kv.Key >= i).Value; 

La funzione FirstOrDefault ha un sovraccarico che accetta un predicato, che seleziona il primo elemento che soddisfa una condizione - è possibile utilizzare che per ottenere direttamente l'elemento che si desidera, o null se non esiste.

Answer 5

Perché non usare il BinarySearch che è costruito nella classe List?

var keys = list.Keys.ToList();
int index = keys.BinarySearch(i);
if (index < 0)
    index = ~index;
var item = index < keys.Count ? list[keys[index]] : null;
return item;

Se la destinazione di ricerca non è nella lista, BinarySearch restituisce il complemento bit per bit della voce immediatamente superiore; possiamo utilizzare che per ottenere direttamente ciò che vuoi da ri-integrando il risultato se è negativo. Se diventa uguale al Count, la vostra chiave di ricerca era più grande di qualsiasi altra cosa nella lista.

Questo dovrebbe essere molto più veloce di fare un where LINQ, dal momento che è già ordinato ... Come commenti hanno sottolineato, la chiamata ToList costringerà una valutazione di tutta la lista, quindi questo è utile solo se si fa più ricerche senza alterare il SortedList sottostante, e si mantiene l'elenco keys intorno separatamente.

Answer 6

Utilizzando OrderedDictionary in PowerCollections è possibile ottenere un enumeratore che inizia dove si chiave sono alla ricerca di dovrebbe essere ... se non è lì, si otterrà il nodo successivo più vicino e può quindi passare avanti / indietro da quella in O (log n) per ogni chiamata nav.

Questo ha il vantaggio di non dover scrivere il proprio di ricerca o anche gestire le proprie ricerche sulla cima di una SortedList.