java - 通过 scala 处理深度优先迭代时出现 stackoverflowerror

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

有人可以给一些建议吗？谢谢!

附注

GeoHash 的 equals 和 hashCode 实现:

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

看来您确实需要以 40 精度进行 200 多次调用...

您可能需要考虑将递归重写为尾递归，以便编译器进行优化。有一种方法可以做到这一点:

@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，这可能会带来一些意想不到的复杂性。