需要幫助弄清楚性能瓶頸

Question

我正在研究我的scala排版，並實現了一個小圖形Api來跟蹤添加到圖形中的頂點和邊。我有基本的GraphLike Trait，並具有擴展GraphLike特性的無向圖類（UnDiGraph）和有向圖類（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要VertexLike [T]。頂點像基本上持有特定頂點的鄰接列表。繼承人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) 
} 

（是的......我知道在類的應用方法是無用的，它只能在對象意識到稍後）。

無論如何，我有一個示例圖，我有大約80,000個頂點。將這些頂點添加到圖表中時間過長。我試圖以一種不變的方式在功能上做事。每當你爲圖形添加一個頂點或一條邊時，你會得到一個新圖（我試圖確保圖類型的構造函數沒有太多）。這是我用來從我的數據創建圖形的客戶端代碼。

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 
} 

我知道構建新圖形將需要幾個週期，但它真的非常棒，因爲我在構造函數中做的不多。反覆創建頂點映射會導致問題（它是圖類的參數之一）。任何關於這種方法的瓶頸的想法將不勝感激。此外，如果您需要任何其他信息，請讓我知道。

Answer 1

作爲對您的補充回答：您每次撥打ls.tail時確實無意中遍歷了整個synMap.keys。

會發生什麼事是：

• Map.key返回Map.keySet的價值，這是一個custom immutable Set。
• 是Set覆蓋了一些東西，但留下tail和drop他們的默認實現。其tail執行（從TraversableLike）只需撥打drop。
• 這就是所有事情都會崩潰的地方：它從IterableLike得到drop的實現，並且這隻對Iterable：迭代有效。因此，創建了一個新的構建器，迭代器的頭部被刪除，然後迭代器被添加到構建器，該構建器遍歷所有密鑰，並返回一個新集合（尾部）。

你或許可以避開轉換到列表完全通過使用迭代器，喜歡的東西：

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的第一個調用會返回一個可迭代的[Int]。看起來這是一個漫長的過程，每次都很可能會經歷整個鍵。

改變呼叫

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

使一切走得更快。有人知道在Map上調用keys時返回的容器的底層實現是什麼？