stackoverflowror当通过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) 
.... 

任何人都可以给一些建议？谢谢！

P.S.

执行情况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

好像你真的在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，这可能会给一些意想不到的并发症。