列表性能优化

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是一组与没有入边的顶点。