XQuery/Timing Fibonacci algorithms
Fibonacci algorithms
editFibonacci is the computer science 'hello world'. A recursive function which follows the definition of the Fibonacci series looks pretty much the same in every language. Here is the XQuery version:
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)
};
The empty sequence is used here as a return when the function is undefined so the return type is an optional integer. Top-down, goal-oriented, close to the mathematical definition but requiring repeated re-evaluations of intermediate values. So how about bottom-up, starting with the known and working up to the goal?
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)
};
with a 'front-door' function to get started:
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)
};
Iterative solutions in which variables are updated look rather messy by comparison with this tail-recursive formulation, a style essential to many algorithms in XQuery.
Timing
editJust how much worse is the recursive formulation? We need to time the calls, and now we really could do with those higher order functions so we can pass either fib function to a timer function to execute. Step in eXists function modules. These raise XQuery from an XML query language to a viable web application platform. The util module provides two functions:
* util:function(qname,arity) to create a function template which can be passed to * util:call (function, params)to evaluate the function
so we can create the recursive function template with:
let $call-fib-recur := util:function(QName("http:example.com/myfn","myfn:fib-recur"),1)
The timer function takes a function, a sequence of the parameters to be passed to the function and a repetition number. The timing is based on system time and the time difference converted to seconds and then to milliseconds:
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
};
and call it as
myfn:time-call($call-fib-recur,10,5)
An intermediate data structure
editCalling the timer with n ranging from 1 to max will generate the required data. Rather than simply outputting this data, we need an intermediate XML data structure containing the results. This can then be transformed into different representation or analysed later, to fit a curve to the data perhaps or export to a spreadsheet.
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>
Results as a table
editThis data structure can be transformed to a table, iterating over the tuples.
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>
};
Here the XPath name() function is used to convert from the tag names to strings. This reflection allows very generic functions to be written and is a key technique for making the transition from problem-specific structures to generic functions. Note that the dataset has not been typed. This is because the function is written with minimal requirements of the structure which would require a permissive schema language to express.
Results as a graph
editFor graphing, this basic matrix could be imported directly into Excel, or, thanks to the wonderful GoogleCharts, to a simple line graph. Selected columns of the dataset are extracted and joined with commas, then all datasets joined with pipes.
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}"/>
};
The final script
editFinally, adding some intro, some page layout and CSS , the final script looks like:
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>