Почему Словарь. Сначала () настолько медленный?
Не реальный вопрос, потому что я уже узнал ответ, но все еще интересную вещь.
Я всегда думал, что хеш-таблица является самым быстрым ассоциативным контейнером, если Вы хешируете правильно.
Однако следующий код является ужасно медленным. Это выполняет только приблизительно 1 миллион повторений и занимает больше чем 2 минуты времени на Core 2 ЦП.
Код делает следующее: это поддерживает набор todo из объектов это должно обработать. При каждом повторении это берет объект от этого набора (не имеет значения, какой объект), удаляет его, процессы он, если это не было обработано (возможно добавляющий больше объектов для обработки) и повторяет это, пока нет никаких объектов для обработки.
Преступник, кажется, Словарь. Ключи. Сначала () операция.
Вопрос состоит в том, почему это медленно?
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().
5 ответов
Словарь поддерживает хеш-таблицу.
Его перечислитель будет перебирать сегменты в хеш-таблице до тех пор, пока не найдет непустое ведро, а затем вернет значение в этом сегменте.
Как только словарь увеличивается, эта операция становится дорогостоящей.
Кроме того, удаление элемента из словаря не сжимает массив сегментов, поэтому вызов First () становится на медленнее по мере удаления элементов. (Потому что для поиска непустого ведра необходимо выполнить цикл дальше)
Следовательно, многократный вызов First () и удаление - это O (n 2 ).
Кстати, вы можете избежать поиска значений следующим образом: (Это не сделает его заметно быстрее)
var kvp = todo.First();
//Use kvp.Key and kcp.Value
Ну, хэш-таблицы не сортируются, я предполагаю, что он должен сделать какую-то сортировку, прежде чем он сможет сделать итерацию, или какое-то сканирование, если он уже отсортирован, он может просто перебирать.
Reflector показывает, что Dictionary поддерживает массив Entry, который используется KeyCollection. Обычно поиск должен быть относительно быстрым, поскольку можно просто индексировать массив (предполагая, что вам не нужен отсортированный 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 в следующий раз становится медленнее.
Не глядя, простейшая реализация сортированного словаря - это сортированный список (типа TreeSet) ключей и объединенный хэш; список дает вам упорядочение, словарь - значения. Таким образом, ключи уже доступны. Hashtable не имеет легкодоступных ключей, поэтому виновником является не first, а keys (все без каких-либо доказательств, не стесняйтесь проверить гипотезу ;D )
Словарь не предпринимает никаких усилий для отслеживания списка ключей. Поэтому итератор должен пройтись по ведрам. Многие из этих ведер, особенно для большого словаря, могут ничего в них не содержать.
Может быть полезно сравнить HashIterator.nextEntry и PrivateEntryIterator.nextEntry (который использует TreeMap.successor) OpenJDK. Версия хэша обходит неизвестное количество записей в поисках той, которая не является нулевой. Это может быть особенно медленным, если из хэш-таблицы было удалено много элементов (что и произошло в вашем случае). В TreeMap единственное, что мы делаем, это обход в порядке возрастания. На этом пути нет нулей (только в листьях).