Что словарь.NET поддерживает, “находят ближайшую ключевую” операцию?

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

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

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

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

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

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

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

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

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

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

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

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

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