Welche .NET-Wörterbuch unterstützt eine „nearest Schlüssel finden“ Betrieb?

Question

ich einige C ++ Code zu C # konvertieren und es ruft std :: map :: lower_bound (k) einen Eintrag in der Karte, deren Schlüssel zu finden, ist gleich oder größer als k. Aber ich sehe jede mögliche Weise nicht die gleiche Sache mit .NET ist SortedDictionary zu tun. Ich vermute, ich könnte eine Problemumgehung implementieren SortedList verwenden, aber leider SortedList ist zu langsam (O (n) zum Einfügen und Löschen von Schlüsseln). Was kann ich tun?

Hinweis: Ich fand eine Abhilfe mit diesem Vorteil von meinem speziellen Szenario nimmt ... Insbesondere meine Schlüssel sind eine dichte Population von ganzen Zahlen bei knapp über 0 beginnen, so habe ich eine Liste als meinen Wörterbuch mit der Liste Index dient als Schlüssel, und suchen nach einem Schlüssel gleich oder größer als k kann in nur wenigen Schleifeniterationen erfolgen. Aber es wäre noch schön, die ursprüngliche Frage beantwortet zu sehen.

Answer 1

Ich habe drei Datenstrukturen B im Zusammenhang + Bäume, die diese Funktionalität für jeden Datentyp bieten: BList<T>, BDictionary<K,V> und BMultiMap<K,V> . Jede dieser Datenstrukturen bieten FindLowerBound() und FindUpperBound() Methoden, die wie C ++ 's lower_bound und upper_bound arbeiten.

Answer 2

Es dauerte ein paar Monate Arbeit, aber schließlich kann ich zumindest eine Teillösung für dieses Problem bieten ... Ich nenne es die Compact Patricia Trie, eine sortierte Wörterbuch, das einen „finden nächst größeren Schlüssel“ -Betrieb bietet.

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

Es ist nur eine Teillösung, da nur bestimmte Arten von Schlüsseln unterstützt werden, nämlich byte[], string, und alle primitiven Integer-Typen (Int8..UInt64). Auch String Sortierung wird die Groß- und Kleinschreibung.

Answer 3

Das Problem ist, dass ein Wörterbuch / Hash-Tabelle ausgelegt ist, an einem einzigartigen Speicherplatz auf einem Eingangswert auf Basis ankommen, so dass Sie eine Datenstruktur benötigen, die Sie speichern, verwandt wurde entwickelt, um jeden Wert einen Bereich zur Aufnahme und zur gleichen Zeit richtig jedes Intervall aktualisieren

Ich denke, Listen überspringen (oder ausgeglichen Binärbäumen) kann Ihnen helfen. Obwohl sie nicht Lookups in O (n) durchführen können, was sie tun können logarithmisch und immer noch schneller als Bäume.

Ich weiß, das ist keine richtige Antwort, da ich nicht, dass die .NET BCL bereits eine solche Klasse sagen kann, enthält, werden Sie leider ein selbst implementieren müssen, oder eine 3rd-Party-Versammlung finden, dass es für Sie unterstützt. Es scheint noreferrer"> The Codeproject hier ein schönes Beispiel über

Sie können versuchen, den Code i unten geschrieben. es binäre Suche, damit die Liste der Annahme / Array ist 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;
        }
    }
}

finden am nächsten 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;
}

Es gibt keine binäre Suchbaum Sammlung Umsetzung im Basisrahmen, so dass Sie entweder einen bauen oder eine Implementierung zu finden. Wie Sie bemerkt, ist SortedList bei der Durchsuchung am nächsten ist aber langsamer (aufgrund seiner zugrunde liegenden Array-Implementierung) für Einfügen / Löschen.

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

SortedList hat O (log (n)) abgeschrieben Komplexität Einfügen Neuteil. Wenn Sie wissen, die Kapazität im Voraus kann es in O (log (n)) im schlechtesten Fall durchgeführt werden.

Sie können dies mit folgenden Erweiterungsmethoden für SortedSet<T> tun:

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;
    }
}

Answer 4

Answer 5

Answer 6

Sie können versuchen, den Code i unten geschrieben. es binäre Suche, damit die Liste der Annahme / Array ist 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;
        }
    }
}

Answer 7

finden am nächsten 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;
}

Es gibt keine binäre Suchbaum Sammlung Umsetzung im Basisrahmen, so dass Sie entweder einen bauen oder eine Implementierung zu finden. Wie Sie bemerkt, ist SortedList bei der Durchsuchung am nächsten ist aber langsamer (aufgrund seiner zugrunde liegenden Array-Implementierung) für Einfügen / Löschen.

Answer 8

finden am nächsten 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;
}

Answer 9

Es gibt keine binäre Suchbaum Sammlung Umsetzung im Basisrahmen, so dass Sie entweder einen bauen oder eine Implementierung zu finden. Wie Sie bemerkt, ist SortedList bei der Durchsuchung am nächsten ist aber langsamer (aufgrund seiner zugrunde liegenden Array-Implementierung) für Einfügen / Löschen.

Answer 10

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

SortedList hat O (log (n)) abgeschrieben Komplexität Einfügen Neuteil. Wenn Sie wissen, die Kapazität im Voraus kann es in O (log (n)) im schlechtesten Fall durchgeführt werden.

Answer 11

Answer 12

Answer 13

Ich denke, es ist ein Fehler in der Frage über

Answer 14

Sie können dies mit folgenden Erweiterungsmethoden für SortedSet<T> tun:

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;
    }
}