滑动时间窗口记录分析

本文关键字：记录 窗口 时间 | 更新日期: 2023-09-27 18:16:47

我有一个电话的数据结构。对于这个问题，有两个字段，CallTime和NumberDialled。

我想执行的分析是"在10秒的窗口中是否有两个以上的呼叫到相同的号码"集合已经按CallTime排序并且是List<Cdr>。

我的解决方案是

List<Cdr> records = GetRecordsSortedByCallTime();
for (int i = 0; i < records.Count; i++)
{
    var baseRecord = records[i];
    for (int j = i; j < records.Count; j++)
    {
        var comparisonRec = records[j];
        if (comparisonRec.CallTime.Subtract(baseRecord.CallTime).TotalSeconds < 20)
        {
            if (comparisonRec.NumberDialled == baseRecord.NumberDialled)
                ReportProblem(baseRecord, comparisonRec);
        }
        else
        {
            // We're more than 20 seconds away from the base record.  Break out of the inner loop
            break; 
        }
    }
}

这至少可以说是丑陋的。有没有更好、更干净、更快的方法来做这件事?

虽然我还没有在大型数据集上测试过，但我将在每小时大约100,000条记录上运行它，因此对每条记录将有大量的比较。

Update数据按时间而不是数字排序，就像以前的问题一样

滑动时间窗口记录分析

如果来电已按通话时间排序，您可以执行以下操作:

  • 初始化一个哈希表，每个电话号码都有一个计数器(哈希表可以先为空，然后添加元素)
  • 有两个指向你的链表的指针，我们叫它们"左"answers"右"
  • 每当'左'和'右'呼叫之间的时间戳小于10秒时，将'右'向前移动一个，并将新遇到的电话号码的计数增加一个
  • 每当差异大于10秒时，将"左"向前移动一个，并减少"左"指针向左移动一个的电话号码的计数
  • 在任何时候，如果有一个电话号码在哈希表中的计数器是3或更多，你已经找到了一个电话号码在10秒窗口内有超过2个呼叫

这是一个线性时间算法，并行处理所有的数字。

我不知道你确切的结构，所以我为这个演示创建了我自己的结构:

class CallRecord
{
    public long NumberDialled { get; set; }
    public DateTime Stamp { get; set; }
}
class Program
{
    static void Main(string[] args)
    {
        var calls = new List<CallRecord>()
        {
            new CallRecord { NumberDialled=123, Stamp=new DateTime(2011,01,01,10,10,0) },
            new CallRecord { NumberDialled=123, Stamp=new DateTime(2011,01,01,10,10,9) },
            new CallRecord { NumberDialled=123, Stamp=new DateTime(2011,01,01,10,10,18) },
        };
        var dupCalls = calls.Where(x => calls.Any(y => y.NumberDialled == x.NumberDialled && (x.Stamp - y.Stamp).Seconds > 0 && (x.Stamp - y.Stamp).Seconds <= 10)).Select(x => x.NumberDialled).Distinct();
        foreach (var dupCall in dupCalls)
        {
            Console.WriteLine(dupCall);
        }
        Console.ReadKey();
    }
}

LINQ表达式循环遍历所有记录，并找到比当前记录(.Seconds > 0)早且在时间限制(.Seconds <= 10)内的记录。由于Any方法不断地遍历整个列表，这可能有点消耗性能，但至少代码更干净:)

我建议您使用Rx Extension和Interval方法。

Reactive Extensions (Rx)是一个使用可观察序列和linq风格查询操作符组合异步和基于事件的程序的库。使用Rx，开发人员使用Observables表示异步数据流，使用LINQ操作符查询异步数据流，并使用scheduler参数化异步数据流中的并发性

Interval方法返回一个可观察序列，该序列在每个周期后产生一个值

下面是一个简单的例子:

    var callsPer10Seconds = Observable.Interval(TimeSpan.FromSeconds(10));
    from x in callsPer10Seconds 
           group x by x into g 
           let count = g.Count() 
           orderby count descending 
           select new {Value = g.Key, Count = count}; 
    foreach (var x in q) 
    { 
        Console.WriteLine("Value: " + x.Value + " Count: " + x.Count); 
    } 

records.OrderBy(p => p.CallTime)
    .GroupBy(p => p.NumberDialled)
    .Select(p => new { number = p.Key, cdr = p.ToList() })
    .Select(p => new
    {
        number = p.number,
        cdr =
            p.cdr.Select((value, index) => index == 0 ? null : (TimeSpan?)(value.CallTime - p.cdr[index - 1].CallTime))
            .FirstOrDefault(q => q.HasValue && q.Value.TotalSeconds < 10)
    }).Where(p => p.cdr != null);

分两步:

  1. 生成调用本身和感兴趣范围内所有调用的枚举
  2. 过滤此列表以查找连续呼叫

使用AsParallel扩展方法并行地对每个记录进行计算。

也可以在线程结束时不调用ToArray，让计算完成，而其他代码可以在线程上执行，而不是强迫它等待并行计算完成。

var records = new [] {
    new { CallTime= DateTime.Now, NumberDialled = 1 },
    new { CallTime= DateTime.Now.AddSeconds(1), NumberDialled = 1 }
};
var span = TimeSpan.FromSeconds(10);
// Select for each call itself and all other calls in the next 'span' seconds
var callInfos = records.AsParallel()
    .Select((r, i) =>
        new
        {
            Record = r,
            Following = records.Skip(i+1)
                            .TakeWhile(r2 => r2.CallTime - r.CallTime < span)
        }
    );
// Filter the calls that interest us
var problematic = (from callinfo in callInfos 
                where callinfo.Following.Any(r => callinfo.Record.NumberDialled == r.NumberDialled)
                select callinfo.Record)
                .ToArray();

如果性能是可以接受的(我认为应该是这样，因为100k记录并不是特别多)，这种方法(我认为)是很好的和干净的:

首先我们将记录按编号分组:

var byNumber = 
    from cdr in calls
    group cdr by cdr.NumberDialled into g
    select new 
             {
                 NumberDialled = g.Key,
                 Calls = g.OrderBy(cdr => cdr.CallTime)
             };

我们现在做的是Zip()。. NET 4)每个调用集合本身移位1，将调用时间列表转换为调用之间的间隙列表。然后我们寻找间隔不超过10秒的数字:

var interestingNumbers =
    from g in byNumber
    let callGaps = g.Calls.Zip(g.Calls.Skip(1), 
        (cdr1, cdr2) => cdr2.CallTime - cdr1.CallTime)
    where callGaps.Any(ts => ts.TotalSeconds <= 10)
    select g.NumberDialled;

现在interestingNumbers是感兴趣的数字序列。

相关文章：