はじめに

一度行った検索結果や演算を何度も使う場合は、その内容を一旦変数に格納しておき、そこから使いまわすのはよくある手法かと思います。今回はMarkLogicにおけるXQueryでその例を示しましょう。

ループ内で何度も使われる処理は、ループ手前に移動する

以下のXQueryを見てみましょう。

・・・
for $uri in $uri-seq
  let $flg := cts:search(/*, cts:document-query("/r/setting.xml"))
  let $map := map:map()
  let $_ := 
    for $i in $flg/repeat
    return map:put($map, $flg/key/text(), $flg/value/text())
  let $doc := cts:search(/*, cts:document-query($uri))
  let $shopState := map:put($map, $doc/state/text())
・・・

このソースコードでは、/r/setting.xmlに対する検索をループ内で何度も行うことになります。この検索にかかわる部分をループ前に切り出してあげましょう。

・・・
let $flg := cts:search(/*, cts:document-query("/r/setting.xml"))
let $map := map:map()
let $_ := 
  for $i in $flg/repeat
  return map:put($map, $flg/key/text(), $flg/value/text())
for $uri in $uri-seq
  let $doc := cts:search(/*, cts:document-query($uri))
  let $shopState := map:put($map, $doc/state/text())
・・・

/r/setting.xmlに対する検索は1回だけになり、ディスクアクセスが緩和されます。

フィボナッチ数列計算を例にした再帰関数の変更例

上記のように、一度計算した結果を再利用するプログラミング手法として動的計画法という考えがあります。以下はフィボナッチ数列F_(n+2) = F_n+ F_(n+1) (n≧0), F_0=0, F_1=1の計算を行う再帰関数と動的計画法適用例です。

☆再帰関数
数学の漸化式は、再帰関数によって計算できます。F30を求めるためにはF29とF28が必要であり、F29を求めるためには・・・とトップダウンから計算を始めていきます。

declare function local:outer-func($n as xs:integer){
  if($n = 0) then 0
  else if($n = 1) then 1
  else local:outer-func($n - 2) + local:outer-func($n - 1)
};

☆動的計画法
F0とF1からF2を求める、このとき保持しておいたF1とF2からF3を求める・・・というボトムアップに計算を進めていく手法です。

declare function local:dp-func($n as xs:integer){
  if($n = 0) then 0
  else if($n = 1) then 1
  else (
    let $f0 := 0
    let $f1 := 1
    let $fn := 1
    let $_ := 
      for $i in (2 to $n)
        let $_ := xdmp:set($fn, $f0 + $f1)
        let $tmp := $f0
        let _ := xdmp:set($f0, $f1)
        let _ := xdmp:set($f1, $tmp + $f1)
        return ()
    return $fn
  )
};

試しに手元のPCでクエリコンソール上で30番目のフィボナッチ数(832040)の計算をProfile実行したところ、再帰関数が13秒だったのに動的計画法は0秒(測定不可能)でした。

このような差が出る理由は再帰関数が個々の結果を共有せず何度も同じF0+F1という基底状態の足し算を行っているからです。計算量は指数関数オーダーとなります。
これに対して動的計画法はより大きなフィボナッチ数を計算するための情報はきちんと保持して再利用しています。MarkLogicではxdmp:setという関数でループ内の変数更新をサポートしています。計算量は線形時間オーダーです。

おわりに

ループ内での処理を外側に出すのはそれほど難しいことではありませんね。チューニング以前にルールとして習慣づけておきたいところです。
動的計画法そのものは適用する場面がそれほどないかもしれませんが、基本的な考えは結果を保持して再利用するというものです。XQueryで再帰関数を含むプロシージャを組む場合は一考の価値がありそうです。

\def\textsmall#1{%
  {\rm\scriptsize #1}
}

免責事項

$\textsmall{当ユーザ会は本文書及びその内容に関して、いかなる保証もするものではありません。}$
$\textsmall{万一、本文書の内容に誤りがあった場合でも当ユーザ会は一切責任を負いかねます。}$
$\textsmall{また、本文書に記載されている事項は予告なしに変更または削除されることがありますので、予めご了承ください。}$