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，這可能會給一些意想不到的併發症。