scala - 图作为邻接表性能

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

此实现比基于 ArrayList<Integer>[] 的 Java 实现慢大约四倍(使用 500 万条边进行测试) .在 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}) }

可能会提高效率，尤其是对于大型集合，例如原始的 500 万条边。