Самый быстрый способ фильтрации двух списков на основе общего поля данных в конфигурации 1-много

c# linq list join

132 просмотра

1 ответ

Это все о performance. У меня есть два основных lists of objects(здесь я буду использовать PEOPLE/PERSONв качестве замены). Во- первых, мне нужно filter one listсамая First_Name property- то мне нужно создать two filtered lists from each master list based on shared date- один список только с одним именем, другой список с каждым именем, но с обоих списках , содержащих только записи даты согласования (нет даты в одном списке , который не существует в Другие). Я написал, pseudo-codeчтобы упростить проблему до основного вопроса ниже. Пожалуйста, поймите, читая, что ДЕНЬ РОЖДЕНИЯ не был лучшим выбором, так как есть несколько записей даты на человека. Поэтому, пожалуйста, сделайте вид, что у каждого человека есть около 5000 «дней рождения» при чтении кода ниже:

public class Person
{
    public string first_Name;
    public string last_Name;
    public DateTime birthday;
}
public class filter_People
{
    List<Person> Group_1 = new List<Person>();// filled from DB Table "1982 Graduates" Group_1 contains all names and all dates
    List<Person> Group_2 = new List<Person>();// filled from DB Table "1983 Graduates" Group_2 contains all names and all dates
    public void filter(List<Person> group_One, List<Person> group_Two)
    {
        Group_1 = group_One;
        Group_2 = group_Two;
        //create a list of distinct first names from Group_1
        List<string> distinct_Group_1_Name = Group_1.Select(p => p.first_Name).Distinct().ToList();

        //Compare each first name in Group_1 to EVERY first name in Group 2, using only records with matching birthdays
        Parallel.For(0, distinct_Group_1_Name.Count, dI => {
            //Step 1 - create a list of person out of group_1 that match the first name being iterated
            List<Person> first_Name_List_1 = Group_1.Where(m => m.first_Name == distinct_Group_1_Name[dI]).ToList();
            //first_Name_List_1 now contains a list of everyone named X (Tom). We need to find people from group 2 who match Tom's birthday - regardless of name

            //step 2 - find matching birthdays by JOINing the filtered name list against Group_2  
            DateTime[] merged_Dates = first_Name_List_1.Join(Group_2, d => d.birthday, b => b.birthday, (d, b) => b.birthday).ToArray();
            //Step 3 - create filtered lists where Filtered_Group_1 contains ONLY people named Tom, and Filtered_Group_2 contains people with ANY name sharing Tom's birthday. No duplicates, no missing dates.
            List<Person> Filtered_Group_1 = first_Name_List_1.Where(p => p.birthday.In(merged_Dates)).ToList();
            List<Person> Filtered_Group_2 = Group_2.Where(p => p.birthday.In(merged_Dates)).ToList();
            //Step 4 -- move on adn process the two filtered lists (outside scope of question)
            //each name in Group_1 will then be compared to EVERY name in Group_2 sharing the same birthday
            //compare_Groups(Filtered_Group_1,Filtered_Group_2)

        });
    }
}
public static class Extension
{
    public static bool In<T>(this T source, params T[] list)
    {
        return list.Contains(source);
    }
}

Здесь идея состоит в том, чтобы взять two different master name listsиз БД и создать подсписки, в которых совпадают даты (один только с одним именем, а другой со всеми именами) с учетом one-to-many comparisonоснований datasetsодинаковой длины с соответствующими индексами дат. Первоначально идея состояла в том, чтобы просто загрузить списки из БД, но списки длинные и загружать все данные имен и использовать их SELECT/WHERE/JOINнамного быстрее. Я говорю "намного быстрее", но это относительно.

Я пытался конвертировать Group_1и Group_2в словари и соответствующие даты с помощью ключей. Не так много улучшений. Group_1 has about 12Million records( about 4800 distinct namesс несколькими датами каждая), а Group_2 имеет примерно одинаковые значения, поэтому здесь вводятся 12Millionзаписи, а вывод - в виде миллиарда записей. Несмотря на то, что я запускаю этот метод как отдельную задачу и ставлю результаты в очередь для обработки другим потоком, требуется вечное разделение этих списков и их поддержание.

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

Буду очень признателен за любую помощь в том, как выполнить фильтрацию по сравнению со многими более продуктивным способом.

Спасибо!

Автор: Shannon Holsinger Источник Размещён: 08.11.2019 10:57

Ответы (1)


2 плюса

Решение

Код в текущем формате, я вижу слишком много проблем, чтобы он мог ориентироваться на производительность с типом данных, которые вы упомянули. Parallelismне волшебная таблетка для бедных algorithmи data structureвыбора.

В настоящее время для каждого сравнения, которое выполняется, и linear search O(N), следовательно, M*O(N)для M операций, даже если мы сделаем эти операции O(logN), даже лучше O(1), будет существенное улучшение времени выполнения.

Вместо того , чтобы Distinctзатем искать в Parallel loopиспользовании Whereпункта, использовать GroupByдля aggregate / groupзаписи, а также создать словарь в одной и той же операции, что обеспечит легкий поиск записей с заданным именем

var nameGroupList = Group_1.GroupBy(p => p.first_Name).ToDictionary(p => p.Key, p => p);

Это поможет вам избавиться от следующих двух операций в исходном коде (одна из них в Parallel - это повторяющаяся операция, которая сильно снижает производительность)

List<string> distinct_Group_1_Name = Group_1.Select(p => p.first_Name).Distinct().ToList();

List<Person> first_Name_List_1 = Group_1.Where(m => m.first_Name == distinct_Group_1_Name[dI]).ToList();

DictionaryБудет типа Dictionary<string,IEnumerable<Person>>, таким образом , вы получите список Человека по имени в O(1)время и нет повторяющихся поиска. Еще одна проблема кода, который будет обрабатываться, - это воссоздание списка и поиск по исходному списку / данным.

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

p.birthday.In(merged_Dates)

поскольку в методах расширения вы каждый раз запускаете операцию list.Containsкак O(N)операцию, которая снижает производительность. Ниже приведены возможные варианты:

Извлеките также следующую операцию из параллельного цикла:

DateTime[] merged_Dates = first_Name_List_1.Join(Group_2, d => d.birthday, b => b.birthday, (d, b) => b.birthday).ToArray();

Вместо этого создайте другой Dictionaryтип Dictionary<string, Hashset<DateTime>>, пересекая данные из Dictionary<string,IEnumerable<Person>>созданных ранее, используя Data from Group2, вы можете использовать соответствующий IEqualityComparerDateTime, и, таким образом, будет доступен готовый счетчик для списка / массива Date, который не нужно создавать каждый раз:

personDictionary["PersonCode"].Intersect(Group2,IEqualityComparer(using Date))

Для окончательного результата, пожалуйста, обратите внимание, вы должны сохранить результат как HashSetвместо List. Преимущество будет в том, Containsчто O(log(N))операция будет работать вместо O(N), что сделает ее намного быстрее. На самом деле также хорошо иметь такую ​​структуру Dictionary<string, Dictionary<DateTime,DateTime>>, которая заставит ее O(1)работать.

Попробуйте эти пункты и предложите, если есть какие-либо улучшения в работе кода.

Автор: Mrinal Kamboj Размещён: 20.08.2016 08:28
Вопросы из категории :
32x32