Эффективное объединение временных записей с помощью LINQ

Question

Рассмотрим набор данных, где элементы могут быть спарены во времени.

Например, входя и выходя из области со значком, можно записать такие данные, как:

┏━━━━━━━━━━┳━━━━━━━━━┳━━━━━━━━━━━┓
┃ Time     ┃ BadgeId ┃ Direction ┃
┣══════════╪═════════╪═══════════┫
┃ 1001930  ┃ A       ┃ IN        ┃
┣━━━━━━━━━━╋━━━━━━━━━╋━━━━━━━━━━━┫
┃ 1004901  ┃ B       ┃ IN        ┃
┣━━━━━━━━━━╋━━━━━━━━━╋━━━━━━━━━━━┫
┃ 1005192  ┃ A       ┃ OUT       ┃
┣━━━━━━━━━━╋━━━━━━━━━╋━━━━━━━━━━━┫
┃ 1012933  ┃ A       ┃ IN        ┃
┣━━━━━━━━━━╋━━━━━━━━━╋━━━━━━━━━━━┫
┃ 1014495  ┃ B       ┃ OUT       ┃
┣━━━━━━━━━━╋━━━━━━━━━╋━━━━━━━━━━━┫
┃ 1017891  ┃ A       ┃ OUT       ┃
┗━━━━━━━━━━┻━━━━━━━━━┻━━━━━━━━━━━┛

А затем спарить его временно, чтобы получить что-то вроде:

┏━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━┓
┃ BadgeId ┃ TimeIn   ┃ TimeOut  ┃
┣═════════╪══════════╪══════════┫
┃ A       ┃ 1001930  ┃ 1005192  ┃
┣━━━━━━━━━╋━━━━━━━━━━╋━━━━━━━━━━┫
┃ A       ┃ 1012933  ┃ 1017891  ┃
┣━━━━━━━━━╋━━━━━━━━━━╋━━━━━━━━━━┫
┃ B       ┃ 1004901  ┃ 1014495  ┃
┗━━━━━━━━━┻━━━━━━━━━━┻━━━━━━━━━━┛

Учитывая набор данных с сотнями миллионов таких записей, какой был бы наиболее эффективный метод создания такого временного спаривания? Меня интересует теоретически лучший подход и наиболее практически эффективный подход с использованием LINQ (или другого языка запросов на основе множеств).

Answer 1

Я не уверен, насколько это эффективно или производительно, но я думаю, что LINQ может преобразовать его в SQL, поэтому, если вы используете базу данных, это может привести к увеличению объема вычислений на сервере.

Сначала сгруппируйте записи по значкам:

var p1 = from p in punches
         group p by p.Badge into pg
         select new {
             Badge = pg.Key,
             Punches = pg.OrderBy(p => p.Time)
         };

Затем, для каждой группы записей значка, просмотрите все записи "IN" и сопоставьте их с записью "OUT", если она существует:

var p2 = p1.SelectMany(pg => pg.Punches.Where(p => p.Dir == "IN")
                                       .Select(p => new {
                                            pg.Badge,
                                            TimeIn = p.Time,
                                            TimeOut = pg.Punches.Where(po => po.Dir == "OUT" && po.Time > p.Time)
                                                                .FirstOrDefault().Time
                                       }));

Наконец, закажите результат:

var ans = p2.OrderBy(bio => bio.Badge).ThenBy(bio => bio.TimeIn);

Так как LINQ to SQL распространяет нули автоматически, я думаю, что это обработает отсутствующий удар "OUT" для "IN", но не потерянный "OUT" удар.

Другая возможность - использовать Select с двумя параметрами для группировки записей перфорации в парах, но это работает только с LINQ to Objects, поэтому, если вы не отфильтруете данные перед обработкой, все миллионы записей будут вытянуты в память.

Для полноты вот попытка:

var p2 = p1.AsEnumerable()
           .SelectMany(pg => pg.Punches.Select((p, i) => (p, i))
                                       .GroupBy(pi => pi.i / 2, pi => pi.p)
                                       .Select(pp => new {
                                            pg.Badge,
                                            TimeIn = pp.Where(p => p.Dir == "IN").FirstOrDefault()?.Time,
                                            TimeOut = pp.Where(p => p.Dir == "OUT").FirstOrDefault()?.Time
                                       }));

Ничего из этого не будет работать очень хорошо, если ваши удары плохо упорядочены, например вам не хватает начального «IN».

Answer 2

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

class Program
{
    static void Main(string[] args)
    {
        var StartingRecords = new List<Record>()
        {
            new Record(1001930, "A", "IN"),
            new Record(1004901, "B", "IN"),
            new Record(1005192, "A", "OUT"),
            new Record(1012933, "A", "IN"),
            new Record(1014495, "B", "OUT"),
            new Record(1017891, "A", "OUT"),
        };

        var records = StartingRecords.OrderBy(x => x.BadgeId).ThenBy(x => x.Time).ToList();

        var pairs = records.Skip(1).Zip(records, (second, first) => Tuple.Create(first, second)).
        Where(x => x.Item1.BadgeId == x.Item2.BadgeId &&
        x.Item1.Direction == "IN" && x.Item2.Direction == "OUT").
        Select(x => new Pair(x.Item1.BadgeId, x.Item1.Time, x.Item2.Time)).ToList();

        foreach (var pair in pairs)
            Console.WriteLine(pair.BadgeId + "\t" + pair.TimeIn + "\t" + pair.TimeOut);

        Console.Read();
    }
}

class Record
{
    public long Time { get; set; }
    public string BadgeId { get; set; }
    public string Direction { get; set; }

    public Record(long time, string badgeId, string direction)
    {
        Time = time;
        BadgeId = badgeId;
        Direction = direction;
    }
}

class Pair
{
    public string BadgeId { get; set; }
    public long TimeIn { get; set; }
    public long TimeOut { get; set; }

    public Pair(string badgeId, long timeIn, long timeOut)
    {
        BadgeId = badgeId;
        TimeIn = timeIn;
        TimeOut = timeOut;
    }
}

Выход: A 1001930 1005192 A 1012933 1017891 B 1004901 1014495