草庐IT

xml - 如何处理深度 XQuery 递归问题

coder 2024-06-29 原文

我正在研究 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 坐标。我希望能够处理至少 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)
};

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

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

最佳答案

Saxon 不将此函数标识为尾递归，因为它将运算符(逗号运算符)应用于递归的结果，并且对结果应用的任何处理都将其视为尾调用。

有趣的是，如果您将其重写为 XSLT 命名模板，那么它可能符合尾递归的条件。这是因为 XSLT 命名模板(在 Saxon 中)是在“推”模式下本地计算的——它们将结果按顺序写入输出序列——这意味着“,”操作实际上是隐式的。通过一些努力，人们可能会为函数设计出类似的策略。

但我试图理解为什么这种递归是必要的。

据我所知，您正在实现的算法是采用序列 $S 并按照以下行计算某些内容

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

也就是说，您将一个函数应用于连续的相邻值对，然后计算这些函数应用的总和。

你可以这样写

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

关于xml - 如何处理深度 XQuery 递归问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34405105/

何处XQuerycodegpxquerymathxmlrecursiontail-recursiongpx

有关xml - 如何处理深度 XQuery 递归问题的更多相关文章

  1. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  2. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  3. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  4. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  5. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  6. ruby-on-rails - Enumerator.new 如何处理已通过的 block ？ - 2

    我在理解Enumerator.new方法的工作原理时遇到了一些困难。假设文档中的示例:fib=Enumerator.newdo|y|a=b=1loopdoy[1,1,2,3,5,8,13,21,34,55]循环中断条件在哪里，它如何知道循环应该迭代多少次(因为它没有任何明确的中断条件并且看起来像无限循环)？ 最佳答案 Enumerator使用Fibers在内部。您的示例等效于:require'fiber'fiber=Fiber.newdoa=b=1loopdoFiber.yieldaa,b=b,a+bendend10.times.m

  7. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  8. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  9. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  10. 【高数】用拉格朗日中值定理解决极限问题 - 2

    首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有，  也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加

随机推荐