StackOverflow通过 Scala 处理深度优先迭代时出错

Question

我打算递归迭代圆圈区域内的所有网格，下面的代码将执行深度优先搜索。但是在 204 堆之后，java.lang.StackOverflowError会被扔掉。

def geohash_circle_around_point(lat: Double, lon: Double, radius: Double) = {
  def expand_neighbors_impl(ghCenter: GeoHash, ghCur: GeoHash, buffer: collection.mutable.Set[GeoHash]): Unit = {
    // MARK: DP: check whether it's iterated already or not
    if(buffer contains ghCur)  {
      return
    }
    buffer += ghCur
    for(ghAround <- get4GeoHashAround(ghCur))  {
      if(distanceBetweenGeohash(ghCenter, ghAround) <= radius)  {
        expand_neighbors_impl(ghCenter, ghAround, buffer)
      }
    }
  }
  def get4GeoHashAround(gh: GeoHash): Array[GeoHash] = {
    Array(gh.getNorthernNeighbour, gh.getSouthernNeighbour, gh.getWesternNeighbour, gh.getEasternNeighbour)
  }
  def distanceBetweenGeohash(gh1: GeoHash, gh2: GeoHash) = {
    haversine(gh1.getBoundingBoxCenterPoint.getLatitude, gh1.getBoundingBoxCenterPoint.getLongitude, gh2.getBoundingBoxCenterPoint.getLatitude, gh2.getBoundingBoxCenterPoint.getLongitude)
  }
  val ghCenter = GeoHash.withBitPrecision(lat, lon, 40)
  val s = collection.mutable.Set[GeoHash]()
  expand_neighbors_impl(ghCenter, ghCenter, s)
  s.map(_.getBoundingBox)
}

堆栈跟踪如下所示：

Exception in thread "main" java.lang.StackOverflowError
  at scala.collection.mutable.HashSet.index(HashSet.scala:40)
  at scala.collection.mutable.FlatHashTable$class.findElemImpl(FlatHashTable.scala:126)
  at scala.collection.mutable.FlatHashTable$class.containsElem(FlatHashTable.scala:121)
  at scala.collection.mutable.HashSet.containsElem(HashSet.scala:40)
  at scala.collection.mutable.HashSet.contains(HashSet.scala:57)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:32)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:39)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:37)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:186)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:37)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:39)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:37)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:186)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:37)
....

谁能给出一些建议？谢谢！

附言

equals和hashCode的实施 对于GeoHash：

public boolean equals(Object obj) {
    if(obj == this) {
        return true;
    } else {
        if(obj instanceof GeoHash) {
            GeoHash other = (GeoHash)obj;
            if(other.significantBits == this.significantBits && other.bits == this.bits) {
                return true;
            }
        }
        return false;
    }
}
public int hashCode() {
    byte f = 17;
    int f1 = 31 * f + (int)(this.bits ^ this.bits >>> 32);
    f1 = 31 * f1 + this.significantBits;
    return f1;
}

Answer 1

似乎您真的需要 200 多次40精度的调用......

您可能需要考虑将递归重写为尾递归，以便编译器进行优化。这是执行此操作的方法：

@tailrec
def expand_neighbors_impl(ghCenter: GeoHash, toGoThrough: List[GeoHash], buffer: Set[GeoHash] = Set()): Set[GeoHash] = {
  toGoThrough.headOption match {
    case None => buffer
    case Some(ghCur) =>
      if (buffer contains ghCur) {
        expand_neighbors_impl(ghCenter, toGoThrough.tail, buffer)
      }
      else {
        val neighbors = get4GeoHashAround(ghCur).filter(distanceBetweenGeohash(ghCenter, _) <= radius)
        expand_neighbors_impl(ghCenter, neighbors ++: toGoThrough, buffer + ghCur)
      }
  }
}
def expand_neighbors_impl(ghCenter: GeoHash, ghCur: GeoHash): Set[GeoHash] =
  expand_neighbors_impl(ghCenter, List(ghCur))

除了使用尾递归之外，它还避免使用可变Set，这可能会带来一些意想不到的复杂情况。