Фильтрация большого объекта списка по данным из другого большого списка: низкая производительность

Question

У меня есть два больших списка объектов. Первый (около 1 000 000 объектов ):

public class BaseItem
{
    public BaseItem()
    {

    }

    public double Fee { get; set; } = 0;

    public string Market { get; set; } = string.Empty;

    public string Traider { get; set; } = string.Empty;

    public DateTime DateUtc { get; set; } = new DateTime();
}

Секунда (около 20 000 объектов ):

public class TraiderItem
{
    public TraiderItem()
    {

    }

    public DateTime DateUtc { get; set; } = new DateTime();

    public string Market { get; set; } = string.Empty;

    public string Type { get; set; } = string.Empty;

    public double Price { get; set; } = 0;

    public double Amount { get; set; } = 0;

    public double Total { get; set; } = 0;

    public double Fee { get; set; } = 0;

    public string FeeCoin { get; set; } = string.Empty;
}

Мне нужно найти все элементы Traider в элементах Base, когда DateUtc равны и Fee равны. Теперь я использую Любой метод:

traiderItemsInBase = traiderItems.Where(a => baseItems.Any(x => x.DateUtc == a.DateUtc && Math.Round(x.Fee, 8) == Math.Round((double)a.Fee * 0.4, 8))).ToList();

Но этот путь очень-очень медленный. Есть ли способ сделать это более эффективным? Есть ли возможность использовать HashSet в этом случае?

Answer 1

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

private static void TestForPreCountingParallel(List<TraiderItem> traiderItems, List<BaseItem> baseItems)
        {
            var watch = new Stopwatch();
            watch.Start();
            ConcurrentBag<TraiderItem> traiderItemsInBase = null;
            for (int i = 0; i < 3; i++)
            {
                traiderItemsInBase = new ConcurrentBag<TraiderItem>();
                var baseFeesRounds = baseItems.Select(bi => Math.Round((double)bi.Fee * 0.4, 8)).ToArray();
                Parallel.ForEach(traiderItems, traiderItem =>
                {
                    double traiderFeeRound = Math.Round(traiderItem.Fee, 8);
                    for (var index = 0; index < baseItems.Count; index++)
                    {
                        var baseItem = baseItems[index];
                        if (traiderItem.DateUtc == baseItem.DateUtc && traiderFeeRound == baseFeesRounds[index])
                        {
                            traiderItemsInBase.Add(traiderItem);
                            break;
                        }
                    }
                });

                Console.WriteLine(i + "," + watch.ElapsedMilliseconds);
            }

            watch.Stop();
            Console.WriteLine("base:{0},traid:{1},res:{2},time:{3}", baseItems.Count, traiderItems.Count,
                traiderItemsInBase.Count, watch.ElapsedMilliseconds);
        }

У кого-нибудь есть еще улучшения?

Для вещей, которые я пробовал, это так:

1. Оригинал Linq: база: 100000, трейд: 20000, разрешение: 40, время: 102544
2. Преобразовано в циклы foreach: Основание: 100000, Traid: 20000, разрешение: 40, время: 43890
3. Плата за предварительный сбор: база: 100000, трейд: 20000, разрешение: 40, время: 22661
4. Параллельный внешний цикл: основание: 100000, трейд: 20000, разрешение: 40, время: 6823

Времена незначительны, тенденция на что смотреть. Тест не идеален, я мало играл с соотношением TraiderItems внутри BaseItems, мой собственный, как видите, довольно низкий. 40 из 100000.

Итак, просто чтобы увидеть несколько различных соотношений:

1. база: 100000, Traid: 20000, разрешение: 400, время: 50842
2. база: 100000, Traid: 20000, разрешение: 400, время: 21754

И еще:

1. база: 100000, Traid: 20000, разрешение: 2000, время: 118150
2. база: 100000, Traid: 20000, разрешение: 2000, время: 57832
3. база: 100000, Traid: 20000, разрешение: 2000, время: 21659
4. база: 100000, Traid: 20000, разрешение: 2000, время: 7350

Я не эксперт, поэтому я должен ссылаться на другие источники, такие как: http://mattwarren.org/2016/09/29/Optimising-LINQ/

В чем проблема с LINQ?

Как обрисовал в общих чертах Джо Даффи, LINQ вводит неэффективность в форме скрытых отчислений

Итак, вывод такой:

1. сделайте свой собственный тест и сначала попробуйте внести некоторые изменения в код, если вы действительно заботиться о производительности. Просто добавление грубой силы к неэффективному код будет стоить кому-то денег.
2. не используйте сложные запросы LINQ для большой коллекции, пока вы не протестируете производительность. Я сгорел от этого, порог на удивление мало (например, 10 тыс. предметов с неправильным LINQ может убить время обработки, когда простой цикл работает хорошо).

Но мне очень нравится LINQ и я часто его использую.

Answer 2

Основная задержка Imho - Math.Round - может быть уменьшена на: 1. для x.Fee: создайте объект Facade для TraiderItem и сохраните в нем один раз рассчитанный FeeRound = x.Fee (или добавьте свойство для FeeRound в самом TraiderItem). Просто этот математический раунд называется 1m * 20k раз, и, возможно, раунд не является мощной частью пары компилятор / процессор. 2. преобразовать первую лямбда-функцию в функцию и вычислить a.Fee и передать в baseItems.Any (.....) в качестве параметра, подобного следующему:

traiderItems.Where(a => { var aFeeRound = Math.Round((double)a.Fee * 0.4, 8);
                      return baseItems
                      .Any(x =>
                         x.DateUtc == a.DateUtc && 
                         x.FeeRound == aFeeRound);})
        .ToList();

Таким образом, Math.Round будет работать только один раз для каждого выражения. извините за ошибки, нет времени на тестирование. Конечно, TPL хорошая идея. Удачи!

Answer 3

У него есть несколько BaseItem, вы можете сгруппировать их по дате в словаре:

    var baseItemsDic = new Dictionary<DateTime, List<BaseItem>>();
    foreach(var item in baseItems)
    {
        if (!baseItemsDic.ContainsKey(item.DateUtc))
            baseItemsDic.Add(item.DateUtc, new List<BaseItem>());
        baseItemsDic[item.DateUtc].Add(item);
    }


    var traiderItemsInBase = traiderItems.Where(a => baseItemsDic.ContainsKey(a.DateUtc) && baseItemsDic[a.DateUtc].Any(x => Math.Round(x.Fee, 8) == Math.Round((double)a.Fee * 0.4, 8))).ToList();

Answer 4

Сначала я подумал о решении с Hashet<> или Dictionary<>, но это не совсем подходит для этого варианта использования. Как насчет того, чтобы ускорить его, используя больше ядер / потоков с PLINQ AsParallel()?

traiderItemsInBase = traiderItems.AsParallel()
    .Where(a => baseItems.Any(x => x.DateUtc == a.DateUtc &&
                              Math.Round(x.Fee, 8) == Math.Round((double)a.Fee * 0.4, 8)))
    .ToList();

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

Answer 5

Использование этого LINQ, т. Е. Любой внутри, где почти как O (N ^ 2)

Лучше всего сначала создать HashSet, в котором ключ будет выглядеть так:

DateUtc.ToString("<Format based on matching depth (like Date or upto minutes/secs>")_Fee Rounded.ToString()

и заполните его всеми списками объектов BaseItem (в худшем случае у вас будет около 1 миллиона элементов в HashSet) (Это эквивалентно 1 циклу FOR)

Далее, переберите все элементы в коллекции TraiderItem (меньшая коллекция) - сформируйте Ключ поиска, как описано выше. И проверьте в HashSet. Это еще одна петля.

Сложность чистого времени около - O (N) + O (K) ---> Можно улучшить это, создав HashSet заранее или параллельно.

Пространственная сложность выше - но у вас слишком много баранов за сутки:)

Answer 6

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