Pavel Pavel - 10 days ago 5
Scala Question

List performance optimization

Is there any chance to optimise next line of code:

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 - array of vertexes with direction/link to other vertexes.
inGraph size could be, say, say 10000 vertexes.

I am trying to find list of sources (list of vertexes with out any in-comming edges)

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

Answer

Yes, it is possible to make it faster by using a more efficient algorithm. What code does now is basically:

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

It has an O(n * m) time complexity in the worst case (where m is the number of edges and n is the number of vertices).

Here is a solution which is linear in the size of the graph:

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

The noIncoming is the set of vertices with no incoming edges.