Как разделить запрос LINQ to Objects? - PullRequest
Новая
       22

Как разделить запрос LINQ to Objects?

7 голосов
/ 16 марта 2011

Это проблема выделения ресурсов. Моя цель - выполнить запрос, чтобы получить приоритетное смещение для любого временного интервала.

Набор данных очень большой. Например, предположим, что на 1000 компаний приходится 100 смен в каждой (хотя реальный набор данных еще больше). Все они загружены в память, и мне нужно выполнить один запрос LINQ to Objects к ним: 

    var topShifts =
            (from s in shifts
            where (from s2 in shifts
                   where s2.CompanyId == s.CompanyId && s.TimeSlot == s2.TimeSlot
                   orderby s2.Priority
                   select s2).First().Equals(s)
            select s).ToList();

Проблема в том, что без оптимизации LINQ to Objects будет сравнивать каждый объект в обоих наборах, выполняя перекрестное объединение всех 1000 x 100 против 1000 x 100, что составляет 10 миллиардов (10 000 000 000) сравнений. Я хочу сравнить только объекты внутри каждой компании (как если бы компания была проиндексирована в таблице SQL). Это должно привести к 1000 наборов 100 x 100 объектов для в общей сложности 10 миллионов (10 000 000) сравнений. Последнее будет масштабироваться линейно, а не экспоненциально по мере роста числа компаний.

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

Полный образец кода: 

public struct Shift
{
    public static long Iterations;

    private int companyId;
    public int CompanyId
    {
        get { Iterations++; return companyId; }
        set { companyId = value; }
    }

    public int Id;
    public int TimeSlot;
    public int Priority;
}

class Program
{
    static void Main(string[] args)
    {
        const int Companies = 1000;
        const int Shifts = 100;
        Console.WriteLine(string.Format("{0} Companies x {1} Shifts", Companies, Shifts));
        var timer = Stopwatch.StartNew();

        Console.WriteLine("Populating data");
        var shifts = new List<Shift>();
        for (int companyId = 0; companyId < Companies; companyId++)
        {
            for (int shiftId = 0; shiftId < Shifts; shiftId++)
            {
                shifts.Add(new Shift() { CompanyId = companyId, Id = shiftId, TimeSlot = shiftId / 3, Priority = shiftId % 5 });
            }
        }
        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        timer.Restart();

        Console.WriteLine("Computing Top Shifts");
        var topShifts =
                (from s in shifts
                where (from s2 in shifts
                       where s2.CompanyId == s.CompanyId && s.TimeSlot == s2.TimeSlot
                       orderby s2.Priority
                       select s2).First().Equals(s)
                select s).ToList();
        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        timer.Restart();

        Console.WriteLine("\nShifts:");
        foreach (var shift in shifts.Take(20))
        {
            Console.WriteLine(string.Format("C {0} Id {1} T {2} P{3}", shift.CompanyId, shift.Id, shift.TimeSlot, shift.Priority));
        }

        Console.WriteLine("\nTop Shifts:");
        foreach (var shift in topShifts.Take(10))
        {
            Console.WriteLine(string.Format("C {0} Id {1} T {2} P{3}", shift.CompanyId, shift.Id, shift.TimeSlot, shift.Priority));
        }

        Console.WriteLine(string.Format("\nTotal Comparisons: {0:n}", Shift.Iterations/2));

        Console.WriteLine("Any key to continue");
        Console.ReadKey();
    }
}

Пример вывода:

1000 компаний х 100 смен
Заполнение данных
Завершено в 10.00ms
Вычислительные главные сдвиги
Завершено за 520 721,00 мс

Сдвиги:
C 0 Id 0 T 0 P0
C 0 Id 1 T 0 P1
C 0 Id 2 T 0 P2
C 0 Id 3 T 1 P3
C 0 Id 4 T 1 P4
C 0 Id 5 T 1 P0
C 0 Id 6 T 2 P1
C 0 Id 7 T 2 P2
C 0 Id 8 T 2 P3
C 0 Id 9 T 3 P4
C 0 Id 10 T 3 P0
C 0 Id 11 T 3 P1
C 0 Id 12 T 4 P2
C 0 Id 13 T 4 P3
C 0 Id 14 T 4 P4
C 0 Id 15 T 5 P0
C 0 Id 16 T 5 P1
C 0 Id 17 T 5 P2
C 0 Id 18 T 6 P3
C 0 Id 19 T 6 P4

Лучшие смены:
C 0 Id 0 T 0 P0
C 0 Id 5 T 1 P0
C 0 Id 6 T 2 P1
C 0 Id 10 T 3 P0
C 0 Id 12 T 4 P2
C 0 Id 15 T 5 P0
C 0 Id 20 T 6 P0
C 0 Id 21 T 7 P1
C 0 Id 25 T 8 P0
C 0 Id 27 T 9 P2

Всего сравнений: 10 000 000 015,00
Любая клавиша для продолжения

Вопросы:

  1. Как я могу разделить запрос (при этом все еще выполняется как один запрос LinQ), чтобы сократить количество сравнений с 10 до 10 миллионов?
  2. Есть ли более эффективный способ решения проблемы, чем подзапрос?

Ответы [ 3 ]

3 голосов
/ 16 марта 2011

Как насчет 

            var topShifts = from s in shifts.GroupBy(s => s.CompanyId)
                        from a in s.GroupBy(b => b.TimeSlot)
                        select a.OrderBy(p => p.Priority).First();

Кажется, чтобы получить тот же вывод, но 100015 сравнений

с правкой @ Джеффа он только вдвое уменьшил мои сравнения: -)

1 голос
/ 16 марта 2011

Вы пробовали использовать group by: 

var topShifts =  from s in shifts
                 group s by new { 
                     CompanyId = s.CompanyId, 
                     TimeSlot = s.TimeSlot } into p
                 let temp = p.OrderBy(x => x.Priority).FirstOrDefault()
                 select new
                     {
                         CompanyId = temp.CompanyId,
                         TimeSlot = temp.TimeSlot,
                         Id = temp.Id,
                         Priority = temp.Priority
                     };
1 голос
/ 16 марта 2011

Я немного не уверен в том, что вы хотите быть честным, но, читая ваш код, я бы сказал, что вы можете сделать что-то вроде 

(from company in shifts.GroupBy(s=>s.CompanyID)
 let lowPriority = (from slot in company.GroupBy(s=>s.TimeSlot)
select slot).OrderBy(s=>s.Priority).First()
 select lowPriority).ToList();
...