List <T>FirstOrDefault () плохая производительность - возможен ли словарь в этом случае?

Question

У меня есть набор «кодов» Z, которые действительны в течение определенного периода времени.

Так как они мне нужны много раз в большом цикле (миллион +), и каждый раз, когда мне приходится искать соответствующий код, я кеширую их в List <>. После нахождения правильных кодов я вставляю (используя SqlBulkCopy) миллион строк.

Я ищу идентификатор со следующим кодом (l_z является List<T>)

var z_fk = (from z in l_z
            where z.CODE == lookupCode &&
                  z.VALIDFROM <= lookupDate &&
                  z.VALIDUNTIL >= lookupDate 
            select z.id).SingleOrDefault();

В других ситуациях я использовал словарь с превосходной производительностью, но в тех случаях мне приходилось только искать идентификатор на основе кода.

Но теперь с поиском по комбинации полей я застрял.

Есть идеи? Заранее спасибо.

Answer 1

Простым улучшением было бы использование ...

//in initialization somewhere
ILookup<string, T> l_z_lookup = l_z.ToLookup(z=>z.CODE);

//your repeated code:
var z_fk = (from z in lookup[lookupCode]
            where z.VALIDFROM <= lookupDate && z.VALIDUNTIL >= lookupDate 
            select z.id).SingleOrDefault();

Вы могли бы дополнительно использовать более сложную, более умную структуру данных, хранящую даты в отсортированном виде, и использовать двоичный поиск, чтобы найти идентификатор, но этоможет быть достаточно.Кроме того, вы говорите о SqlBulkCopy - если вы имеете дело с базой данных, возможно, вы можете выполнить запрос к базе данных, а затем просто создать соответствующий индекс, включающий столбцы CODE, VALIDUNTIL и VALIDFROM.

Iобычно предпочитают использовать Lookup вместо Dictionary, содержащего Lists, поскольку его создание тривиально и имеет более чистый API (например, когда ключ отсутствует).

Answer 2

Создать словарь, в котором хранится список элементов для каждого кода поиска - Dictionary<string, List<Code>> (при условии, что код поиска является строкой, а объекты имеют тип Code).

Тогда, когда вам нужно выполнить запрос на основе lookupDate, вы можете запустить запрос непосредственно из dict[lookupCode]:

var z_fk = (from z in dict[lookupCode]
            where z.VALIDFROM <= lookupDate &&
                  z.VALIDUNTIL >= lookupDate 
            select z.id).SingleOrDefault();

Затем просто убедитесь, что всякий раз, когда у вас есть новый объект Code, он добавляется в коллекцию List<Code> в dict, соответствующем lookupCode (и, если он не существует, создайте его) .

Answer 3

У нас недостаточно информации, чтобы дать очень предписывающий совет, но есть некоторые общие вещи, о которых вы должны подумать.

Какие типы значений времени? Вы сравниваете время даты или какое-то примитивное значение (например, time_t). Подумайте, как ваши типы данных влияют на производительность. Выберите лучшие.

Должны ли вы действительно делать это в памяти или вы должны поместить все эти строки в SQL и разрешить запрашивать их там? Это действительно хорошо.

Но давайте придерживаться того, о чем вы спрашивали - при поиске в памяти.

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

В вашем случае у вас есть два критерия - код и диапазон дат. Вот несколько идей ...

Вы можете разделить на основе кода - т. Е. Словаря> - если у вас много равномерно распределенных кодов, каждый из ваших размеров списка будет иметь размер N / M (где N = общее количество событий, а M = количество событий). Таким образом, миллион узлов с десятью кодами теперь требует поиска 100 тыс. Элементов, а не миллиона. Но вы могли бы пойти немного дальше. Сам список можно отсортировать по времени запуска, что позволяет бинарному поиску очень быстро исключить многие другие узлы. (это, конечно, имеет компромисс во времени для сбора данных). Это должно обеспечить очень быстро

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

Вы можете перевернуть модель словаря, чтобы разделить данные по времени начала, округленному до некоторой границы (в зависимости от длины, степени детализации и частоты ваших событий). В основном это группирование данных в группы с одинаковым временем запуска. Например, все события, которые были начаты между 12:00 и 12:01, могут быть в одном ведре и т. Д. Если у вас очень небольшое количество событий и много очень частых (но не патологически) событий, это может дать вам очень хорошая производительность поиска.

Суть? Подумайте о ваших данных. Подумайте, как дорого стоит добавлять новые данные и как дорого стоит запрашивать данные. Подумайте, как ваши типы данных влияют на эти характеристики. Примите обоснованное решение на основе этих данных. Если вы сомневаетесь, пусть SQL сделает это за вас.

Answer 4

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