Может кто-нибудь объяснить мне, почему функция generics List.Contains() такая медленная?
У меня List<long> около миллиона номеров, и код, который постоянно проверяет, есть ли конкретное число в этих числах.
Я попытался сделать то же самое, используя Dictionary<long, byte> и функцию Dictionary.ContainsKey(), и это было примерно в 10-20 раз быстрее, чем со списком.
Конечно, я не хочу использовать словарь для этой цели, потому что он не предназначен для этого.
Таким образом, реальный вопрос здесь заключается в том, есть ли альтернатива List<T>.Contains(), но не такая странная, как Dictionary<K,V>.ContainsKey()?
Если вы просто проверяете существование, HashSet<T> в .NET 3.5 - ваш лучший вариант - производительность, подобная словарю, но не пара ключей/значений - только значения:
HashSet<int> data = new HashSet<int>();
for (int i = 0; i < 1000000; i++)
{
data.Add(rand.Next(50000000));
}
bool contains = data.Contains(1234567); // etc
List.Contains - это операция O (n).
Dictionary.ContainsKey - это операция O (1), поскольку она использует хэш-код объектов в качестве ключа, что дает вам более быструю возможность поиска.
Я не думаю, что неплохо иметь Список, содержащий миллион записей. Я не думаю, что класс List был разработан для этой цели.:)
Возможно ли сохранить эти миллионные объекты в RDBMS, например, и выполнить запросы в этой базе данных?
Если это невозможно, я все равно буду использовать словарь.
Думаю, у меня есть ответ! Да, верно, что Contains() в списке (массиве) является O (n), но если массив короток и вы используете типы значений, он все равно должен быть довольно быстрым. Но используя CLR Profiler [бесплатную загрузку с Microsoft], я обнаружил, что Contains() - это значения бокса, чтобы сравнить их, что требует распределения кучи, которое ОЧЕНЬ дорого (медленно). [Примечание: это .Net 2.0; другие .Net-версии не тестировались.]
Вот полная история и решение. Мы имеем перечисление под названием "VI" и создали класс "ValueIdList", который является абстрактным типом для списка (массива) объектов VI. Первоначальная реализация была в древнем .Net 1.1 дня, и она использовала инкапсулированный ArrayList. Недавно мы обнаружили http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx, что общий список (List <VI> ) работает намного лучше, чем ArrayList в типах значений (например, наше перечисление VI), потому что значения don ' t должен быть помещен в коробку. Это правда, и это сработало... почти.
Профайлер CLR показал удивление. Здесь часть графика распределения:
Как вы можете видеть, Contains() неожиданно вызывает Generic.ObjectEqualityComparer.Equals(), который, по-видимому, требует бокса значения VI, что требует дорогого распределения кучи. Странно, что Microsoft устранит бокс в списке, только чтобы потребовать его снова для простой операции, такой как это.
Нашим решением было переписать реализацию Contains(), что в нашем случае было легко сделать, поскольку мы уже инкапсулировали общий объект списка (_items). Вот простой код:
public bool Contains(VI id)
{
return IndexOf(id) >= 0;
}
public int IndexOf(VI id)
{
int i, count;
count = _items.Count;
for (i = 0; i < count; i++)
if (_items[i] == id)
return i;
return -1;
}
public bool Remove(VI id)
{
int i;
i = IndexOf(id);
if (i < 0)
return false;
_items.RemoveAt(i);
return true;
}
Сравнение значений VI теперь выполняется в нашей собственной версии IndexOf(), которая не требует бокса, и это очень быстро. Наша специальная программа ускорилась на 20% после этой простой перезаписи. O (n)... не проблема! Просто избегайте использования использованной памяти!
Словарь не так уж плох, потому что ключи в словаре предназначены для быстрого поиска. Чтобы найти номер в списке, ему необходимо выполнить итерацию по всему списку.
Конечно, словарь работает только в том случае, если ваши номера уникальны и не упорядочены.
Я думаю, что в .NET 3.5 есть класс HashSet<T>, он также позволяет использовать только уникальные элементы.
A SortedList будет быстрее искать (но медленнее вставлять элементы)
Это не совсем ответ на ваш вопрос, но у меня есть класс, который увеличивает производительность Contains() в коллекции. Я подклассифицировал очередь и добавил словарь, который отображает хэш-коды в списки объектов. Функция Dictionary.Contains() - это O (1), тогда как List.Contains(), Queue.Contains() и Stack.Contains() - O (n).
Тип значения словаря - это объекты, содержащие объекты с одним и тем же хэш-кодом. Вызывающий может предоставить пользовательский объект класса, который реализует IEqualityComparer. Вы можете использовать этот шаблон для стеков или списков. Для этого кода потребуется всего несколько изменений.
/// <summary>
/// This is a class that mimics a queue, except the Contains() operation is O(1) rather than O(n) thanks to an internal dictionary.
/// The dictionary remembers the hashcodes of the items that have been enqueued and dequeued.
/// Hashcode collisions are stored in a queue to maintain FIFO order.
/// </summary>
/// <typeparam name="T"></typeparam>
private class HashQueue<T> : Queue<T>
{
private readonly IEqualityComparer<T> _comp;
public readonly Dictionary<int, Queue<T>> _hashes; //_hashes.Count doesn't always equal base.Count (due to collisions)
public HashQueue(IEqualityComparer<T> comp = null) : base()
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>();
}
public HashQueue(int capacity, IEqualityComparer<T> comp = null) : base(capacity)
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>(capacity);
}
public HashQueue(IEnumerable<T> collection, IEqualityComparer<T> comp = null) : base(collection)
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>(base.Count);
foreach (var item in collection)
{
this.EnqueueDictionary(item);
}
}
public new void Enqueue(T item)
{
base.Enqueue(item); //add to queue
this.EnqueueDictionary(item);
}
private void EnqueueDictionary(T item)
{
int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
Queue<T> temp;
if (!this._hashes.TryGetValue(hash, out temp))
{
temp = new Queue<T>();
this._hashes.Add(hash, temp);
}
temp.Enqueue(item);
}
public new T Dequeue()
{
T result = base.Dequeue(); //remove from queue
int hash = this._comp == null ? result.GetHashCode() : this._comp.GetHashCode(result);
Queue<T> temp;
if (this._hashes.TryGetValue(hash, out temp))
{
temp.Dequeue();
if (temp.Count == 0)
this._hashes.Remove(hash);
}
return result;
}
public new bool Contains(T item)
{ //This is O(1), whereas Queue.Contains is (n)
int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
return this._hashes.ContainsKey(hash);
}
public new void Clear()
{
foreach (var item in this._hashes.Values)
item.Clear(); //clear collision lists
this._hashes.Clear(); //clear dictionary
base.Clear(); //clear queue
}
}
Мое простое тестирование показывает, что мой HashQueue.Contains() работает намного быстрее, чем Queue.Contains(). Запуск тестового кода с числом, установленным в 10 000, занимает 0.00045 секунд для версии HashQueue и 0,37 секунды для версии Queue. С числом 100 000, версия HashQueue занимает 0.0031 секунды, тогда как Очередь занимает 36.38 секунд!
Здесь мой тестовый код:
static void Main(string[] args)
{
int count = 10000;
{ //HashQueue
var q = new HashQueue<int>(count);
for (int i = 0; i < count; i++) //load queue (not timed)
q.Enqueue(i);
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
bool contains = q.Contains(i);
}
sw.Stop();
Console.WriteLine(string.Format("HashQueue, {0}", sw.Elapsed));
}
{ //Queue
var q = new Queue<int>(count);
for (int i = 0; i < count; i++) //load queue (not timed)
q.Enqueue(i);
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
bool contains = q.Contains(i);
}
sw.Stop();
Console.WriteLine(string.Format("Queue, {0}", sw.Elapsed));
}
Console.ReadLine();
}
Почему словарь не подходит?
Чтобы узнать, находится ли конкретное значение в списке, вам нужно пройти весь список. Со словарем (или другим контейнером на основе хэша) гораздо быстрее сузить количество объектов, с которыми вам нужно сравнивать. Ключ (в вашем случае, число) хэшируется и дает словарю дробное подмножество объектов для сравнения.
Я использую это в Compact Framework, где нет поддержки для HashSet, я выбрал словарь, в котором обе строки - это значение, которое я ищу.
Это означает, что я получаю список < > функциональность со словарной производительностью. Это немного хаки, но это работает.