1

我有一个大文本文件，每行有 2 个数字，表示行中第一个和第二个元素之间的有向边。我正在尝试在 scala 中构建一个图形，将其表示为Map[tailOfEdge,ArrayofHeadsOfEdges]

这样，如果我的文件有

   1   2
   1   3
   2   3

这应该是Map(1-> Array(2,3),2-> Array(3))

但是，我的文件非常大（约 500 万行）

我最初试图阅读整个文件，使用toArray然后使用groupBy和积累这种方式。但是，我一直遇到堆大小问题（更不用说他可能是一种非常幼稚的方法）

现在，对我有用的（虽然非常慢）是创建一个可变映射，循环遍历文件的每一行（使用 for 循环），将行分成 2 个数字。给定节点的所有边在文件中都是连续的，所以我只跟踪我期望的节点，如果它是同一个节点，我会累积新的边，如果它是一个新节点，那么我添加完成的累积数组到地图，重置我期望的节点并使用这个新列表重新启动累积数组。

肯定有更好的方法来做到这一点......

4

2 回答 2

3

您可以使用左折叠和不可变映射非常干净地做到这一点：

val source = scala.io.Source.fromFile(args(0))

val graph = source.getLines.foldLeft[Map[Int, Vector[Int]]](
  Map.empty withDefaultValue Vector.empty
) {
  case (acc, line) => line.trim.split("\\s+").map(_.toInt) match {
    case Array(k, v) => acc.updated(k, acc(k) :+ v)
  }
}

source.close()

这在我的机器上大约 7 秒内运行在一个包含 500 万行的文件上。getLines是一个迭代器，因此您不需要将整个文件读入内存。

我不确定“非常慢”对您意味着什么。这个实现不对文件中键的顺序做任何假设，如果你真的需要它比每秒一百万行快，你应该能够利用它们是有序的事实. 但它可能不会有太大帮助，而且几乎肯定会涉及更复杂的代码。

你也可以使用数组而不是向量——我刚刚在这里使用向量来表明你甚至不需要头部列表是可变的。

于 2013-08-19T20:55:03.933 回答
0

如果您的输入序列真的很大，那么其他解决方案最终会OOME。这是我的命令式解决方案，它依赖于调用者在生成组时干净地处理它们，但 AFAICT 在恒定堆栈中运行并保留最少的堆供自己使用。:)

希望其他人可以对 Stream 或具有类似性能特征的东西进行折叠，只要您小心不要保留对头部的引用。

/**
 * @param in       the input
 * @param disposal a function that will dispose of groups as they're identified
 */
def groupByInfinite[A,B](in: Iterator[(A,B)])(disposal: (A,Seq[B]) => Unit) {

  /**
   * @param in      the input
   * @param current the current A value
   * @param got     the B values being accumulated for the current A value
   */
  @tailrec
  def group0(in: Iterator[(A,B)], current: A, got: Seq[B]) {
    if (in.hasNext) {
      val (a,b) = in.next()
      if (a == current) {
        group0(in, a, got :+ b)
      } else {
        disposal(current, got)
        group0(in, a, Vector(b))
      }
    } else {
      disposal(current, got)
    }
  }

  if (in.hasNext) {
    val (a,b) = in.next()
    group0(in, a, Vector(b))
  }
}
于 2013-08-19T21:31:48.927 回答