Graph как производительность списка смежности

Question

Я реализовал список смежности, как 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) } 

Эта реализация работает примерно в четыре раза медленнее (протестировано с 5 миллионов ребер), чем реализация Java на основе на ArrayList<Integer>[]. В ребрах Java изначально хранятся как ArrayList<int[]>. Любые идеи о том, как быстрее сделать версию Scala?

Answer 1

Для первоначального сбора ребер,

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

может повысить эффективность особенно для больших коллекций, например, для оригинальных 5 миллионов ребер.