如何处理深的XQuery递归问题

Question

我上XQuery library for getting simple geospatial information from GPS files (it's called GPXQuery and available at GitHub)工作。 GPX文件通常包含GPS坐标的轨迹，并且可能变得相当大。我最大的测试文件有20'000点。 GPX很简单：

<gpx version="1.1" xmlns="http://www.topografix.com/GPX/1/1"> 
    <trk> 
    <name>Berkeley Test Walk #1</name> 
    <trkseg> 
     <trkpt lon="-122.26794633083045" lat="37.878523925319314"> 
     <ele>78.4000015258789</ele> 

有<trkpt>元素，代表了所有记录的GPS坐标的长序列。我希望能够处理至少100000个，希望更多。

我的第一个稍微复杂的函数计算了记录的GPS轨迹的距离。数学在这里并不重要。问题是我遇到了堆栈问题。以我的20,000点为例，我的标准萨克森设置已经停止。我相信，这可以通过更慷慨的内存分配来解决，但我想知道是否有更重要的内容可能会发生。

我的函数应符合尾递归优化，但是这是一个有点很难说，可能与产品不同而异。这里的功能（S），它们通过gpxquery:trk-distance($GPX/gpx:gpx)[1]调用来获得一个给定的GPX文件$GPX第一GPX轨道的距离：

module namespace gpxquery = "https://github.com/dret/GPXQuery"; 

declare namespace xsd = "http://www.w3.org/2001/XMLSchema"; 
declare namespace math = "http://www.w3.org/2005/xpath-functions/math"; 
declare namespace gpx = "http://www.topografix.com/GPX/1/1"; 
declare variable $gpxquery:earth-radius := 6371000.0; 

declare function gpxquery:trk-distance($gpx as element(gpx:gpx)) 
    as xsd:float* 
{ 
    for $trk in 1 to count($gpx/gpx:trk) 
     return sum(gpxquery:trk-distance-recurse($gpx/gpx:trk[$trk]/gpx:trkseg/gpx:trkpt)) 
}; 

declare function gpxquery:trk-distance-recurse($trkpts as element(gpx:trkpt)*) 
    as xsd:float* 
{ 
    if (count($trkpts) le 1) 
     then 0 
     else (
      gpxquery:distance-between-points($trkpts[1]/@lat, $trkpts[1]/@lon, $trkpts[2]/@lat, $trkpts[2]/@lon) , 
      gpxquery:trk-distance-recurse($trkpts[position() gt 1]) 
    ) 
}; 

declare function gpxquery:distance-between-points($lat1 as xsd:float, $lon1 as xsd:float, $lat2 as xsd:float, $lon2 as xsd:float) 
    as xsd:float 
{ 
    let $dlat := ($lat2 - $lat1) * math:pi() div 180 
    let $dlon := ($lon2 - $lon1) * math:pi() div 180 
    let $rlat1 := $lat1 * math:pi() div 180 
    let $rlat2 := $lat2 * math:pi() div 180 
    let $a  := math:sin($dlat div 2) * math:sin($dlat div 2) + math:sin($dlon div 2) * math:sin($dlon div 2) * math:cos($rlat1) * math:cos($rlat2) 
    let $c  := 2 * math:atan2(math:sqrt($a), math:sqrt(1-$a)) 
    return xsd:float($c * $gpxquery:earth-radius) 
}; 

有什么我应该/可以在代码结构方面有什么不同和算法，以避免这些内存问题更大的文件？或者这对于一般问题看起来是一种合理的方法，而且我使用库的人都必须确保运行时环境能够处理深度嵌套的递归调用的需求？

从人与递归函数工作，遇到类似的问题任何反馈将不胜感激。

Answer 1

Saxon不会将此函数识别为尾递归，因为它将递归运算符（逗号运算符）应用于递归结果，并且对结果应用的任何处理均将其作为尾调用使其失效。

有趣的是，如果你重写它作为XSLT命名模板，那么它可能会获得资格成为尾递归。这是因为XSLT命名模板（撒克逊）在“推”模式本身进行评价 - 他们写他们的结果依次输出序列 - 这意味着“”操作实际上是隐含的。通过一点努力，人们可能会为功能设计出类似的策略。

但我想明白为什么这个递归甚至是必要的。

至于我可以看到你正在实施的算法是采取序列$ S和计算沿着

f($S[1], $S[2]) + f($S[2], $S[3]) + f($S[3], $S[4]) ... 

就是你申请一个函数来连续对相邻线的东西值，然后计算这些函数应用程序的总和。

其中$ f是要应用的功能，你可以这样写

sum(for-each-pair($S, tail($S), $f)) 

。

或者更传统的XQuery 1。0风格你可以写类似

sum(
for $i in 1 to count($S)-1 
return f($S[i], $S[i+1]) 
) 

Answer 2

非递归版本：更短，更快，更少的内存要求：

declare function gpxquery:trk-distance($gpx as element(gpx:gpx)) 
    as xsd:double* 
{ 
    for $trk in 1 to count($gpx/gpx:trk) 
    let $trkpts := $gpx/gpx:trk[$trk]/gpx:trkseg/gpx:trkpt 
    return sum(
     for $i in 1 to count($trkpts)-1 
     return gpxquery:haversine($trkpts[$i]/@lat, $trkpts[$i]/@lon, $trkpts[$i+1]/@lat, $trkpts[$i+1]/@lon) 
    ) 
}; 

declare function gpxquery:haversine($lat1 as xsd:double, $lon1 as xsd:double, $lat2 as xsd:double, $lon2 as xsd:double) 
    as xsd:double 
{ 
    (: This is the Haversine formula as described by http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates :) 
    let $dlat := ($lat2 - $lat1) * math:pi() div 180 
    let $dlon := ($lon2 - $lon1) * math:pi() div 180 
    let $rlat1 := $lat1 * math:pi() div 180 
    let $rlat2 := $lat2 * math:pi() div 180 
    let $a  := math:sin($dlat div 2) * math:sin($dlat div 2) + math:sin($dlon div 2) * math:sin($dlon div 2) * math:cos($rlat1) * math:cos($rlat2) 
    let $c  := 2 * math:atan2(math:sqrt($a), math:sqrt(1-$a)) 
    return xsd:double($c * 6371000.0) 
};