Эффективно сравнить все комбинации двух в коллекции Scala

Работа с OpenFlow Я хочу, чтобы вычислить, сколько пар потоков удовлетворяют следующему условию (для любых двух потоков, например f1 и f2):Эффективно сравнить все комбинации двух в коллекции Scala

f1 ' s Src ip должно быть равно f2's Dst ip.
f1Dst ip должно быть равно f2Src 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 
}

Мой вопрос, Является ли это самый эффективный способ выполнения этого вычисления? Или было бы лучше создать HashMap, чтобы отслеживать каждый src, dst и protocol type?

Ниже приведен пример данных:

{ 
    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 все комбинации из 2 элементов из списка n элементов - 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

ответ

Смежные вопросы