Нужна помощь в определении узкого места производительности

Question

Я работаю над своими scala chops и реализовал небольшой график Api для отслеживания вершин и ребер, добавленных в график. У меня есть базовая функция GraphLike Trait и есть класс Undirected Graph (UnDiGraph) и класс Directed graph (DiGraph), который расширяет черту GraphLike. Ниже перечислены некоторые из них

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 
     } 
    } 
} 

Heres what the 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]. Vertex Как обычно, имеет список смежности для конкретной вершины. Вот что выглядит 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

В качестве дополнения к вам ответьте: вы действительно непреднамеренно пройдете весь synMap.keys каждый раз, когда вы звоните ls.tail.

Что происходит:

• Map.key возвращает значение Map.keySet, которое является custom immutable Set.
• что Set переопределяет несколько вещей, но оставляет tail и drop их реализации по умолчанию. Его реализация tail (от TraversableLike) просто вызывает drop.
• И вот где все разваливается: он получает свою реализацию drop от IterableLike, и это делает только то, что вы можете сделать с помощью 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())) 

сделал все быстрее. Кто-нибудь знает, какова основная реализация контейнера, возвращаемого при вызове keys на карте?