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>