Улучшение времени доступа к SortedDictionary

Question

У меня есть 2 миллиона предметов в SortedDictionary<string, MyClass>

Я сделал следующее, и у меня есть возраст, есть идеи?

for(int i = 0; i<dic.Count-1; i++)
{
    Debug.WriteLine(dic.ElementAt(i).Value.ToString());
}

Answer 1

Класс SortedDictionary<TKey, TValue> напрямую не поддерживает (быстрый) поиск по индексу;это внутренне реализовано как двоичное дерево поиска.Следовательно, при каждом вызове полученного вами метода LINQ Enumerable.ElementAt создается новый перечислитель, который выполняет итерацию каждого значения последовательности, представленной парами ключ-значение в коллекции (отсортировано по ключу) с начала * 1008.* пока не достигнет желаемого индекса.Это означает, что цикл должен будет тянуть что-то вроде 1 + 2 + 3 + ... + Count (примерно 2 триллиона) элементов до завершения, что делает его (по крайней мере) квадратичным по своей временной сложности.

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

foreach(var myClass in dic.Values)
   Debug.WriteLine(myClass);

Если вы действительно хотите быстрый доступ по индексу (из предоставленного кода, кажется, нетпричина указать это), рассмотрите возможность использования SortedList<TKey, TValue>.У этого выбора есть свои недостатки (более медленные не добавляемые и удаляемые вставки), которые вы должны оценить.

Я также заметил, что условие цикла - i < dic.Count - 1, а не более распространенное i < dic.Count.Это либо ошибка в отдельности, либо, возможно, вы намереваетесь не учитывать последнее значение в словаре.В последнем случае вы можете поддерживать локальную переменную, служащую счетчиком, или с помощью LINQ:

foreach(var myClass in dic.Values.Take(dic.Count - 1))
   Debug.WriteLine(myClass);

Answer 2

foreach может быть быстрее, так как вы не используете индексатор

foreach (var value in dic.Values)
   Debug.Writeline(value)

Кроме того, что касается скорости, Debug.Writeline, вероятно, не лучший вариант (что вы будете делать с 2 миллионами записей трассировки отладки в любом случае ??). Рассмотрите возможность записи в файл, базу данных и т. Д.

РЕДАКТИРОВАТЬ Глядя на отражатель, поиск значения в SortedDictionry сводится к двоичному поиску:

internal virtual Node<T> FindNode(T item)
{
    int num;
    for (Node<T> node = this.root; node != null; node = (num < 0) ? node.Left : node.Right)
    {
        num = this.comparer.Compare(item, node.Item);
        if (num == 0)
        {
            return node;
        }
    }
    return null;
}

Реализация итерации SortedDictionary кажется немного более сложной:

public bool MoveNext()
{
    this.tree.VersionCheck();
    if (this.version != this.tree.version)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }
    if (this.stack.Count == 0)
    {
        this.current = null;
        return false;
    }
    this.current = this.stack.Pop();
    SortedSet<T>.Node item = this.reverse ? this.current.Left : this.current.Right;
    SortedSet<T>.Node node2 = null;
    SortedSet<T>.Node node3 = null;
    while (item != null)
    {
        node2 = this.reverse ? item.Right : item.Left;
        node3 = this.reverse ? item.Left : item.Right;
        if (this.tree.IsWithinRange(item.Item))
        {
            this.stack.Push(item);
            item = node2;
        }
        else
        {
            if ((node3 == null) || !this.tree.IsWithinRange(node3.Item))
            {
                item = node2;
                continue;
            }
            item = node3;
        }
    }
    return true;
}

Кажется, он поддерживает стек, верхний элемент которого является наименьшим (или самым большим, в зависимости от направления) и, таким образом, всегда тот, который должен быть извлечен и возвращен во время итерации. Я не делал никакого анализа сложности, но он должен быть значительно эффективнее, чем каждый раз выполнять бинарный поиск.

Answer 3

Использование foreach:

    foreach (var pair in d)
        Debug.WriteLine(pair.Value);

Могу поспорить, что вывод отладки занимает больше времени, чем поиск по словарю.