Was .NET-Wörterbuch unterstützt "finde nächstgelegene Taste" Betrieb?

Ich bin der Konvertierung C++ - code in C# und es ruft std::map::lower_bound(k) zu finden, einen Eintrag in die Karte, dessen Schlüssel gleich oder größer als k sein. Allerdings sehe ich keine Möglichkeit, das zu tun die gleiche Sache mit .NET das SortedDictionary. Ich vermute, ich könnte eine Problemumgehung implementieren, mit der SortedList, aber leider SortedList ist zu langsam (O(n) für einfügen und löschen von Schlüsseln). Was kann ich tun?

Hinweis: ich habe eine Problemumgehung verwenden, nutzt mein Szenario... Speziell, meine keys sind eine Dichte Bevölkerung von ganzen zahlen, beginnend bei knapp über 0, so habe ich eine Liste<TValue> meine Wörterbuch mit der Liste-index dienen als Schlüssel, und die Suche nach einem Schlüssel, der größer oder gleich k kann gemacht werden in nur ein paar schleifendurchläufe. Aber es wäre noch schön zu sehen, dass die ursprüngliche Frage beantwortet.

Gleichen question, aber ohne Beschränkung auf SortedList<K, V>.

InformationsquelleAutor Qwertie | 2009-11-06

2

Dauerte es ein paar Monate Arbeit, aber endlich kann ich Ihnen zumindest eine teilweise Lösung für dieses problem... ich nenne es den Compact Patricia Trie, eine sortierte Wörterbuch, das bietet eine "find nächst größeren Schlüssel" Betrieb.

http://www.codeproject.com/KB/recipes/cptrie.aspx

Es ist nur eine teilweise Lösung, da Sie nur bestimmte Arten von Schlüsseln werden unterstützt, nämlich byte[], string, und alle primitiven integer-Typen (Int8..UInt64). Auch die string-Sortierung groß-und Kleinschreibung.
- -1: diese ist vergoldet. c2.com/cgi/wiki?GoldPlating
- Ich bin damit einverstanden. Gibt es andere bessere Lösungen gibt, z.B. die TreeDictionary<K,V> im C5-Sammlungen das ist ein rot-schwarz-Baum implementation, und hat WeakSuccessor/TryWeakSuccessor Methoden, die schon.
InformationsquelleAutor Qwertie
1

Das problem ist, dass ein Wörterbuch/hash-Tabelle ist entworfen, um eine einzigartige Position im Speicher basierend auf einer Eingabe-Wert, so müssen Sie eine Daten-Struktur, die entworfen, um Platz für eine Reihe in Verbindung mit jedem Wert, den Sie speichern, und zur gleichen Zeit aktualisieren, jedes Intervall richtig

Ich denke skip-Listen (oder ausgeglichene binäre Bäume) kann Ihnen helfen. Obwohl Sie nicht zum durchführen von suchen in O(n), die Sie tun können, logarithmisch und immer noch schneller als Bäume.

Ich weiß, das ist keine richtige Antwort, da kann ich nicht sagen, dass die .NET BCL enthält bereits eine solche Klasse, Sie haben leider zu implementieren, die eine sich selbst, oder finden Sie eine 3rd-party-assembly, die Sie unterstützen, für Sie. Es scheint ein schönes Beispiel über bei Der CodeProject hier, obwohl.
- SortedDictionary zu sein scheint, werden mit einer rot-schwarz-Baum; schade, nicht alle seine Fähigkeiten öffentlich gemacht werden.
InformationsquelleAutor Cecil Has a Name

Können Sie versuchen, den code, den ich schrieb unten. es unter Verwendung der binären Suche, daher vorausgesetzt, die Liste/array vorsortiert.

public static class ListExtensions
{
    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtMostIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtLeastIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; // /2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult <= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex - 1;

                if (returnIndex < index)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            //todo: test
            return startIndex - 1;
        }
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; // /2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult >= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex + 1;

                if (returnIndex >= index + count)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            return endIndex + 1;
        }
    }
}

Vielen Dank für den Beitrag dieser binäre Suche Algorithmus, aber es wäre nicht mein problem gelöst, denn es erfordert ein sortiertes array. In meinem Szenario (sorry für die nicht klar in der Frage), Schlüssel-Einsätze werden interleaved mit key-Abfragen. Beibehaltung der Sortierreihenfolge eines Arrays auf JEDER einfügen (so, dass die binäre Suche möglich) erfordert O(N) Zeit. Also, ein array, sortiert nach dem key würde nicht haben eine gute Leistung. Nun, wenn das array gebaut werden konnte im Voraus, und dann folgt eine Reihe von Abfragen, Sortieren müsste nur einmal gemacht werden, das wäre effizient. Aber das war keine option für mich.

InformationsquelleAutor DxCK

1

Erstellte ich drei Daten-Strukturen in Bezug auf B+ - Bäume, die diese Funktionalität bieten, die für einen beliebigen Datentyp: BList<T>, BDictionary<K V> und BMultiMap<K V>. Jede dieser Datenstrukturen bieten FindLowerBound() und FindUpperBound() Methoden wie etwa C++'s lower_bound und upper_bound.

InformationsquelleAutor Qwertie

finden, die am nächsten zu K:

dict.Keys.Where(i => i >= K).OrderBy(i => i).First();

oder viel schneller:

public int? GetNearestKey(dict, K) 
{
    int? lowerK = null;
    foreach (int key in dict.Keys)
    {
        if (key == K) 
        {
            lowerK = K;
            break; 
        }
        else if (key >= K && (!lowerK.HasValue || key < lowerK))
        {
            lowerK = key;
        }
    }
    return lowerK;
}

äh... jetzt ist es aus O(n) O(n log n).
Ich muss es tun in O(log n). Theoretisch SortedDictionary ist in der Lage, dies zu tun, aber ich sehe nicht ein API für es.

InformationsquelleAutor manji

0

Gibt es nicht eine binäre Suchbaum collection Implementierung in der Basis-framework, so werden Sie entweder bauen oder finden eine Implementierung. Wie Sie bemerkt haben, SortedList am nächsten ist, in Bezug auf die Suche aber er ist langsamer (wegen seiner zugrunde liegenden array-Implementierung) für einfügen/löschen.
- SortedDictionary IST ein binärer Suchbaum. Die öffentliche API lässt sich die Suche Funktionalität.
InformationsquelleAutor Joe
0

Ich denke, es ist ein Fehler in der Frage über SortedList Komplexität.

SortedList hat O(log(n)) amortisierten Komplexität für einfügen neues Element. Wenn Sie im Voraus wissen, die Kapazität es kann durchgeführt werden in O(Log(n)) im schlechtesten Fall.
- Microsoft dummerweise nicht die big-O Komplexität in der Dokumentation ( msdn.microsoft.com/en-us/library/...), aber es scheint zu implizieren, dass die SortedList speichert die Schlüssel und Werte in arrays. Sortierte arrays O(N) insert Komplexität, wenn die Schlüssel eingefügt werden, ist zufällig.
- Es tut, in msdn.microsoft.com/en-us/library/... heißt es: "Diese Methode ist eine O(n) - operation für unsortierte Daten, wobei n für die Anzahl. Es ist eine O(log n) - operation, wenn das neue element wird Hinzugefügt am Ende der Liste. Wenn die insertion bewirkt eine Größe, die operation ist O(n)."
- Unsortierte Daten ist normal. Wenn Ihre Daten bereits sortiert sind, müssen Sie nicht SortedList in den ersten Platz (List<T> hat eine BinarySearch Methode.) Also Ihre Behauptung, dass "SortedList hat O(log(n)) amortisierten Komplexität" ist schlicht falsch.
InformationsquelleAutor Elisha

Können Sie für SortedSet<T> mit folgenden extension Methoden:

public static class SortedSetExtensions
{
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if(set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var minimum = set.Min;

        if(set.Comparer.Compare(minimum, value) > 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(minimum, value).Max;
        return true;
    }

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if (set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var maximum = set.Max;

        if (set.Comparer.Compare(maximum, value) < 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(value, maximum).Min;
        return true;
    }
}

InformationsquelleAutor ghord

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.