XQuery/计时斐波那契算法
< XQuery
斐波那契是计算机科学的“你好，世界”。一个遵循斐波那契数列定义的递归函数在每种语言中看起来都差不多。以下是 XQuery 版本
declare function myfn:fib-recur($n as xs:integer) as xs:integer? {
if ($n <0) then ()
else if ($n = 0) then 0
else if ($n=1) then 1
else myfn:fib-recur($n - 1) + myfn:fib-recur($n - 2)
};
空序列在这里用作函数未定义时的返回值，因此返回类型是可选整数。自顶向下，目标导向，接近数学定义，但需要重复重新评估中间值。那么自底向上，从已知开始，向上工作到目标呢？
declare function myfn:fib-itr-x($n as xs:integer, $m1 as xs:integer, $m2 as xs:integer) as xs:integer {
if ($n = 1)
then $m2
else myfn:fib-itr-x($n - 1, $m2, $m1 + $m2)
};
使用“前门”函数开始
declare function myfn:fib-itr($n as xs:integer) as xs:integer? {
if ($n < 0) then ()
else if ($n = 0) then 0
else myfn:fib-itr-x($n, 0, 1)
};
与这种尾递归公式相比，变量更新的迭代解决方案看起来相当凌乱，这种风格对于 XQuery 中的许多算法至关重要。
递归公式到底差多少？我们需要计时调用，现在我们真的需要那些高阶函数，这样我们就可以将任一 fib 函数传递给一个计时函数来执行。进入 eXists 函数模块。这些将 XQuery 从 XML 查询语言提升到可行的 Web 应用程序平台。util 模块提供了两个函数
* util:function(qname,arity) to create a function template which can be passed to * util:call (function, params)to evaluate the function
因此我们可以使用以下方法创建递归函数模板
let $call-fib-recur := util:function(QName("http:example.com/myfn","myfn:fib-recur"),1)
计时函数采用一个函数、要传递给函数的一系列参数以及一个重复次数。计时基于系统时间，时间差转换为秒，然后转换为毫秒
declare function myfn:time-call($function as function, $params as item()* ,$reps as xs:integer ) as xs:decimal {
let $start := util:system-time()
let $result :=
for $i in 1 to $reps
return util:call($function, $params)
let $end := util:system-time()
let $runtimems := (($end - $start) div xs:dayTimeDuration('PT1S')) * 1000
return $runtimems div $reps
};
并调用它作为
myfn:time-call($call-fib-recur,10,5)
使用从 1 到 max 范围内的 n 调用计时器将生成所需数据。我们不需要简单地输出此数据，而是需要包含结果的中间 XML 数据结构。然后可以将它转换为不同的表示形式或稍后进行分析，以拟合数据的曲线，或者可能导出到电子表格。
let $runs :=
<dataset>
{ for $n in -1 to $max
return
<tuple>
<n>{$n}</n>
<fib>{ myfn:fib-itr($n) }</fib>
<recursive>{ myfn:time-call($call-fib-recur,$n,$reps) }</recursive>
<iterative>{ myfn:time-call($call-fib-itr,$n,$reps) } </iterative>
</tuple>
}
</dataset>
此数据结构可以转换为表格，遍历元组。
declare function myfn:dataset-as-table($dataset ) as element(table) {
<table>
<tr>
{for $data in $dataset/*[1]/*
return
<th>{name($data)}</th>
}
</tr>
{for $tuple in $dataset/*
return
<tr>
{for $data in $tuple/*
return
<td>{string($data)}</td>
}
</tr>
}
</table>
};
这里使用 XPath name() 函数从标签名转换为字符串。这种反射允许编写非常通用的函数，并且是将问题特定结构转换为通用函数的关键技术。请注意，数据集没有类型。这是因为该函数是用对结构的最小要求编写的，这将需要一种允许的模式语言来表达。
对于图表，此基本矩阵可以直接导入 Excel，或者，由于有了很棒的 GoogleCharts，可以直接导入到简单的折线图中。数据集的选定列被提取并用逗号连接，然后所有数据集用管道连接。
declare function myfn:dataset-as-chart($dataset, $vars as xs:string+) as element(img) {
let $series :=
for $var in $vars
return string-join( $dataset/*/*[name(.) = $var],",")
let $points := string-join($series ,"|" )
let $chartType := "lc"
let $chartSize := "300x200"
let $uri := concat("http://chart.apis.google.com/chart?",
"cht=",$chartType,"&chs=",$chartSize,"&chd=t:",$points)
return
<img src="{$uri}"/>
};
最后，添加一些介绍、页面布局和 CSS，最终脚本看起来像这样
declare namespace myfn = "http://www.cems.uwe.ac.uk/xmlwiki/myfn";
declare function myfn:time-call($function as function(xs:integer) as xs:integer?, $params ,$reps as xs:integer ) as xs:decimal {
let $start := util:system-time()
let $result :=
for $i in 1 to $reps
return util:call($function ,$params)
let $end := util:system-time()
let $runtimems := (($end - $start) div xs:dayTimeDuration('PT1S')) * 1000
return $runtimems div $reps
};
declare function myfn:fib-recur($n as xs:integer) as xs:integer? {
if ($n <0) then ()
else if ($n = 0) then 0
else if ($n=1) then 1
else myfn:fib-recur($n - 1) + myfn:fib-recur($n - 2)
};
declare function myfn:fib-itr($n as xs:integer) as xs:integer? {
if ($n < 0) then ()
else if ($n = 0) then 0
else myfn:fib-itr-x($n, 0, 1)
};
declare function myfn:fib-itr-x($n as xs:integer, $m1 as xs:integer, $m2 as xs:integer) as xs:integer {
if ($n = 1)
then $m2
else myfn:fib-itr-x($n - 1,$m2, $m1 + $m2)
};
declare function myfn:dataset-as-chart($dataset, $vars as xs:string+) as element(img) {
let $series :=
for $var in $vars
return string-join( $dataset/*/*[name(.) = $var],",")
let $points := string-join($series ,"|" )
let $chartType := "lc"
let $chartSize := "300x200"
let $uri := concat("http://chart.apis.google.com/chart?",
"cht=",$chartType,"&chs=",$chartSize,"&chd=t:",$points)
return
<img src="{$uri}"/>
};
declare function myfn:dataset-as-table($dataset ) as element(table) {
<table>
<tr>
{for $data in $dataset/*[1]/*
return
<th>{name($data)}</th>
}
</tr>
{for $tuple in $dataset/*
return
<tr>
{for $data in $tuple/*
return
<td>{string($data)}</td>
}
</tr>
}
</table>
};
declare option exist:serialize "method=xhtml media-type=text/html omit-xml-declaration=no indent=yes
doctype-public=-//W3C//DTD XHTML 1.0 Transitional//EN
doctype-system=http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";
let $max := xs:integer(request:get-parameter("max",1))
let $reps := xs:integer(request:get-parameter("reps",1))
let $call-fib-recur := util:function(QName("http://www.cems.uwe.ac.uk/xmlwiki/myfn","myfn:fib-recur"),1)
let $call-fib-itr:= util:function(QName("http://www.cems.uwe.ac.uk/xmlwiki/myfn","myfn:fib-itr"),1)
let $runs :=
<dataset>
{ for $n in -1 to $max
return
<tuple>
<n>{$n}</n>
<fib>{ myfn:fib-itr($n) } </fib>
<recursive>{ myfn:time-call($call-fib-recur,$n,$reps) }</recursive>
<iterative>{ myfn:time-call($call-fib-itr,$n,$reps) } </iterative>
</tuple>
}
</dataset>
return
<html>
<head>
<title>Fibonacci with XQuery</title>
<style type="text/css">
<![CDATA[
body {
background-color: #FFFFDD;
}
#graph {
float: right;
width: 50%;
padding: 10px;
}
#table {
float: left;
width: 50%
padding: 10px;
}
td,th {
border-right: 1px solid #FFFF00;
border-bottom: 1px solid #FFFF00;
padding: 6px 6px 6px 12px;
}
]]>
</style>
</head>
<body>
<h1>Fibonnacci from 1 to {$max} with {$reps} repetitions</h1>
<p>Recursive and iterative methods in XQuery on eXist.db</p>
<div id="graph">
{myfn:dataset-as-chart($runs,("recursive","iterative"))}
</div>
<div id="table">
{myfn:dataset-as-table($runs)}
</div>
</body>
</html>