Производительность поиска C# HashSet‹T› (по сравнению с ObservableCollection‹T›)?

C# общая производительность поиска HashSet‹T> должна быть O(1), а производительность поиска ObservableCollection‹T> должна быть O(n).

У меня есть большое количество уникальных элементов, каждый элемент имеет свойство DateTime, которое не является уникальным.

Каждый элемент вычисляет свой HashCode, просто возвращая свой DateTime.GetHashCode().

Теперь я хочу получить подмножество моих данных, например. все элементы, имеющие дату между мартом 2012 г. и июнем 2012 г.

    var result = from p in this.Elements
                 where p.Date >= new DateTime(2012, 03, 01) &&
                       p.Date <= new DateTime(2012, 30, 06
                 select p;

Если я запускаю этот запрос LINQ для коллекции из 300 000 элементов, требуется ~25 мс, чтобы вернуть 80 элементов, которые находятся в заданном диапазоне — не имеет значения, использую ли я HashSet‹T> или ObservableCollection‹T>.

Если я перебираю все элементы вручную и проверяю их, это занимает то же время, ~ 25 мс.

Но я знаю HashCode всех дат, которые находятся в заданном диапазоне. Можно ли получить все элементы с заданными хэш-кодами из моего HashSet‹T>? Я думаю, так будет намного быстрее...

Можно ли ускорить запрос LINQ? Я предполагаю, что он не использует специальные возможности моего HashSet‹T>?


performance linq observablecollection hashset
person Ehssan    schedule 17.05.2012    source источник
comment
Является ли хэш-код каждого элемента его датой?   -  person Jodrell    schedule 17.05.2012
comment
У HashSet‹T› нет особых возможностей, позволяющих эффективно извлекать элементы, дата которых попадает в диапазон. HashSet позволяет быстро определить, входит ли конкретный объект или значение в набор (или нет).   -  person hatchet - done with SOverflow    schedule 17.05.2012
comment
Мое первое наблюдение заключается в том, что хеш-коды должны быть разными, если это возможно, если объекты различаются (это, безусловно, не всегда может быть так, но это то, к чему вы должны стремиться). В вашем случае это не так. У вас есть разные элементы с одинаковыми хэш-кодами, что плохо. В худшем случае, если у вас было только три разные уникальные даты, тогда ваш хеш-набор будет иметь только три сегмента, и поэтому поиск чего-либо в хэш-наборе должен будет отсортировать все элементы в этом сегменте, что приведет к O (n) (плюс-минус ). Также я должен отметить, что это общее замечание, не имеющее прямого отношения к вопросам :)   -  person Chris    schedule 17.05.2012
comment
О, и в качестве дополнительного примечания, это хеш-набор, о котором вы говорите, this.elements? Из вопроса непонятно...   -  person Chris    schedule 17.05.2012
comment
Если у вас есть 300 000 элементов, вы извлекаете их из базы данных? Если это так, вы можете получить только элементы в правильном диапазоне дат, что должно быть намного быстрее.   -  person jb.    schedule 17.05.2012
comment
Нет, элементы не из базы данных. Я просто спрашиваю, потому что производительность поиска в универсальном HashSet должна быть O(1), но запросы LINQ (и мои собственные запросы) выполняются за O(n). Да, и просто упомянем: очень мало элементов имеют одинаковый хэш-код...   -  person Ehssan    schedule 18.05.2012
comment
@EhssanDoust, как уже отмечалось, хотя вы не выполняете поиск по хэшу при выполнении запросов linq, вы просто выполняете поиск по IEnumerable и выполняете сравнение свойства Date (которое в вашем случае просто оказывается элементом, используемым для генерации хэша). Вы же понимаете, что HashSet не может получить элемент на основе хеша? См. это. Вам действительно нужно использовать другую структуру данных.   -  person Sam Holder    schedule 18.05.2012

Ответы (2)


arrow_upward
4
arrow_downward

Как уже отмечалось, набор хэшей очень эффективен при определении того, входит ли данный хэш в набор. Ваш запрос просто использует тот факт, что хэш-набор реализует IEnumerable для перебора всего набора и сравнения дат. Он вообще не будет использовать хэши. Вот почему ручной способ занимает столько же времени, сколько и запрос.

Вы не можете получить элемент на основе хэша из хеш-набора, вы можете только проверить существование элемента в наборе. Словарь — это то, что вам нужно, если вам нужно получить его с помощью has (что вроде нет)

Решите, что вам нужно делать с вашими данными, и используйте структуру, оптимизированную для этого. Это может быть ваш собственный класс, который поддерживает несколько внутренних структур, каждая из которых эффективна в чем-то одном (например, один для поиска диапазонов, а другой для проверки существования по нескольким полям), или может существовать существующая структура, которая соответствует вашим потребностям. Но, не зная, что вы хотите делать со своими данными, трудно советовать.

Еще одна вещь, которую следует учитывать, — оптимизируете ли вы преждевременно. Если 25 мс для поиска вручную достаточно быстро, то, возможно, любая структура, реализующая IEnumerable, будет достаточно хорошей. В этом случае вы можете выбрать один на основе других критериев, которые вам нужны.

person Sam Holder    schedule 18.05.2012
comment
Спасибо за ваш ответ. Я думаю, что текущей производительности поиска более чем достаточно, я просто подумал, что можно получить элементы напрямую по их хэш-коду, что, как вы указали, невозможно. Метод Remove из HashSet<T> гораздо более эффективен, чем тот, который предлагается любой обычной коллекцией, поэтому я обязательно буду использовать HashSet. - person Ehssan; 19.05.2012

arrow_upward
5
arrow_downward

Вы не используете правильную структуру данных. Вы должны использовать что-то вроде отсортированного списка (отсортированного по свойству Date), где вы можете затем выполнять двоичный поиск начала и конца диапазона.

person jason    schedule 17.05.2012
comment
Да, я бы определенно использовал SortedList или SortedDicionary, но я не могу - «Дата» элемента не является уникальным ключом... - person Ehssan; 18.05.2012
comment
@EhssanDoust, почему тот факт, что дата не уникальна, мешает вам использовать словарь? Пока метод Equals правильно определяет, когда 2 экземпляра равны, а gethashcode всегда возвращает одно и то же значение для 2 разных объектов, если равенство между этими объектами также верно, тогда он будет работать. - person Sam Holder; 18.05.2012
comment
@SamHolder Я не уверен, правильно ли я понимаю, что вы говорите, но если я хочу эффективно искать элемент по его дате с помощью словаря, ключ словаря должен быть этой датой, верно? Но в моей коллекции очень мало неуникальных дат... Значит, я не могу использовать их как ключи? - person Ehssan; 19.05.2012
comment
@EhssanDoust да, извините, ошибка понимания с моей стороны. Я забыл, что у тебя была только дата, а не полный объект. Отсортированный список должен быть в порядке, как предположил Джейсон, поскольку список может иметь несколько элементов с одним и тем же ключом. поэтому найдите индекс первого элемента с нужной датой, затем найдите индекс элемента с последней датой, затем получите все элементы между этими индексами. - person Sam Holder; 19.05.2012