Lo diccionario .NET soporta una operación de “encontrar la clave más cercano”?

Question

Me estoy convirtiendo poco de código C ++ a C # y se llama std :: Mapa :: límite distinto (k) para encontrar una entrada en el mapa cuya clave es igual o mayor que k. Sin embargo, yo no veo ninguna manera de hacer lo mismo con SortedDictionary de .NET. Sospecho que pude poner en práctica una solución utilizando SortedList, pero desafortunadamente SortedList es demasiado lento (O (n) para la inserción y eliminación de claves). ¿Qué puedo hacer?

Nota: He encontrado una solución que aprovecha el uso de mi escenario particular ... En concreto, las llaves son una población densa de números enteros a partir de poco más de 0, por lo que utilizó una lista como mi diccionario con la lista índice que sirve de clave, y la búsqueda de una clave igual o mayor que k se puede hacer en sólo unas pocas iteraciones del bucle. Pero aún sería agradable ver la pregunta original contestado.

Answer 1

He creado tres estructuras de datos relacionados con B + árboles que proporcionan esta funcionalidad para cualquier tipo de datos: BList<T>, BDictionary<K,V> y BMultiMap<K,V> . Cada una de estas estructuras de datos proporcionan FindLowerBound() y FindUpperBound() métodos que funcionan como lower_bound y upper_bound C ++ 's.

Answer 2

Se tomó un par de meses de trabajo, pero al final me puede ofrecer al menos una solución parcial a este problema ... Yo lo llamo el compacto Patricia Trie, un diccionario ordenada que ofrece una "mayor siguiente encontrar la clave" la operación.

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

Es sólo una solución parcial, ya que sólo ciertos tipos de claves son compatibles, es decir, byte[], string, y todos los tipos de enteros primitivos (Int8..UInt64). Además, la clasificación de la cadena entre mayúsculas y minúsculas.

Answer 3

El problema es que una tabla de diccionario / de hash está diseñado para llegar a una posición de memoria único basado en un valor de entrada, por lo que tendrá una estructura de datos que está diseñado para dar cabida a una serie relacionada con cada valor a almacenar, y al mismo tiempo actualizar cada intervalo correctamente

saltar listas (o árboles binarios equilibrados) puede ayudar. Aunque no pueden realizar búsquedas en O (n), que pueden hacer de forma logarítmica y aún más rápido que los árboles.

Sé que esto no es una respuesta adecuada ya que no puedo decir que el .NET BCL ya contiene dicha clase, se le lamentablemente tiene que implementar uno mismo, o encontrar una tercera asamblea del partido que lo apoya para usted. Parece que hay un buen ejemplo a través de la página El CodeProject aquí , sin embargo.

Answer 4

Puede probar el código que he escrito a continuación. que mediante la búsqueda binaria, por lo tanto, suponiendo que la lista / matriz es pre-ordenadas.

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 5

encuentre más cercana a K:

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

o mucho más rápido:

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 6

No es un binario implementación de la colección árbol de búsqueda en el marco de base, por lo que usted o bien tienen que construir uno o encontrar una aplicación. Como se anotó, SortedList es más cercano en términos de la búsqueda, pero es más lento (debido a su aplicación matriz subyacente) para la inserción / deleción.

Answer 7

Creo que hay un error en la pregunta sobre SortedList complejidad.

SortedList tiene O (log (n)) amortizado complejidad para insertar nuevo elemento. Si usted sabe de antemano la capacidad que se puede hacer en O (log (n)) en el peor de los casos.

Answer 8

Puede hacer esto para SortedSet<T> con los siguientes métodos de extensión:

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