Список оптимизации производительности

Question

Есть ли шанс оптимизировать следующую строку кода:

val adj: Array[ListBuffer[Int]] = Array.fill(n)(ListBuffer[Int]()) 
... 
.. 

val sourceVertexes = inGraph.zipWithIndex.filter(v => a.zipWithIndex.exists(r => r._2 != v._2 && r._1.exists(f => f == v._2)) 

inGraph - массив вершин с направлением/ссылки на другие вершины. inGraph размер может быть, скажем, 10000 вершин.

Я пытаюсь найти список источников (список вершин с любым в-пришедший краем)

val adj: Array[List[Int]] = Array.fill(n)(List[Int]()) 

Answer 1

Да, это можно сделать это быстрее, используя более эффективный алгоритм. Какой код делает сейчас в основном:

for each vertex: 
    for each edge: 
     if egde goes to vertex: 
      discard it 

Он имеет O(n * m) временную сложность в худшем случае (когда m это число ребер и n это число вершин).

Вот решение, которое является линейным размером графика:

noIncoming = a hash set with all vertices (or just a boolean array) 
for each edge: 
    if edge is not a loop: 
     noIncoming.remove(edge.desitination) // or we can put a mark in a boolean array 

noIncoming есть множество вершин, не имеющие входящих ребер.