プログラマーのメモ書き

伊勢在住のプログラマーが気になることを気ままにメモったブログです

2-3木を実装した

ボチボチこちらの『データ構造とアルゴリズム』を読んでるところです。

時間を見つけては興味のある内容を実装したりして遊んでます。で、今回は、平面走査法を実装してみたいなと思い立ち、まずはここで紹介されていた探索木の一つである 2-3木 を実装してみました。

個人的には、実装していくだけでも十分楽しいんですが、それだけだと、アルゴリズムの本見たり、ネットを漁れば(最近だと ChatGPT に聞けば)いいだけの話なので、ここではそのあたりは深く触れず、実装時にやってみた Python の単体テストとか、木の可視化などについてを主にメモしておきます。

なお、実装時の環境は以下の通りでした。

  • WIndows 11 22H2 上の WSL2, Ubuntu 22.04.2
  • Python 3.11.4

こちらの記事のように Windows 上の VSCode から WSL にリモート接続して開発してます。

実装について

とはいえ、実装時に気になったところもあったので、それらについて簡単にメモっときます。

前述の本を参考に実装していったのですが、実際にコードを書いてみると困った点としては、

  • 2-3 木 の定義として、葉以外のノード(節点)は 2 つまたは 3 つの子要素を持っている
  • しかし、木を作成する際に、一つ目の葉を追加したときは、根の要素に対して、追加前は子要素が 0 個、追加後が 1 個
  • 同様に、木を作成する際に、二つ目の葉を追加したときは、根の要素に対して、追加前は子要素が 1 個、追加後が 2 個

となるため、この部分だけを例外的に扱う必要がありました。まあ、考えてみれば葉が 1 個という状態もありえるんだから、考慮する必要があるのは当たり前ですよね。

あと、困ったというわけではないのですが、紹介されていたアルゴリズムでは、ある中間のノードは、

  • 左側のサブツリー内のキーの最大値
  • 中央のサブツリー内のキーの最大値

を持つとしていたのですが、値を直接持つと、先々平面走査法で扱う時にちょっと困りそうな印象があります(キーとして交点の座標を持つ必要があり、それが変化していくため)。なので、この部分をキーの最大値を直接持つのではなく、キーの最大値を持つノードへの参照を持つように変えてみました。

実装に興味がある方は、 GitHub にコードをアップしているのでそちらを参考にしてください。

単体テスト

久しぶりに Python でまとまったコードを書いてみたので、単体テストも作ってみました。まあ、厳密にはメソッド単位でのテストになっていないので単体テストか?という疑問がつく内容ですが、 2-3 木のクラスをテストする、という意味でここでは単体テストと呼んでます。

Python の単体テストは、下記などの記事を参考にして作ってみました。 unittest という標準モジュールを使えば、簡単にテストが作れるとのことです。

プロジェクトのフォルダの下に test というフォルダを作り、その中に test を定義するファイルを作成しています。

テストの作成

まず、今回作った 2-3 木のモジュール (TwoThreeTree.py) を使う際には、葉の要素がキーとなるオブジェクトを保持する形をとる際に、葉のクラスの派生クラスを作る形を想定しているため、そのための定義を test/TestClasses.py にまとめています。

from dataclasses import dataclass
import math
from TwoThreeTree import Leaf, Node

# テスト用の Node 要素
@dataclass
class NodeForTest:
    id: str     # id
    key: float  # キー

class MyLeaf(Leaf[NodeForTest]):

    def __init__(self, val: NodeForTest, parent: Node[NodeForTest] | None):
        super().__init__(val, parent, get_key, comp_key)

def get_key(v: NodeForTest) -> float:
    return v.key
def comp_key(v1: NodeForTest, v2: NodeForTest) -> int:
    if math.isclose(v1.key, v2.key):
        return 0
    if v1.key < v2.key:
        return -1
    else:
        return 1    
def myleaf_ctor(v: NodeForTest, parent: Node[NodeForTest]):
    return MyLeaf(v, parent)

で、このクラスを使う形で、テストを書いていきます。

テストは、 test_*.py のような名前のファイルに書く必要があります。たとえば、一般的な 2-3 木の操作に関するテストを test_TwoThreeTest_general.py というファイル名で作成します。

from dataclasses import dataclass
import unittest
from TwoThreeTree import Leaf, Node, TwoThreeTree
from test.TestClasses import MyLeaf, NodeForTest, comp_key, get_key, myleaf_ctor

class TestTwoThreeTree(unittest.TestCase):
    """典型的な 2-3 木に関するテスト
    """

    @classmethod
    def setUpClass(cls):
        print("2-3 tree test setup")

        # 2-3木を作成してテスト
        cls.tht: TwoThreeTree = TwoThreeTree[MyLeaf, NodeForTest](get_key, comp_key, myleaf_ctor)

    @classmethod
    def tearDownClass(cls):
        pass

    def test_create_tree_1(self):
        TestTwoThreeTree.tht.insert(NodeForTest("01", 2.0))

        self.assertEqual(2, TestTwoThreeTree.tht.size)
        self.assertEqual(1, TestTwoThreeTree.tht.leafSize)
        self.assertEqual(2, TestTwoThreeTree.tht.height)
(後略)

こんな感じです。

まず、 unittest.TestCase を継承したクラスを作ります。この中の、 test_* のような名前のメソッド一つ一つがテストになります。テストはメソッド名のアルファベット順に実行されます。

テスト前に実行したい処理およびテスト後に実行したい処理は

  • setup / tesrDown
  • setUpClass / tearDownClass

に記述します。

前者の 2 つのメソッドは、テストメソッドが呼ばれる前後に毎回呼ばれます。一方、後者のメソッドは、クラスメソッドで、上記のクラス全体で最初と最後の一度だけ呼ばれる形になります。

上記の例だと、何もない 2-3 木に順番に葉の追加を行って、その結果を確認したいので、クラスメソッドを利用しています。

テストメソッド内で、対象となる処理を行ったあと、確認したい内容を assertEqual というメソッドで比較していきます。上記の例だと、

  • 2-3 木の総ノード数(size)
  • 葉の数(leafSize)
  • 木の高さ(hheight)

を確認しています。テストによっては確認する内容は変わると思いますが、 assertxxxx というメソッドがいろいろと用意されているので、それらを使ってテストを組み立て行きます。

結構簡単ですね。

テストの実行

テストを実行するには、コマンドラインから実行します。

(.venv) mor@DESKTOP-DE7IL4F:~/tmp$ python -m unittest test/test_TwoThreeTree_general.py 
2-3 tree test setup
................
----------------------------------------------------------------------
Ran 16 tests in 0.001s

OK
(.venv) mor@DESKTOP-DE7IL4F:~/tmp$ 

問題がなければ、こんな感じに OK と表示されます。

ただ、これだと、テスト数が増えてくるといちいちコマンドラインで実行するのが大変になってきます。同じことを VSCode からやるには、

VSCodeとpytestでPythonコードをテスト&デバッグする|CO-WRITE

などを参考にして、構成を行ってやります(構成方法はリンク先の記事を参考にしてください)。なお、参考までに、設定後の .settings.json は

{
    "python.testing.unittestArgs": [
        "-v",
        "-s",
        "./test",
        "-p",
        "test_*.py"
    ],
    "python.testing.pytestEnabled": false,
    "python.testing.unittestEnabled": true
}

となってました。

問題なく構成ができたのち、 VSCode のフラスコのアイコンを選択すると、

のようにテストが一覧で表示されます。

で、テストにカーソルを合わせると

のように『テストの実行』アイコンが表示されるので、これをクリックするとテストが実行できます。

もし、テスト失敗があると、上記のように赤で×印で教えてくれます。これは結構便利ですね。

木の可視化

単体テストを書いてテストするのは、これはこれで大事なんですが、木(グラフなど)を扱ってると、どうも本当にこれでいいのかピンときません。もちろん、アルゴリズムとして処理の途中の動作も確認して追いかけてはいるのですが、なかなか追いかけるのも大変です。

ということで、せっかく Python で実装していることもあるので、木を可視化する方法として簡単にできるものがないか調べてみると、 Python から Graphviz を利用するための graphviz パッケージがあることがわかりました。ということで、 graphviz パッケージを利用して、木の状態を Graphviz 経由で出力するメソッドを追加してみます。

こうすることで、テスト時の木の変化を視覚的に追いかけることができるようになりますね。

具体的に、 Python から Graphviz を使うには

などを参考にして、 graphviz パッケージのインストール等を行いました。なお、 graphviz パッケージだけではなく、 Graphviz 本体そのものがインストールされている必要があるのでご注意ください(手元の WSL 環境では こちらの記事でインストール済みでした)。

なお、試した際のバージョンは以下の通りでした。

  • graphviz パッケージ 0.20.1
  • Graphviz 2.42.2-6

実際に書いた処理は、 GitHub のコード(TwoThreeTree.py の TwoThreeTree クラスの visualizeGraph メソッド)を参考にしてください。

以下に、上記の処理を作成する際に参考にした記事を載せておきます。

なお、 VSCode の import で graphviz が不明となってエラーが出る場合は

VSCodeで Import "***" could not be resolved Pylance(reportMissingImports) が出るときの対処法 - Qiita

で対応しました。

可視化の例

たとえば、この作成した可視化メソッドを使うと、2-3 木に順次葉を追加している様子が下記のようになっていることが視覚化できます。

最初の 根(ルート)の要素のみの状態

キー 2 の葉を追加

キー 5 の葉を追加

キー 9 の葉を追加

キー 7 の葉を追加。ちゃんと中間ノードが増えて、それぞれで葉をもってますね。木の高さも正しいです。

キー 4 の葉を追加

キー 1 の葉を追加

キー 3 の葉を追加

キー 10 の葉を追加

キー 8 の葉を追加

なお、このメソッドは verbose 引数を取ることができて、 true を指定すると親から子への参照だけでなく、子から親への参照と中間ノードが持つ最大値に関する情報も表示するようにしています(上記の出力例は verbose ありになってます)。

今後

探索木として、赤黒木も実装してみたいなと思ってるんですが、これもこれで手順がややこしそうで、ちょっと二の足踏んでます。 まあ、とりあえず動く 2-3 木の実装ができたので、まずは平面走査法をやってみるかな?

更新

  • 2023/7/14 可視化についての書きっぷりを若干修正(Graphviz 本体と graphviz パッケージを分けて記述するなど)