2014-01-25 40 views
3

我實現了一個鄰接表爲Array[List[Int]]和基本圖表生成程序是這樣的圖作爲鄰接表性能

val edges : List[(Int, Int)] = ... 
    val adj = Array.fill(v)(List.empty[Int]) 
    edges foreach { case(t, h) => adj(t) = h::adj(t) } 

此實現的作品比Java實現(500萬個邊緣測試)的約四倍慢在ArrayList<Integer>[]。在Java邊緣最初存儲爲ArrayList<int[]>。任何關於如何使Scala版本更快的想法?

+0

如果性能是首要因素,請使用兩個數組。這些對由給定索引處的每個數組中的條目形成。 –

+0

您可以提供可以運行的完整的Java和Scala程序嗎? –

回答

0

對於邊緣的初始集合,

scala> val edges : List[(Int,Int)] = List((1,2),(1,3),(1,4),(2,3),(2,4),(3,4)) 
e: List[(Int, Int)] = List((1,2), (1,3), (1,4), (2,3), (2,4), (3,4)) 

考慮此重排,

scala> val adj = edges.groupBy{_._1}.map { case (k,v) => (k, v.map {_._2}) } 
res21: scala.collection.immutable.Map[Int,List[Int]] = Map(2 -> List(3, 4), 1 -> List(2, 3, 4), 3 -> List(4)) 

也許使用par方法,它提供了一個並行實現的給定集合,並且其相關聯的方法的,

scala> val adj = edges.par.groupBy{_._1}.map { case (k,v) => (k, v.map {_._2}) } 

可能提高效率es特別是對於大型收藏品,例如最初的500萬條邊緣。