Лучший способ проверить содержимое общего списка
Мне нужно поработать над кодом, который использует общие списки для хранения коллекции настраиваемых объектов.
Затем он выполняет что-то вроде следующего, чтобы проверить, есть ли данный объект в коллекции, и если это так, что-то сделать:
List<CustomObject> customObjects;
//fill up the list
List<CustomObject> anotherListofCustomObjects;
//fill it up
//...
foreach (CustomObject myCustomObject in customObjects)
{
if (anotherListofCustomObjects.Contains(myCustomObject))
{
//do stuff
}
}
Проблема в том, что на обработку 7000 таких объектов уходит вечность.
Это не мой код - я просто пытаюсь придумать варианты его улучшения - Мне кажется, было бы намного быстрее использовать словарь, чтобы получить материал по ключу, вместо того, чтобы перебирать всю коллекцию, как показано выше.
Предложения?
Ответы 8
Ну вроде вы сами ответили? Если вам нужен быстрый запрос к набору данных, тогда словарь может быть лучше, чем плоский список (для больших размеров данных, как у вас).
Вы можете, например, использовать объект как свой собственный ключ -
Dictionary<CustomObject,CustomObject> ...
Обратите внимание, что значение равенства зависит от контекста. Если вы передаете исходную ссылку, то ничего страшного - ContainsKey справится с этой задачей. Если у вас есть объект разные, но похожие для целей равенства для сравнения, тогда вам необходимо реализовать свои собственные GetHashCode(), Equals() и, в идеале, IEquatable<CustomObject>. Либо в самом CustomObject, либо в кастомном IEqualityComparer<CustomObject>.
Использование объекта в качестве ключа к объекту - это ничто иное, как использование самого объекта, чтобы найти себя, как версия списка в исходном сообщении. Ключ словаря должен быть меньшим по размеру и более простым для обработки, чем элемент значения.
@BeowulfOF нет, это не так. Использование объекта в качестве ключа быстрее, потому что вы можете использовать тот же объект (из другого списка), чтобы проверить, есть ли он в словаре.
@BeowulfOF - это просто ссылка. Конечно, вы может используете отдельный ключ, но это не обязательно. Производительность зависит в первую очередь от сложности Equals и GetHashCode, независимо от того, является ли это ключом объекта или естественным ключом.
Действительно, ваш код в настоящее время O (n ^ 2), что будет медленным. Ты можешь:
- используйте словари или KeyedCollections вместо этого, это сделает его O (nlog n)
- если вы можете гарантировать, что элементы находятся в одном порядке, вы можете переписать последний цикл, чтобы использовать только один индекс, и это будет O (n)
Другой способ, помимо словарей, - если вы используете .NET 3.5, использовать Linq для объектов и Intersect:
foreach(CustomObject c in customObjects.Intersect(anotherListOfCustomObjects))
{
// do stuff.
}
Согласно рефлектору, он использует наборы на основе хэша для пересечения последовательностей.
Да, это лучше, потому что он выполняет поиск набора в экземплярах Set <T> на основе хэша (который является внутренним классом).
Производительность от этого не выиграет, даже если это будет медленнее. Linq в основном предназначен только для лучшего понимания, но не для повышения производительности.
@BeowulfOF: вы проверяли код? :) См. Мой предыдущий комментарий. Конечно, если бы «Пересечение» было реализовано с использованием алгоритма O (n * m), как в вопросе, это было бы то же самое, но, к счастью, это не так.
Кстати, я рассчитал это с помощью простых списков int, и это действительно намного быстрее.
Если вы должен поддерживаете два отдельных списка, один из типов Set может быть быстрее (с использованием операции соединения). Некоторые из доступных библиотек
Просто незначительное дополнение к другим комментариям. Если вам нужно отсортировать другой список клиентов, вы можете использовать SortedList.
Тесты - твой друг. Размер коллекции определяет структуру данных / алгоритм, который вы должны использовать. Я предлагаю вам провести несколько тестов производительности для следующих опций:
- Ваше текущее решение
- Используйте алгоритм
BinarySearchв отсортированном списке. - Используйте
HashSet<CustomObject>.
Учитывая количество элементов, я подозреваю, что HashSet<CustomObject> - это то, что вам нужно.
Хешсет тоже отлично работает.
new HashSet<CustomObject>().Join()
Проблема с перфомансом предполагает, что вам нужно искать альтернативные алгоритмы или структуры данных. Как ты сам сказал.