用于记录分析的滑动时间窗口

Question

我有一个电话数据结构.对于这个问题,有两个领域,CallTime和NumberDialled.

我想要执行的分析是"在10秒窗口中是否有两个以上的相同数字的调用"该集合已经按照排序CallTime并且是a 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条记录运行它,因此每条记录将进行大量比较.

更新数据按时间而非数字排序,与早期版本的问题相同

Answer 1

如果电话呼叫已按呼叫时间排序,您可以执行以下操作:

• 初始化一个哈希表,其中包含每个电话号码的计数器(哈希表可以先清空,然后随时添加元素)
• 有两个指向你的链接列表的指针,我们称之为'左'和'右'
• 每当"左"和"右"呼叫之间的时间戳小于10秒时,向右移动"向右",并将新遇到的电话号码的数量增加一
• 每当差异超过10秒时,将"向左"向前移动一个,并将"左"指针留下的电话号码的计数减1
• 在任何时候,如果有一个电话号码,其哈希表中的计数器是3或更多,你发现一个电话号码在10秒钟内有超过2个电话

这是一种线性时间算法,并行处理所有数字.