Какой словарь .NET поддерживает операцию «найти ближайший ключ»?

Question

Я конвертирую некоторый код C++ в C#, и он вызывает std::map::lower_bound(k), чтобы найти на карте запись, ключ которой равен или больше k.Однако я не вижу способа сделать то же самое с SortedDictionary .NET.Я подозреваю, что мог бы реализовать обходной путь, используя SortedList, но, к сожалению, SortedList слишком медленный (O(n) для вставки и удаления ключей).Что я могу сделать?

Примечание:Я нашел обходной путь, который использует мой конкретный сценарий...В частности, мои ключи представляют собой плотную совокупность целых чисел, начиная с чуть больше 0, поэтому я использовал List<TValue> в качестве словаря с индексом списка, служащим ключом, и поиск ключа, равного или большего, чем k, можно выполнить в всего несколько итераций цикла.Но все равно было бы неплохо увидеть ответ на исходный вопрос.

Answer 1

Я создал три структуры данных, связанные с деревьями B+, которые обеспечивают эту функциональность для любого типа данных: BList<T>, BDictionary<K,V> и BMultiMap<K,V>.Каждая из этих структур данных предоставляет FindLowerBound() и FindUpperBound() методы, которые работают как C++ lower_bound и upper_bound.

Answer 2

Работа заняла пару месяцев, но наконец я могу предложить хотя бы частичное решение этой проблемы...Я называю его Compact Patricia Trie, отсортированным словарем, предлагающим операцию «найти следующий больший ключ».

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

Это лишь частичное решение, поскольку поддерживаются только определенные виды ключей, а именно: byte[], string, и все примитивные целочисленные типы (Int8..UInt64).Кроме того, сортировка строк чувствительна к регистру.

Answer 3

Проблема в том, что словарь/хеш-таблица спроектирована так, чтобы попадать в уникальную ячейку памяти на основе входного значения, поэтому вам понадобится структура данных, предназначенная для размещения диапазона, связанного с каждым хранимым вами значением, и в то же время время обновляет каждый интервал правильно

Я думаю пропускать списки (или сбалансированные бинарные деревья) могут вам помочь.Хотя они не могут выполнять поиск за O(n), они могут делать это логарифмически и при этом быстрее, чем деревья.

Я знаю, что это неправильный ответ, поскольку я не могу сказать, что .NET BCL уже содержит такой класс; к сожалению, вам придется реализовать его самостоятельно или найти стороннюю сборку, которая его поддерживает.Кажется, есть хороший пример на Кодпроект здесь, хотя.

Answer 4

Вы можете попробовать код, который я написал ниже.он использует двоичный поиск, поэтому предполагается, что список/массив предварительно отсортирован.

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

найти ближайший к К:

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

или намного быстрее:

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

В базовой платформе нет реализации коллекции двоичных деревьев поиска, поэтому вам придется либо создать ее, либо найти реализацию.Как вы заметили, SortedList наиболее близок с точки зрения поиска, но медленнее (из-за реализации базового массива) для вставки/удаления.

Answer 7

Я думаю, что есть ошибка в вопросе о Сортированный список сложность.

Сортированный список имеет амортизированную сложность O(log(n)) для вставка новый предмет.Если вы заранее знаете мощность, в худшем случае это можно сделать за O(Log(n)).

Answer 8

Вы можете сделать это для SortedSet<T> со следующими методами расширения:

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