如何处理深度XQuery递归问题

Question

我正在开发一个基于XQuery的库，用于从GPS文件中获取简单的地理空间信息（称为GPXQuery，可在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坐标。我希望能够处理至少100,000个，希望更多。

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

我的函数应该符合尾递归优化的要求，但这有点难以判断，可能因产品而异。以下是函数，并且它们被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)
};

针对更大的文件，我是否需要在代码结构和算法方面做出不同的调整以避免这些内存问题？或者，看起来这是解决一般问题的合理方法，使用该库的人只需确保运行时环境能够处理深度嵌套递归调用的要求？

非常感谢那些使用递归函数并遇到类似问题的人提供任何反馈。

- dret

---

听起来不错。基本上，你自己回答了问题：这取决于产品，不总是容易应用尾递归。我只是在BaseX中运行它，它也没有应用尾递归。如果您有兴趣使用BaseX，我相信我们会尽最大努力改进BaseX并应用尾递归-如果您有兴趣，最好写信给邮件列表。 - dirkk

谢谢，@dirkk！你解决了关于尾递归的问题，即它不是你可以依赖的东西。所以我想知道的是：如果我想重写这个代码以更可预测的方式运行，是否有递归的方法来实现，或者是否有一些非递归的替代方案来避免堆栈问题？ - dret

Answer 1

Saxon并不将这个函数视为尾递归，因为它将一个运算符（逗号运算符）应用于递归的结果，对结果进行的任何处理都会使其失去尾调用的资格。

有趣的是，如果将其重写为XSLT命名模板，则可能会被认为是尾递归。这是因为XSLT命名模板（在Saxon中）是以“推”模式本地评估的 - 它们按顺序将其结果写入输出序列 - 这意味着“,”操作实际上是隐含的。通过一些努力，人们可能可以设计出类似的函数策略。

但我正在试图理解为什么需要这种递归。

据我所知，您正在实现的算法是获取一个序列$S并计算类似于：

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

也就是说，你正在将一个函数应用于相邻值的连续对，并计算这些函数应用的总和。

您可以这样写：

```python sum(f(x, y) for x, y in zip(lst, lst[1:])) ```

其中 `lst` 是包含要处理的值的列表，`f` 是要应用的函数。

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

$f是要应用的函数。

或者更常规的XQuery 1.0风格，您可以编写类似于以下内容：

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

- Michael Kay

---

非常感谢您以那种方式解释尾递归。此外，在这种情况下避免递归是正确的。现在代码看起来像下面展示的那样，运行速度更快，可能可以处理更大的数据集。 - dret

请点击问题旁边的勾选标记将其标记为已解决，以便后来的访问者可以看到该问题已经得到解决。 - Michael Kay

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 https://dev59.com/enRC5IYBdhLWcg3wP-dh :)
    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)
};

- dret