时间戳

首页 > 解决方案 > 递归发生时的Scala StackOverflows

scala - 递归发生时的Scala StackOverflows

问题描述

嗨，我有一个 BronKerbosch 算法，用于检测使用 scala 实现的社区。它有一个包含超过 100000 个节点的数据集。当我运行代码时，它给出了一个错误提示 stackoverflows。我也添加了@tailrec 注释。下面我添加了代码以及错误

import org.apache.spark.SparkContext
import org.apache.spark.graphx.Graph.graphToGraphOps
import org.slf4j.{Logger, LoggerFactory}
import scala.annotation.tailrec
import scala.collection.mutable.{ArrayBuffer, Set => MutableSet}
import scala.reflect.ClassTag

class BronKerbosch[VD: ClassTag, ED: ClassTag](sc: SparkContext,
                                           inputGraph: Graph[VD, ED])  {



  private val logger: Logger = 
  LoggerFactory.getLogger(classOf[BronKerbosch[VD, ED]]);

  private val sparkContext: SparkContext = sc;

  private var graph: Graph[VD, ED] = inputGraph;

  private var neighbourVerticesMap = 
  graph.collectNeighborIds(EdgeDirection.Either)
  .collect().map(vertex => (vertex._1.asInstanceOf[Long], vertex._2))
  .toMap;

  def runAlgorithm = {

    logger.info("Starting BronKerbosch Algorithm");
    var potentialClique = Array[Long]()
    var candidates = graph.vertices.map(vertex => 
    vertex._1.asInstanceOf[Long]).collect().to[ArrayBuffer];

    var alreadyFound = ArrayBuffer[Long]();

    var cliques = ArrayBuffer[Array[Long]]()

    findCliques(potentialClique, candidates, alreadyFound, cliques);

    cliques;
  }


  private def findCliques(potentialClique: Array[Long],candidates: ArrayBuffer[Long], alreadyFound: ArrayBuffer[Long],cliques: ArrayBuffer[Array[Long]]): Unit = {

    if (candidates.isEmpty && alreadyFound.isEmpty) {
      cliques.append(potentialClique)

    }
    @tailrec
    var originalCandidates = candidates
    candidates.foreach { candidateVertex =>
    {
     var neighbourVertices = neighbourVerticesMap.getOrElse(candidateVertex, Array[Long]())

     findCliques((potentialClique :+ candidateVertex).distinct,candidates.intersect(neighbourVertices),alreadyFound.intersect(neighbourVertices), cliques)
  }


  }
 }
 }

下面是错误

Exception in thread "main" java.lang.StackOverflowError
at 
scala.collection.mutable.HashTable$class.findEntry(HashTable.scala:132)
at scala.collection.mutable.HashMap.findEntry(HashMap.scala:40)
at scala.collection.mutable.HashMap.apply(HashMap.scala:64)
at scala.collection.SeqLike$$anonfun$occCounts$1.apply(SeqLike.scala:481)
at scala.collection.SeqLike$$anonfun$occCounts$1.apply(SeqLike.scala:481)
at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
at scala.collection.mutable.WrappedArray.foreach(WrappedArray.scala:35)
at scala.collection.SeqLike$class.occCounts(SeqLike.scala:481)
at scala.collection.SeqLike$class.intersect(SeqLike.scala:469)
at scala.collection.AbstractSeq.intersect(Seq.scala:41)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply$mcVJ$sp(BronKerbosch.scala:57)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at scala.collection.mutable.ResizableArray$class.foreach(ResizableArray.scala:59)
at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
at com.creative.graphx.BronKerbosch.com$creative$graphx$BronKerbosch$$findCliques(BronKerbosch.scala:53)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply$mcVJ$sp(BronKerbosch.scala:57)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at scala.collection.mutable.ResizableArray$class.foreach(ResizableArray.scala:59)
at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
at com.creative.graphx.BronKerbosch.com$creative$graphx$BronKerbosch$$findCliques(BronKerbosch.scala:53)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply$mcVJ$sp(BronKerbosch.scala:57)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at com.creative.graphx.BronKerbosch$$anonfun$com$creative$graphx$BronKerbosch$$findCliques$1.apply(BronKerbosch.scala:53)
at scala.collection.mutable.ResizableArray$class.foreach(ResizableArray.scala:59)
at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
at com.creative.graphx.BronKerbosch.com$creative$graphx$BronKerbosch$$findCliques(BronKerbosch.scala:53)

解决这个问题的最佳方法是什么？

标签： scalagraph-algorithm

解决方案

这段代码有很多问题，但肯定不是尾递归的。

尾递归要求函数只执行一次递归调用，并且该调用必须是函数中的最后一个操作。（代码中可能有多个调用，但通过代码的任何给定路径只能调用一个）

在您的代码中，递归调用findCliques位于foreach循环内，因此可能会多次调用它，每个候选者调用一次。仅此一项就可能是堆栈溢出的原因。

您的@tailrec注释不起作用，因为它需要在函数定义之前，而不是在函数中间。

代码的其他问题包括格式错误、不必要地使用var、未使用的值 ( originalCandidates) 以及过多的可变数据结构。

推荐阅读