需要帮助找出性能瓶颈

Question

我正在做我的scala图章，并实现了一个小的图Api来跟踪添加到图中的顶点和边。我有基本的GraphLike特征，并且有一个无向图类( UnDiGraph)和一个扩展GraphLike特征的有向图类(DiGraph )。下面是一些清单

trait GraphLike[T] {
    val vertices: Map[T, VertexLike[T]]
    def addEdge( a:T, b:T ): GraphLike[T]
    def addVertex( t:T ): GraphLike[T]
    def addVertex( vert: VertexLike[T] ): GraphLike[T]
    def adjacency( t:T ): Option[ List[T] ]  =
    {
      if ( vertices contains t )
        Some( vertices(t).adjList )
      else
        None
    }
    def vertNum: Integer = vertices size
    def edgeNum: Integer = 
    {
      def summer( sum: Integer, ms: Map[T, VertexLike[T] ] ): Integer =
      {
        if ( ms.isEmpty )
          sum
        else
          summer( sum + ms.head._2.adjList.size, ms.tail )
      }
      summer( 0, vertices )
    }
    def getVertex( t: T ): VertexLike[T] =
    {
      vertices( t )
    }
    def edgeExists( a:T, b:T ): Boolean =
    {
      try
      {
          if( vertices( a ).adjList contains b )
            true
          else
            false
      }catch {
        case ex: NoSuchElementException => false 
      }
    }
}

这是Directe Graph的样子。

class DiGraph[T](val vertices: Map[ T, VertexLike[ T ] ] = Map.empty ) extends GraphLike[T] {
    def makeVertex( t:T ): VertexLike[T] = new Vertex( t )

    def addEdge( a:T, b:T ): GraphLike[T] =
    {
      //Make sure vertices exist
      if( edgeExists(a, b) )
        this
      else {
        try {
          vertices(b)
          vertices(a)
        } catch {
          case ex: NoSuchElementException => println("Vertices not Found"); this
        }
        addVertex( vertices( a ) + b )
      }
    }
    def addVertex( t:T ): DiGraph[T] = 
    {
      if( vertices contains t ) this
      else
      new DiGraph[T]( vertices + ( t -> makeVertex(t) ) )
    }
    def addVertex( vert: VertexLike[T] ): DiGraph[T] =
    {
      new DiGraph[T]( vertices + ( vert.apply -> vert ) ) 
    }
}

顶点存储在从类型T到VertexLikeT的映射中。顶点Like基本上包含特定顶点的邻接列表。下面是VertexLike的样子：

trait VertexLike[T] 
{
  def addEdgeTo( dest: T ): VertexLike[T]
  def adjList: List[T]
  def +( dest: T) = addEdgeTo(dest)
  def apply: T
} 

class Vertex[T](t: T, adj: List[T] = List() ) extends VertexLike[T]
{
    def apply() = t
    def adjList = adj
    def addEdgeTo( dest: T ) = 
      if( adjList contains dest )
        this
      else
        new Vertex[T]( t, dest :: adjList )
}

(是的..我意识到类中的apply方法是无用的，它只对对象起作用。后来才意识到这一点)。

不管怎样，我有一个样本图，其中我有大约80,000个顶点。将顶点添加到Graph中花费的时间太长了。我试着用一种不变的方式做事情。无论何时向图中添加顶点或边，都会得到一个新的图(我试图确保图类型的构造器不会做太多的工作)。这是我用来从我的数据创建图形的客户端代码。

def GraphInstantiater: GraphLike[Int] =
{
  println( "Total number of Vertices: " + synMap.keys.size )
  def vertexAdder( ls: Iterable[Int], graph:GraphLike[Int] ): GraphLike[Int] = 
    if( ls.isEmpty) graph else vertexAdder( ls.tail, graph.addVertex( ls.head ) ) 

  val gr = vertexAdder( synMap.keys, new DiGraph[Int]( Map() ) )
  println( "Vertices added. Total: %d".format( gr.vertices.size ) )
  gr
}

我知道构造新的图需要循环，但是考虑到我在构造器中做的并不多，这真的很棒吗？重复创建顶点图会导致问题(它是graph类的参数之一)。任何关于这种方法的瓶颈是什么的想法都将不胜感激。另外，如果您需要任何其他信息，请让我知道。

Answer 1

作为对您答案的补充:您确实在每次调用ls.tail时无意中遍历了整个synMap.keys。

发生的情况是：

• Map.key返回Map.keySet的值，这是一个custom immutable Set.
• that Set重写了一些内容，但将tail和drop保留为其默认实现。它的迭代实现(来自TraversableLike)只是调用drop.
• And，而这正是一切都失败的地方:它从IterableLike获得drop的实现，而这只做了您可以使用Iterable：iterate做的事情。因此创建了一个新的构建器，删除了迭代器的头部，然后将迭代器添加到构建器中，遍历所有键，并返回一个新的集合(尾部)。

通过使用迭代器，您可能可以完全避免转换为列表，如下所示：

def vertexAdder( ls: Iterator[Int], graph:GraphLike[Int] ): GraphLike[Int] = {
  if(!ls.hasNext) 
    graph 
  else
    val h = ls.next
    vertexAdder( ls, graph.addVertex(h) ) 
}

然后：

val gr = vertexAdder( synMap.keysIterator, new DiGraph[Int]( Map() ) )

顺便说一句，令人遗憾的是Set没有提供自己版本的tail。它可以直接获取自身迭代器的头，然后返回减去该元素的值。

Answer 2

哦哇..。我知道是怎么回事了。在GraphInstantiater方法中，第一个传递synMap.keys的调用返回一个iterableInt。看起来这是一个很长的过程，很可能每次都要经过整个密钥集。

将调用更改为

val gr = vertexAdder( synMap.keys.toList, new DiGraph[Int]( Map() ) )

让一切变得更快。有人知道在地图上调用keys时返回的容器的底层实现是什么吗？