C# - проблемы с результатами задачи - PullRequest
Новая
       22

C# - проблемы с результатами задачи

0 голосов
/ 06 апреля 2020

Я должен найти повторяющиеся адреса в списке из 758 000 адресов путем сравнения строк. Что я сделал до сих пор: 

public int StartDuplicateFinder(List<Address> addresses, List<Address> checklist)
{
    int found = 0;

    foreach(Address addr1 in addresses)
    {
        List<Address> addresses2 = checklist.FindAll(
        delegate (Address addr2)
        {
            return addr2.AddressString == addr1.AddressString && addr2.Duplicate == "" 
                && addr2.AddrIndex > addr1.AddrIndex;
        }
        );

        foreach(Address addr2 in addresses2)
        {
            addr2.Duplicate = "1";
            found++;
        }
    }
    return found;
}

Это занимает около 7 часов (что слишком долго) и доставляет около 93 000 дубликатов!

Чтобы ускорить его, я разделил checklist в List<Address> checklists с 4 порциями (200k, 200k, 200k и 158k) и используется Task следующим образом: 

public class Worker
{
    private List<Address> addresses = null;
    private List<Addresses> checklist = null
    private int found = 0;

    public Worker(List<Address> _addresses, List<Address> _checklist)
    {
        addresses = _addresses; //always 758.000 addresses

        //with 4 Tasks: Task 1, 2 and 3 = 200.000 addresses, Task 4 = 158.000 addresses
        //with 6 Tasks: Task 1, 2, 3, 4 and 5 with 150.000 addresses, Task 6 with 8.000 addresses
        checklist = _checklist;
    }

    public int StartDuplicateFinder()
    {
        foreach(Address addr1 in addresses)
        {
            List<Address> addresses2 = checklist.FindAll(
            delegate (Address addr2)
            {
                return addr2.AddressString == addr1.AddressString && addr2.Duplicate == "" 
                    && addr2.AddrIndex > addr1.AddrIndex;
            }
            );

            foreach(Address addr2 in addresses2)
            {
                addr2.Duplicate = "1";
                found++;
            }
        }
    }

    public int Found {get {return found;}}
}

private async void StartTasks(List<Task> Tasklist)
{
    foreach (Task t in Tasklist)
    {
        t.Start();
    }
    await Task.WhenAll(Tasklist.ToArray());
}

private void DoSomething()
{
    List<Task> Tasklist = new List<Task>();

    foreach(List<Address> checklist in checklists)
    {
        Worker w = new Worker(addresses, checklist);
        Tasklist.Add(new Task(StartDuplicateFinder));        
    }
    StartTasks(Tasklist);

    //wait until the tasks are finished
    //do other stuff
    ...
}

Теперь он работает только в течение 35 минут! Но если я посмотрю на найденные дубликаты, то получится огромное отклонение. Было найдено только около 27 000 дубликатов.

Я пробовал это несколько раз, и каждый раз получал другие результаты. 

4 Tasks, first run:     4 Tasks, second run:
Task# > duplicates      Task# > duplicates
1     >   749           1     >   689
2     >  2450           2     >  2391
3     > 10304           3     > 10073
4     > 14462           4     > 14282
Sum   > 27965           Sum   > 27435

6 Tasks, first run:     6 Tasks, second run:
Task# > duplicates      Task# > duplicates
1     >    16           1     >    24
2     >    56           2     >    55
3     >   202           3     >   236
4     >   679           4     >   634
5     >   852           5     >   800
6     >  2985           6     >  2981
Sum   >  4790           Sum   >  4730

Каждый раз, когда это один и тот же список из 758 000 адресов.

Я пробовал это с Task, Thread и BackgroundWorker, но я всегда получаю разные результаты! Если я выполню это в 1 задании, то результат всегда будет 92.377 дубликатов (что я считаю правильным).

Может кто-нибудь помочь мне решить проблему?

Ответы [ 2 ]

3 голосов
/ 06 апреля 2020

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

Но вместо параллельной обработки рассмотрите возможность использования более эффективных структур данных и алгоритмов. IE вместо объединения вложенных циклов создайте таблицу Ha sh (Dictionary<TKey,TValue> или Lookup<TKey,TValue>), чтобы сделать это быстрее в одном потоке (по крайней мере, в качестве первого шага). Например, что-то вроде: 

public int StartDuplicateFinder(List<Address> addresses, List<Address> checklist)
{
    int found = 0;

    var checklistByAddressString = checklist.ToLookup(a => a.AddressString, a => a);

    foreach (Address addr1 in addresses)
    {
        var addressMatches = checklistByAddressString[addr1.AddressString];
        var addresses2 = addressMatches.Where(addr2 => addr2.Duplicate == ""
                && addr2.AddrIndex > addr1.AddrIndex);

        foreach (Address addr2 in addresses2)
        {
            addr2.Duplicate = "1";
            found++;
        }
    }
    return found;
}
1 голос
/ 06 апреля 2020

Проблема в том, что вы изменяете элементы в списке addresses, пока просматриваете их. Вы создаете условия гонки.

Ваш фильтр имеет, как часть критериев: 

addr2.Duplicate == ""

В то время как позже вы изменяете элементы: 

addr2.Duplicate = "1"`.

Возможно, будет лучше, если вы разбиваете на части addresses и go против полного checkList

Или просто используйте LINQ query в одном потоке для обоих списков. Скорее всего, вы получите значительно более быстрые результаты, чем циклически просматривая коллекции вручную.

...