XQuery/Timing Fibonacci algorithms

From Wikibooks, open books for an open world
Jump to: navigation, search

Fibonacci algorithms[edit]

Fibonacci 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 and but requiring repeated re-evaluations of intermediate values. So how about bottom-up, starting with the knowns 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[edit]

Just 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[edit]

Calling the timer with n ranging from 1 to max will generate the required data. Rather than simply outputing 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}
          <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[edit]

This 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[edit]

For 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,"&amp;chs=",$chartSize,"&amp;chd=t:",$points)
return
   <img src="{$uri}"/>
};

The final script[edit]

Finally, 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, $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,"&amp;chs=",$chartSize,"&amp;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&#160;XHTML&#160;1.0&#160;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>

Execution[edit]

execute (with preset limits) on the CEMS server.