列表性能優化

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 - 陣列方向/鏈接到其他頂點頂點。例如，圖形大小可以說是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是一組與沒有入邊的頂點。