Esiste una funzione di limite inferiore su un SortedList<K,V>?

Question

Esiste una funzione di limite inferiore su a SortedList<K ,V>?La funzione dovrebbe restituire il primo elemento uguale o maggiore della chiave specificata.C'è qualche altra classe che lo supporta?

Ragazzi, per favore leggete di nuovo la domanda. Non ho bisogno di una funzione che restituisca la chiave se è presente.Sono interessato allo scenario in cui non esiste una corrispondenza esatta della chiave.

Sono interessato al tempo O (log n)..Significa che non ho problemi con il ciclo foreach, ma piuttosto mi piacerebbe avere un modo efficiente per farlo.

Ho fatto alcune prove a riguardo.

Le istruzioni Linq non sono ottimizzate né dal compilatore né dalla macchina runtime, quindi attraversano tutti gli elementi della raccolta e sono lente O(n).Basandosi sulla risposta di Mehrdad Afshari, ecco una ricerca binaria che funziona in O(log n) sulla raccolta Keys:

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
            this IList<T> sortedCollection, T key
        ) where T : IComparable<T> {
    int begin = 0;
    int end = sortedCollection.Count;
    while (end > begin) {
        int index = (begin + end) / 2;
        T el = sortedCollection[index];
        if (el.CompareTo(key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}

Answer 1

Ricerca binaria il SortedList.Keys collezione.

Eccoci qui.Questo è O(log N):

private static int BinarySearch<T>(IList<T> list, T value)
{
    if (list == null)
        throw new ArgumentNullException("list");
    var comp = Comparer<T>.Default;
    int lo = 0, hi = list.Count - 1;
    while (lo < hi) {
            int m = (hi + lo) / 2;  // this might overflow; be careful.
            if (comp.Compare(list[m], value) < 0) lo = m + 1;
            else hi = m - 1;
    }
    if (comp.Compare(list[lo], value) < 0) lo++;
    return lo;
}

public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
                          (this SortedList<T,U> sortedList, T key)
{
    return BinarySearch(sortedList.Keys, key);
}

Answer 2

Sceglierei LINQ (presumendo che tu stia utilizzando C#3), ma utilizzando l'overload di FirstOrDefault che accetta un predicato:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

(molti altri metodi Enumerable possono anche accettare predicati, il che è una bella scorciatoia)

Answer 3

Non ne sono a conoscenza, ma è una semplice istruzione LINQ:

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();

first sarà il primo oggetto che supera il confronto oppure default(T) (che è normalmente null).

Modificare

La versione di DaveW:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

fa lo stesso lavoro ma potrebbe essere potenzialmente più veloce, dovresti comunque testarlo.

Answer 4

Oppure puoi scrivere il tuo metodo di estensione per farlo.Tieni presente che NON è garantito che tutte queste funzioni vengano eseguite in sequenza.

Answer 5

Si spera che questo dovrebbe essere più veloce, a seconda dell'implementazione di SortedList.

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
        this SortedList<K, V> sortedCollection, K key
    ) where V : new()
{
    if (sortedCollection.ContainsKey(key))
    {
        return sortedCollection.IndexOfKey(key);
    }
    sortedCollection[key] = new V();
    int retval = sortedCollection.IndexOfKey(key);
    sortedCollection.Remove(key);
    return retval;
}