CodeZine(コードジン)

特集ページ一覧

高パフォーマンスなストアドプロシージャの設計

9つのヒントと数独の解法を使った実例

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2007/03/08 00:00

ダウンロード ソースファイル (19.7 KB)

目次

数独解法プログラム

 私はここで具体例として、ストアドプロシージャベースの数独解法プログラムを作成しました。これにはいくつかの理由があります。1つは、数独では9×9マスの表を用いるため、この表をデータベースのテーブルとしてとらえるのはきわめて自然だということです。2つ目は、この解法プログラムは、比較的シンプルな構造をしているうえ、前節で紹介したいくつかのヒントを適切に生かすことで、ハイパフォーマンスなデータベースソリューションの実装例を示すことができるという点です。3つ目は、データベースソリューションの柔軟性のおかげで、パズルそのものを一般的な視点からとらえることができ、パズルの解法プログラムをもっと汎用的な目的に発展させるための方法が分かるという点です。

 この解法プログラムは、2つのデータベーステーブルで構成されています。1つ目のテーブルには、初期状態のパズルデータを格納します。2つ目のテーブルには、計算結果、表を埋めるスクリプト、および結果を計算するストアドプロシージャを格納します。サンプルコードを用意してあるので、この解法プログラムをご自身で試してみることもできます。

 「TEMP_GS_V1.sql」スクリプトでは、テーブルを定義しています。最初のテーブルでは、各レコードが、数独のマス目1つを表します。2つ目のテーブルでは、各レコードが、解答全体を表します。テーブルの構造をこのようにした理由は、解法プログラムを見ていく中で明らかにしていきます。とりあえず現段階では、この構造には柔軟性が必要であるということ、そしてルールと前提との混同を避ける必要があるということを頭に入れておいてください(ヒント5を参照)。

数独のルールと解法

 数独のルールは、「各行、各列、および3×3マスの各ブロックのそれぞれに、1~9の数字を重複なしで入れなくてはならない」というものです。また、前提として、初期状態の一連の数字からは、1つの正解のみが得られることになっています。そうでない場合、その問題は「有効でない」とみなされます。この前提は、現実世界のアプリケーションに置き換えて考えると、無理があるように思えます。データの状態が絶対に有効だという前提で開発するわけにはいかないからです。従って、ここで作成する数独解法プログラムでは、その点を反映することにしました。つまり、パズルの問題が有効かどうかにかかわらず、きちんと動作するようにします。そして、有効でない問題については、考え得るすべての解答を導き出すことにします。

 この解法プログラムでは、データ入力(問題作成)のためのインターフェイスは用意していません。解法プログラムの範疇から外れるためです。スクリプトを使用して「TEMP_GS」テーブルにデータを格納する必要があります。「Fill_GS.sql」スクリプトは、「TEMP_GS」テーブルにデータを格納する方法の例です。このスクリプトでは、AlEscargotという、数独の超難問のデータを格納しています。これはかつて、史上最強の難問と言われたこともある数独問題です。このパズルの解答前の初期状態を図1に示します。

図1 解答前の初期状態AlEscargotパズル
図1 解答前の初期状態AlEscargotパズル

 ストアドプロシージャCALCULATE_GSには、解法プログラムのアルゴリズムが記述されています(具体的なスクリプトについては「CALCULATE_GS_V3.sql」を参照)。この中の一連の手順には、前節で紹介したSQL Serverのヒントの実例が盛り込まれています。なお、CALCULATE_GSプロシージャは、パラメータとしてパズル番号(PUZZLE_NUM)を受け取ります。これは、マルチユーザー環境に適したソリューションを作成するときに、習慣として取り入れるとよいでしょう。各パズルにそれぞれ固有のIDを付けておけば、複数のユーザーが同一の物理テーブルを使用して、このストアドプロシージャを同時に実行できます。

ストアドプロシージャ処理手順

 CALCULATE_GSストアドプロシージャでは、以下の手順で処理を行います。

  1. テーブル変数を作成し、1~9の数値を格納します。このテーブル変数はヒント4の実例です。すなわち、このテーブルはレコード数がさほど多くないうえ、ストアドプロシージャ内で頻繁に使用し、このテーブル自身に対し3回結合することもあります。この場合は、一時テーブルよりもテーブル変数を使う方がはるかに効率的です。次に、「TEMP_GS」テーブルに対し、取り得るマス目に対応するすべての行を格納します。これは、以下の手順2、3で行います。
  2.  
  1. 最初に、シングルトンを計算します。シングルトンとは、数独のルールを満たす値が1つに定まるマス目のことです。この評価は複数回実行します。前回の計算の結果、新たにシングルトンになるマス目があるかもしれないからです。この処理では、カーソルは使用しません。代わりに、シングルトンに行き当たるまで集計ステートメントを実行します。これにより、ステートメントの数を最小限に抑えることができます。この手法は、ヒント1の具体例です。
  2.  
  1. シングルトンがなくなったら、次に、残りのマス目を、取り得る複数の数字で埋めます。これも単一の処理として行います(ヒント1の具体例です)。
  2.  
  1. 次に、一時テーブルを作成し、取り得るマス目の行に対応する値を格納します。このとき、複雑な問題の場合にはレコード数を予期できないため、一時テーブルを使うのが最適です。多くの場合、テーブル変数を使用して解を求める方が高速だということは覚えておくとよいでしょう。現実には、そういう状況の場合、2つのストアドプロシージャを別個に用意することが必要になる場合があります。小さなボリューム用に最適化されたストアドプロシージャと、大きなボリューム用のストアドプロシージャです。集計の処理過程で中間テーブルを作成するのは、ヒント2の具体例です。このテーブルでは、きわめて単純な集計条件を使用して、たくさんの有効でない組み合わせを除外しています。その条件とは、「各行のマス目の合計値が45である」というものです。この条件は、各行の数字がそれぞれ一意でなくてはならないという条件に比べれば十分に単純なため、集計ステートメントの処理速度の足を引っ張ることはなく、しかも有効でない組み合わせの大半を単一の処理手順で除外できるため、強力さも十分です。
  2.  
  1. 手順2と同じ考え方で、マス目の列に対応する一時テーブルを作成し、中身を格納します。この手法は、ヒント2の具体例です。つまり、理屈の上では、有効な行に対応するテーブル1つだけでも事足りるのですが、後でそのテーブル自身に対して結合を行うときに、内部的に結合結果をフィルタリングする前の段階で、膨大な数の組み合わせが生成される可能性があり、パフォーマンスに支障が生じるおそれがあるのです。この手順と次の手順で、結合用の余分なテーブルを作成することによって、結合処理の過程で生成される中間的な組み合わせが多くなりすぎる事態を回避できます。
  2.  
  1. 手順2および3と同じ考え方で、マス目のブロックに対応する一時テーブルを作成し、中身を格納します。
  2.  
  1. 手順2~4で作成した3つの一時テーブルから、数独のルールを満たしていないレコードを削除します。これらの一時テーブルに格納されているレコードは、挿入の段階で集計条件を使用した、あらかじめ抽出済みのものなので、対象となるデータ数が絞られており、厳密な条件を指定して余分な行を削除する処理は短時間で済みます。また、それぞれの違反ごとにレコードを別個に削除する方が、OR句を使用するより高速です(各違反は、いずれか2つの列に同じ値が出てくる行という形で表されます)。ここでは、動的SQLを使用して、すべての削除ステートメントを1つのループに取りまとめることで、スペースを節約しています。ここでは、各ステートメントが単純で、複雑な実行プランが必要ないため、動的SQLを使用しても、パフォーマンスにはさほど影響しません。しかし、ステートメントが複雑だとしたら、動的SQLは避けるのが無難かもしれません。この手順はヒント3の具体例です。ただし、既に述べたように、一時テーブルの場合には、これはさほど重要ではありません。永続的なデータベーステーブルの場合にははるかに重要です。
  2.  
  1. 手順5を終えた時点で、3つの一時テーブルにはいずれも、数独のルールを満たす有効な要素(行、列、およびブロック)のみが格納されています。従って、これらをそのまま結合するだけで、正解が得られるはずです(パズルによっては正解が複数あることもあるという点に留意してください)。結合するテーブルが小さいか、またはインデックスが設定されている場合、処理の過程で多数の行が取得されない限りは、結合処理は常に高速に行われます。データベースエンジンでは通常、結合の最適化は適切に行われます。ただし、結合の順序を適切に指定しておくと、エンジンの処理が向上する場合があります。そこでこの手順では、3つのテーブルをパレット順序で結合しています。行、列、行、列……の順で結合し、途中にブロックが入るという形です。こうすることで、各結合で得られる仮想的な行の数が極力少なくなるようにしています。結合の結果は「TEMP_GS_RESULT」テーブルに挿入します。これは前述の通り、解答を格納するテーブルです。

 正解が1つのみのパズルの場合は、「FinalSelect.sql」スクリプトで「TEMP_GS_RESULT」テーブルを選択し、解答を表形式で出力できます。ここで示した解法プログラムは、まずまず高速です。図1の「AlEscargot」パズルを2.4GHzのCPUと1GBのRAMを搭載したマシンで解いたところ、5分20秒で解答が導かれました。解答をテキスト形式で出力すると、次のようになります。

   1    6    2    8    5    7    4    9    3

   5    3    4    1    2    9    6    7    8

   7    8    9    6    4    3    5    2    1

   4    7    5    3    1    2    9    8    6

   9    1    3    5    8    6    7    4    2

   6    2    8    7    9    4    1    3    5

   3    5    6    4    7    8    2    1    9

   2    4    1    9    3    5    8    6    7

   8    9    7    2    6    1    3    5    4

まとめ

 ここで示した解法プログラムは、データベースを基盤として適切に設計されたもので、効率という面の他にも、次のような特長があります。

  • パズルには正解が1つしかないということを前提としていません。複数の正解がある場合は、考えられるすべての正解を求めます。
  • 非常にすっきりした構造で、ミスの余地が少なくなります。

 構造がすっきりしているおかげで、拡張の方向性も明確に判断できます。例えば、処理手順と結合はどれもきわめて明快なので、動的SQLを使用して解法プログラムを書き直し、もっと大きなサイズに対応できるように拡張することも非常に簡単です。今回と同様にすっきりした構造のストアドプロシージャと動的SQLを使用して、N^2×N^2サイズのパズルを解けるように解法プログラムを拡張することも非常に簡単です。そうして得られる解法プログラムも、パフォーマンスは確実に優れています。

 ただし、Nが大きな値の場合には、最後の結果を格納するテーブルで、各レコードが解答全体ではなくマス目を表すように設計し直すことが必要です。そうしないと、列番号と行の長さに関するSQL Serverの制限を簡単に超えてしまうおそれがあります。とは言え、これはかなり単純な拡張であり、かなめとなるアルゴリズムの処理効率には影響は生じません。

 このように、元の解法プログラムも、拡張バージョンの解法プログラムも、同様のスケーラビリティを備えています。その点が、他に考えられる解法プログラムとの明確な違いです。



  • LINEで送る
  • このエントリーをはてなブックマークに追加

バックナンバー

連載:japan.internet.com翻訳記事

もっと読む

著者プロフィール

  • japan.internet.com(ジャパンインターネットコム)

    japan.internet.com は、1999年9月にオープンした、日本初のネットビジネス専門ニュースサイト。月間2億以上のページビューを誇る米国 Jupitermedia Corporation (Nasdaq: JUPM) のニュースサイト internet.com や EarthWeb.c...

  • Gene Pinski(Gene Pinski)

    Pearson School Systemsで開発リーダーを勤めており、Chancery SMS(カナダのブリティッシュコロンビア州バーナビー)のいくつかの開発分野を担当している。ビジネスアプリケーションやWebアプリケーションの開発のほか、ゲームの開発にも関心を寄せている。Webサイトはこちら。...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5