Binäre Suche auf den Tasten der SortedList<K V>

Muss ich schreiben einige code für die lineare interpolation und ich bin versucht, herauszufinden, die effizienteste Weg, um die Schlüssel zu suchen der ein SortedList<K, V> für die Obere und untere Tasten, die um mein Ziel-Schlüssel.

SortedList<int, double> xyTable = new SortedList<int, double>()
{
    {1, 10}, {2, 20}, {3, 30}, {4,40}
};

double targetX = 3.5;

Was ist der effizienteste Weg, um in der Liste suchen und bestimmen, die 3.5 ist zwischen 3 und 4? Ich habe eine Methode /cheat, der funktioniert für ganze zahlen (vorübergehend legen Sie die Ziel-Taste in der Liste suchen Sie dann den index), aber ich dachte, ich würde bitten, die Profis, also könnte ich die Erzeugung von hochwertigen code.

Dank.

InformationsquelleAutor Nitax | 2011-05-23
  1. 7

    Binäre Suche gibt Ihnen anständige Leistung auf eine Liste. Jedoch die Schlüssel-Eigenschaft auf SortedList ist der Typ IList, in der Erwägung, dass BinarySearch definiert ist List. Glücklicherweise finden Sie eine Implementierung der binären Suche für IList in diesem Zusammenhang Frage:

    Wie zum ausführen einer binären Suche auf IList<T>?

    InformationsquelleAutor ColinE
  2. 4

    In meinem Fall die Quelle SortedList ändert sich nicht viel, da deren Einsatz als lookup-Tabelle. So in diesem Fall macht es Sinn, konvertieren Sie die SortedList zu einem List<T> einmal. Danach ist es Recht einfach zu bedienen built-in binarysearch-Methode Methode der List<T>...

    double targetX = 3.5;

//Assume keys are doubles, may need to convert to doubles if required here.
//The below line should only be performed sparingly as it is an O(n) operation.
//In my case I only do this once, as the list is unchanging.
List<double> keys = xyTable.Keys.ToList();

int ipos = keys.BinarySearch(targetX);

if (ipos >= 0)
{
    //exact target found at position "ipos"
}
else
{
    //Exact key not found: BinarySearch returns negative when the 
    //exact target is not found, which is the bitwise complement 
    //of the next index in the list larger than the target.
    ipos = ~ipos;
    if (ipos >= 0 && ipos < keys.Count)
    {
        if (ipos > 0)
        {
            //target is between positions "ipos-1" and "ipos"
        }
        else
        {
            //target is below position "ipos"
        }
    }
    else
    {
        //target is above position "ipos"
    }
}
    • Gute Sachen, das ist die Antwort, die ich im Begriff war, Sie zu geben. 🙂
    • target ist unter der position "ipos" - meinst du, es ist unterhalb der untersten Taste in der Reihe?
    • Downvoted, weil jemand fragt, für eine binäre Suche ist interessiert, in der Leistung. ToList jedoch ist eine überflüssige und langsame O(n) - operation, und es ist besser für die Leistung (CPU und Arbeitsspeicher Verbrauch) nach der Arbeit direkt auf die IList<K> Keys wie angegeben durch ColinE Antwort, die auch links eine Frage mit einer kopieren-und-pasteable Antwort.
    • vielen Dank für dein Kommentar - habe ich einen Kommentar über diese Tatsache. In meinem Fall, wie ich anfangs erwähnte, die Liste, die ich ausgeführt wurde, eine binäre Suche auf ist unveränderlich, und so war ich nur der Durchführung der ToList() einmal, in einer statischen constructer-Methode.
    InformationsquelleAutor dodgy_coder
  3. 2

    MSDN,

    Die Elemente der SortedList-Objekt sortiert werden, indem Sie die Tasten entweder nach einer bestimmten IComparer-Implementierung angegeben, wenn die SortedList erstellt wird, oder nach der IComparable-Implementierung zur Verfügung gestellt, indem die Tasten selbst.
    Die index-Sequenz basierend auf der Sortierreihenfolge. Wenn ein element Hinzugefügt wird, wird es eingefügt in SortedList in der richtigen Reihenfolge Sortieren lassen, und die Indizierung passt sich entsprechend an. Wenn ein element entfernt wird, wird die Indizierung passt sich auch entsprechend an. Daher wird der index von einem bestimmten Schlüssel/Wert-paar kann geändert werden, wenn Elemente Hinzugefügt oder entfernt werden aus der SortedList.

    *****Diese Methode nutzt einen binären such-Algorithmus; daher diese Methode ist eine O(log n) - operation, wobei n für die Anzahl.*****

    Beginnend mit dem .NET Framework 2.0 wird diese Methode verwendet die collection-Objekte' Equals und CompareTo-Methoden auf einen Gegenstand, um zu bestimmen, ob das Element vorhanden ist. In den früheren Versionen des .NET Framework, diese Bestimmung wurde vorgenommen, indem die Equals und CompareTo Methoden der item-parameter auf die Objekte in der Sammlung.

    In anderen Worten, die Methode IndexOfKey in SortedList ist eigentlich mit binarysearch-Methode der Algorithmus bereits, so gibt es keine Notwendigkeit, zu konvertieren form SortedList Liste in Ihrem Fall.

    Hoffe es hilft..

    • IndexOfKey findet nur exakte übereinstimmung. Die Frage ist, klar, dass ist nicht das, was erforderlich ist, benötigen Sie "Obere und untere Tasten, die um mein Ziel-Schlüssel".
    InformationsquelleAutor Yoel Wigoda Kaver
  4. 1
    public class Bounds
{
    int lower;
    int upper;

    public Bounds(int lower, int upper)
    {
       this.lower = lower;
       this.upper = upper;
    }
}

public Bounds BinarySearch(List<int> keys, double target)
{
    //lower boundary case returns the smallest key as the lower and upper bounds
    if (target < keys[0])
        return new Bounds(0, 0);

    else if (target < keys[1])
        return new Bounds(0, 1);

    //upper boundary case returns the largest key as the lower and upper bounds
    else if (target > keys[keys.Length - 1])
        return new Bounds(keys.Length - 1, keys.Length - 1);

    else if (target > keys[keys.Length - 2])
        return new Bounds(keys.Length - 2, keys.Length - 1);

    else
        return BinarySearch(keys, target, 0, keys.Length - 1);

}

//'keys' is a List storing all of the keys from your SortedList.
public Bounds BinarySearch(List<int> keys, double target, int lower, int upper)
{
    int middle = (upper + lower)/2;

    //target is equal to one of the keys
    if (keys[middle] == target)
        return new Bounds(middle - 1, middle + 1);

    else if (keys[middle] < target && keys[middle + 1] > target)
        return new Bounds(middle, middle + 1);

    else if (keys[middle] > target && keys[middle - 1] < target)
        return new Bounds(middle - 1, middle);

    if (list[middle] < target)
         return BinarySearch(list, target, lower, upper/2 - 1);

    if (list[middle] > target)
         return BinarySearch(list, target, upper/2 + 1, upper);
}

    Dies funktionieren könnte..ich habe nicht testen Sie es aus. Wenn nicht, hoffentlich ist es dicht genug, dass Sie können es verwenden, mit geringfügigen Verbesserungen. Das ist ein komisches problem, also ich behandelt alle von der "boundary cases", damit ich nicht darüber nachdenken, was der Algorithmus tun würde, wenn der Bereich wurde bis auf 2 Elemente oder weniger.

    • Warum nicht List<T>.BinarySearch()?
    • Ich bin nicht sehr vertraut mit es..wird die List<T>.Binarysearch-Methode() ausreichend sein, um das zu finden, was er sucht?
    • es wäre, wenn er hed List<T>, aber er hat nur IList<T>, so dass Ihre Lösung ist tatsächlich ein guter Vorschlag.
    InformationsquelleAutor alexD
Schreibe einen Kommentar