有效地Scala的集合

與OpenFlow工作，我想計算兩個所有組合比較多少雙流滿足以下條件（給定任意兩個流，例如f1和f2）：有效地Scala的集合

f1「 s Src ip必須等於f2的Dst ip。
f1的Dst ip必須等於f2的Src ip。
f1和f2必須具有相同的協議。

這個我認爲應該是兩個元素(NFlows Choose 2)的組合。由於this question我使用的方法combinations象下面這樣：

val pairFlows = matchs.combinations(2).filter{ list => 
    val f1 = list.head 
    val f2 = list.tail.head 

    f1.dl_type == f2.dl_type && 
    f1.nw_dst == f2.nw_src && 
    f1.nw_src == f2.nw_dst 
}

我的問題是，這是執行這種計算的最有效的方法是什麼？或者爲了跟蹤每個src，dst和protocol type，創建一個HashMap會更好嗎？

這裏是數據的一個示例：

{ 
    1: [ 
     { 
      "actions": [ 
       "OUTPUT:2" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 18, 
      "hard_timeout": 0, 
      "byte_count": 1764, 
      "duration_sec": 6884, 
      "duration_nsec": 5000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:02", 
       "nw_src": "10.0.0.1", 
       "in_port": 1, 
       "nw_dst": "10.0.0.2" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:2" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 18, 
      "hard_timeout": 0, 
      "byte_count": 1764, 
      "duration_sec": 1123, 
      "duration_nsec": 181000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:02", 
       "nw_src": "10.0.0.3", 
       "in_port": 3, 
       "nw_dst": "10.0.0.2" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:1" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 10, 
      "hard_timeout": 0, 
      "byte_count": 980, 
      "duration_sec": 1132, 
      "duration_nsec": 253000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:01", 
       "nw_src": "10.0.0.3", 
       "in_port": 3, 
       "nw_dst": "10.0.0.1" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:1" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 16, 
      "hard_timeout": 0, 
      "byte_count": 1568, 
      "duration_sec": 1141, 
      "duration_nsec": 652000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:01", 
       "nw_src": "10.0.0.2", 
       "in_port": 2, 
       "nw_dst": "10.0.0.1" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:3" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 20, 
      "hard_timeout": 0, 
      "byte_count": 1960, 
      "duration_sec": 6883, 
      "duration_nsec": 961000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:03", 
       "nw_src": "10.0.0.2", 
       "in_port": 2, 
       "nw_dst": "10.0.0.3" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:3" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 12, 
      "hard_timeout": 0, 
      "byte_count": 1176, 
      "duration_sec": 6883, 
      "duration_nsec": 984000000, 
      "priority": 1, 
      "length": 120, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 2048, 
       "dl_dst": "00:00:00:00:00:03", 
       "nw_src": "10.0.0.1", 
       "in_port": 1, 
       "nw_dst": "10.0.0.3" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:CONTROLLER" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 0, 
      "hard_timeout": 0, 
      "byte_count": 0, 
      "duration_sec": 9156, 
      "duration_nsec": 252000000, 
      "priority": 65535, 
      "length": 96, 
      "flags": 0, 
      "table_id": 0, 
      "match": { 
       "dl_type": 35020, 
       "dl_dst": "01:80:c2:00:00:0e" 
      } 
     }, 
     { 
      "actions": [ 
       "OUTPUT:CONTROLLER" 
      ], 
      "idle_timeout": 0, 
      "cookie": 0, 
      "packet_count": 22, 
      "hard_timeout": 0, 
      "byte_count": 1260, 
      "duration_sec": 9156, 
      "duration_nsec": 268000000, 
      "priority": 0, 
      "length": 80, 
      "flags": 0, 
      "table_id": 0, 
      "match": {} 
     } 
    ], 
}

在這裏有8間流動，其中3個是對。

來源

2017-01-16 elbaulp

與GROUPBY（_。dl_type）開始會給你幾個較小的列表，而不是一個巨大的，檢查。根據您的數據的外觀，這可以幫助很多，一點或根本沒有。另外，看着通過h來自n個元素列表的2個元素的所有組合是O（n^2）。如果您保留兩個列表，一個按dst排序，另一個按src排序（這是在O（nlogn）中完成的），您可以遍歷它們一次並收集所有匹配。這會給你比上面的例子更好的時間複雜度。 – Buhb

@Buhb謝謝，我已經設法在'O（n） – elbaulp

我終於寫的代碼是O(n)，我保持Map與關鍵f.nw_src + f.nw_dst + f.dl_type和價值Int表示，如果該鍵有相應的對流量（這將是一個具有關鍵f.nw_dst + f.nw_src + f.dl_type下面是最終代碼：

val table = flows./:(Map.empty[String,Int]){ case (m,f) => 
    val key = f.nw_src + f.nw_dst + f.dl_type 
    val inverseKey = f.nw_dst + f.nw_src + f.dl_type 
    val haspair = m get inverseKey match { 
    case Some(v) => v + 1 
    case None => 0 
    } 
    m + (key -> haspair) 
} 

val pairs = table.filter(_._2 > 0)

希望這有助於有人找一個類似的問題。

來源

2017-01-17 11:13:01 elbaulp

有效地Scala的集合

回答

相關問題