Почему Dictionary.First () такой медленный?

Question

Не реальный вопрос, потому что я уже нашел ответ, но все же интересная вещь.

Я всегда думал, что хеш-таблица - это самый быстрый ассоциативный контейнер, если вы правильно хешируете.

Однако следующий код ужасно медленный.Он выполняет только около 1 миллиона итераций и занимает более 2 минут времени на процессоре Core 2.

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

Похоже, виновником является операция Dictionary.Keys.First ().

Вопрос в том, почему он медленный?

Stopwatch watch = new Stopwatch();
watch.Start();

HashSet<int> processed = new HashSet<int>();
Dictionary<int, int> todo = new Dictionary<int, int>();

todo.Add(1, 1);
int iterations = 0;

int limit = 500000;
while (todo.Count > 0)
{
    iterations++;
    var key = todo.Keys.First();
    var value = todo[key];
    todo.Remove(key);
    if (!processed.Contains(key))
    {
        processed.Add(key);
        // process item here
        if (key < limit) { todo[key + 13] = value + 1; todo[key + 7] = value + 1; }
        // doesn't matter much how
    }
}
Console.WriteLine("Iterations: {0}; Time: {1}.", iterations, watch.Elapsed);

В результате:

Iterations: 923007; Time: 00:02:09.8414388.

Простое изменение словаря на SortedDictionary приводит к:

Iterations: 499976; Time: 00:00:00.4451514.

в 300 раз быстрее, при этом итераций всего в 2 раза меньше.

То же самое происходит в Java.Используется HashMap вместо Dictionary и keySet().iterator().next() вместо Keys.First().

Answer 1

Dictionary<TKey, TValue> поддерживает хэш-таблицу.

Его перечислитель будет перебирать сегменты в хэш-таблице до тех пор, пока не найдет непустую область, а затем вернет значение в этой области. Как только словарь становится большим, эта операция становится дорогой.
Кроме того, удаление элемента из словаря не сокращает массив сегментов, поэтому вызов First() замедляет 1008 * при удалении элементов. (Потому что он должен пройти дальше, чтобы найти непустое ведро)

Следовательно, повторный вызов First() и удаление - это O (n ² ).

---

Кстати, вы можете избежать поиска значения следующим образом: (Это не сделает его заметно быстрее)

var kvp = todo.First();

//Use kvp.Key and kcp.Value

Answer 2

Словарь не прилагает усилий, чтобы отслеживать список ключей. Таким образом, итератор должен пройтись по блокам. Многие из этих блоков, особенно для большого словаря, во многих ничего нет.

Может быть полезно сравнить OpenJDK HashIterator.nextEntry и PrivateEntryIterator.nextEntry (который использует TreeMap.successor). Хеш-версия обходит неизвестное количество записей, ища ненулевое значение. Это может быть особенно медленным, если в хеш-таблице было удалено много элементов (что в вашем случае). В TreeMap единственная прогулка, которую мы делаем, это наш обход в порядке. На пути нет нулей (только на листьях).

Answer 3

Отражатель показывает, что Dictionary<TKey, TValue> поддерживает массив Entry<TKey, TValue>, который используется KeyCollection<TKey, TValue>.Enumerator<TKey, TValue>.Обычно поиск должен быть относительно быстрым, поскольку он может просто индексироваться в массив (при условии, что вы не хотите сортировать First):

// Dictionary<TKey. TValue>
private Entry<TKey, TValue>[] entries;

Однако , если выудаляя первые элементы этого массива, вы в конечном итоге обойдете массив, пока не найдете непустой:

// Dictionary<TKey, TValue>.KeyCollection<TKey, TValue>.Enumerator<TKey, TValue>
while (this.index < this.dictionary.count) {
    if (this.dictionary.entries[this.index].hashCode >= 0) {
        this.currentKey = this.dictionary.entries[this.index].key;
        this.index++;
        return true;
    }
    this.index++;
}

Когда вы удаляете свои записи, вы начинаете получать все больше и больше пустыхперед массивом entries, и в следующий раз становится медленнее извлекать First.

Answer 4

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

Answer 5

Не глядя, самая простая реализация отсортированного словаря - это отсортированный список (например, TreeSet) ключей и объединенный хэш; список дает вам порядок, словарь дает вам значения. Таким образом, ключи уже доступны. У Hashtable нет доступных ключей, поэтому виновник не first, а keys (все без малейших доказательств, не стесняйтесь проверять гипотезу; D)