用於記錄分析的滑動時間窗口

Question

我有一個電話呼叫的數據結構。對於這個問題有兩個字段，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; 
     } 
    } 
} 

WHIS是醜陋的，至少可以說。有沒有更好，更乾淨，更快捷的方法？

雖然我沒有在大型數據集上測試過，但我會在每小時運行100,000條記錄，因此每條記錄都會有大量的比較結果。

更新的數據是由沒有時間數量排序如問題

Answer 1

如果電話呼叫已按呼叫時間排序，則可以執行以下操作：

• 初始化對每一個電話號碼的計數器（哈希表，可先空和你添加元素把它作爲你去）
• 有兩個指針到你的鏈接列表中的哈希表，我們稱他們爲'左'和'右'
• 只要'左'和'右'呼叫之間的時間戳是le短於10秒，向右移動「右」一次，並將新遇到的電話號碼的計數加1
• 每當差值超過10秒時，向前移動「左」1並減少電話的計數「左」指針離開的號碼
• 在任何時候，如果有一個電話號碼，其散列表中的計數器爲3或更多，您就會發現一個電話號碼在10秒內有2次以上的呼叫窗口

這是一個線性時間算法，並行處理所有數字。

Answer 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方法不斷超越您的整個列表而導致的性能提升，但至少代碼更清晰:)

Answer 3

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); 

Answer 4

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

無功擴展器（Rx）是構成使用觀察序列和LINQ風格查詢操作異步和基於事件的程序庫。使用的Rx，開發者表示與觀測量異步數據流，使用LINQ運營商查詢異步數據流，和使用調度程序

的間隔方法返回之後產生的值的觀察到的序列參數併發在異步數據流每個週期

下面是簡單的例子：

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); 
    } 

Answer 5

在兩個步驟：

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(); 

Answer 6

如果性能是可以接受的（我想應該是的，因爲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）每個調用集合與本身移接一個，來的通話時間列表轉換成的差距電話之間的列表。然後，我們尋找的數字，其中有最多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是感興趣的數字序列。