scala - Need help figuring out performance bottleneck -

i'm working on scala chops , implemented small graph api track vertices , edges added graph. have basic graphlike trait, , have undirected graph class ( undigraph) , directed graph class (digraph ) extend graphlike trait. here of listing

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( ).adjlist contains b )             true           else             false       }catch {         case ex: nosuchelementexception => false        }     } } 

heres directe graph looks like.

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) )               else {         try {           vertices(b)           vertices(a)         } catch {           case ex: nosuchelementexception => println("vertices not found");         }         addvertex( vertices( ) + b )       }     }     def addvertex( t:t ): digraph[t] =      {       if( vertices contains t )       else       new digraph[t]( vertices + ( t -> makevertex(t) ) )     }     def addvertex( vert: vertexlike[t] ): digraph[t] =     {       new digraph[t]( vertices + ( vert.apply -> vert ) )      } } 

vertices stored in map going type t vertexlike[t]. vertex holds adjacency list specific vertex. heres vertexlike looks like:

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 )               else         new vertex[t]( t, dest :: adjlist ) } 

( yes... realize apply method in class useless , works on objects. realized little later ).

anyways, have sample graph have 80,000 vertices. adding vertices graph taking way long. tried things functionally , in immutable way. whenever add vertex or edge graph, new graph ( tried make sure constuctors of graph types weren't doing ). client code use create graph data.

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 } 

i know constructing new graphs take cycles great given i'm not doing in constructors. repeatedly creating map of vertices keep causing problems ( 1 of parameters of graph class ). ideas on bottlenecks in method appreciated. if need additional information, please let me know.

as complement answer: indeed inadvertently traverse whole synmap.keys every time call ls.tail.

what happens is:

• map.key returns value of map.keyset, custom immutable set.
• that set overrides few things, leaves tail , drop default implementation. tail implementation (from traversablelike) calls drop.
• and that's falls apart: gets implementation of drop iterablelike, , can iterable: iterate. new builder created, head of iterator dropped, iterator added builder, which traverses keys, , new collection (the tail) returned.

you can avoid conversion list altogether using iterator, like:

def vertexadder( ls: iterator[int], graph:graphlike[int] ): graphlike[int] = {   if(!ls.hasnext)      graph    else     val h = ls.next     vertexadder( ls, graph.addvertex(h) )  } 

and then:

val gr = vertexadder( synmap.keysiterator, new digraph[int]( map() ) ) 

as side note, bit sad set doesn't provides own version of tail. maybe takes head of own iterator , returns minus element.