1. はじめに
Advent Calendar 3日目！
久しぶりに本を読んでみようかなと思い、本屋でSoftware Designを買った。
Software Design 10月号に、「アルゴリズム力～ダイクストラ法を学ぶ」という記事があり、重みづけされたネットワークにおいて、Dijkstra's algorithm（ダイクストラ法）を用いて最短経路を求める方法が説明されていた。
「これ、再起呼び出しで書けないだろうか？」と思い、実際にコードを書き始めたのが本記事のきっかけである。
しばらくdijkstra法で書いたものと再帰で書いたものを見比べていた。すると再起で書いたコードがドメイン駆動デザインで設計されたコードに見えてきた。そこで、そもそもDDDはどんなものなのか、DDDでないものはどんなものなのかを記事にまとめてみようと思い立った。
2. 前提知識
コードを示す前に、オブジェクト指向に触れておく。
オブジェクト指向なんて説明されるまでもないという方は3章に直接行ってほしい。
2-1. オブジェクト指向って何？
私なりにまとめてみる。
- オブジェクト指向分析（OOA）
- オブジェクト指向設計（OOD）
- オブジェクト指向プログラミング（OOP）
がある。それぞれ「オブジェクト指向で～しようと」いう話だが、分析レイヤーの人が考えるオブジェクト指向と、設計レイヤーの人が考えるオブジェクト指向と、プログラマが考えるオブジェクト指向はそれぞれ全く異なるので分けて考えよう。
2-2. オブジェクト指向分析って何？
ドメイン（スコープ）を定義し、ドメインオブジェクトを見つけてドメインモデルを作る事だ。
「オブジェクト指向は、『犬は動物を継承しています。猫は動物を継承しています』というような現実世界の描写だ」というような説明は、OOAの説明だ。
2-3. オブジェクト指向設計って何？
静的なドメインモデル（OOA成果物）をもとに、業務要件を満足するようアーキテクティングする事だ。（動的な要素を付与する）
「オブジェクト指向は、責任(Design by Contract)をベースとした自律分散協調モデルだ」というような説明は、OODの説明だ。
2-4. オブジェクト指向プログラミングって何？
Javaのようなオブジェクト指向言語の言語仕様を効果的に使ってコードを書く事だ。
「オブジェクト指向とは、継承・カプセル化・多態性のことだ」というような説明は、OOPの説明だ。
2-5. 結論は？
「ドメイン駆動デザイン」はOODの話だ。ドメイン駆動はOOAの事だ。
DDDはプログラミングのテクニックではない。OODでドメインオブジェクトに責務を割り振る事によって発生するものだということを最初に触れておきたい。
3. 実装の比較
以下最短経路探索の実装。
■ dijkstra法の例
dijkstra.py
import heapq
class Node:
def __init__(self, name):
self.name = name
self.links = {}
def __gt__(self, other):
return self.name > other.name
def link(a, b, dist):
a.links[b] = dist
b.links[a] = dist
def dijkstra(start):
fixed = {}
nearest = [(0, start, start)] # dist, node, prev
heapq.heapify(nearest)
while nearest:
dist, node, prev = heapq.heappop(nearest)
if node not in fixed:
fixed[node] = (dist, prev)
for nb, d in node.links.items():
if nb not in fixed:
heapq.heappush(nearest, (d + dist, nb, node))
return fixed
dijkstra_test.py
from unittest import TestCase
from .dijkstra import Node, link, dijkstra
class NodeTest(TestCase):
def testDijkstra(self):
n0 = Node("N0")
n1 = Node("N1")
n2 = Node("N2")
n3 = Node("N3")
n4 = Node("N4")
n5 = Node("N5")
n6 = Node("N6")
n7 = Node("N7")
n8 = Node("N8")
link(n0, n1, 3)
link(n0, n2, 8)
link(n1, n2, 4)
link(n1, n3, 2)
link(n1, n4, 9)
link(n2, n3, 1)
link(n2, n4, 3)
link(n3, n4, 3)
link(n3, n5, 7)
link(n3, n6, 9)
link(n4, n6, 5)
link(n4, n7, 19)
link(n5, n6, 5)
link(n5, n8, 12)
link(n6, n7, 14)
link(n6, n8, 10)
link(n7, n8, 3)
# 訪問開始！
dijkstra(n0)
# 結果
for n in all_nodes:
print(n)
dijkstra法に関する説明は、ソフトウェアデザインの本を読んでもらうのが一番良いと思う。
■ 再起呼び出しの例
おそらく総当たり法に近い。
model.py
class Node:
def __init__(self, name):
self.name = name
self._links = {}
self._prev = None
self._dist = 100000 # infinit
def link(self, node, dist):
self._links[node] = dist
def walk_to(self, prev, dist):
if self._dist > dist:
self._prev = prev
self._dist = dist
for nb, d in self._links.items():
if nb is not prev:
nb.walk_to(self, dist + d)
def __repr__(self):
return f'{self.name}: {self._dist} prev={self._prev.name}'
def link(a, b, dist):
a.link(b, dist)
b.link(a, dist)
model_test.py
from unittest import TestCase
from .model import Node, link
class NodeTest(TestCase):
def testWalk(self):
n0 = Node("N0")
n1 = Node("N1")
n2 = Node("N2")
n3 = Node("N3")
n4 = Node("N4")
n5 = Node("N5")
n6 = Node("N6")
n7 = Node("N7")
n8 = Node("N8")
link(n0, n1, 3)
link(n0, n2, 8)
link(n1, n2, 4)
link(n1, n3, 2)
link(n1, n4, 9)
link(n2, n3, 1)
link(n2, n4, 3)
link(n3, n4, 3)
link(n3, n5, 7)
link(n3, n6, 9)
link(n4, n6, 5)
link(n4, n7, 19)
link(n5, n6, 5)
link(n5, n8, 12)
link(n6, n7, 14)
link(n6, n8, 10)
link(n7, n8, 3)
# 訪問開始！
n0.walk_to(n0, 0)
# 結果
for n in (n0, n1, n2, n3, n4, n5, n6, n7, n8):
print(n)
result
N0: 0 prev=N0
N1: 3 prev=N0
N2: 6 prev=N3
N3: 5 prev=N1
N4: 8 prev=N3
N5: 12 prev=N3
N6: 13 prev=N4
N7: 26 prev=N8
N8: 23 prev=N6
Process finished with exit code 0
こちらは少し説明しておく。
Nodeは頂点を表すクラス。
Nodeは自分の隣接Nodeの一覧(links)を{ 隣接Node: distance } 形式で持っている。
Node間をリンクに沿って訪問した時、既に訪問済みであれば過去のルートにおける距離が記録されている。その記録された距離より短い距離で訪問できた場合、その距離を上書きする。
- 訪問に関するコードは全てノードオブジェクト自身が持っていて、そのコードは自分自身以外関知しない。
- 再起呼び出しである。
あたりが特徴。
コードの比較
性能的にはdijkstra法のほうがずっと速い事は間違いない。特に万に達するようなノードが構成するのネットワークに対して再起呼び出しで解くことは不可能ではないだろうか。
末尾再起最適化が可能な言語系なら解けるのか？おそらくもっと早い段階でstack overflowになるだろう。
djkstra法の計算量は $O(n^2)$ であり、総当たり法の計算量は $O(n!)$ か、そのくらいの差がありそう。
dijkstraのコードは解法が確立しているので、比較的見やすいコードではあるものの、おそらくアルゴリズムを知らない人間がみてすぐ何をしているのかを理解するのは困難ではないだろうか。
再起のコードは、実際に訪問している描像をそのままコードにしているだけなので、わりと分かりやすいのではないかと思う。
4. ドメイン駆動デザイン(DDD)とトランザクションスクリプト(TS)
再帰の例がDDD的だなあと感じたわけだが、そもそもDDDとTSがそれぞれどのようなものか書いておく。
4-1. トランザクションスクリプト(TS)とは？
昔からある構造化設計を現代的な言い方をしたもの？。データと処理を完全に分離する。データはstructである。
処理は、Serviceから全structを操作する。
- 全ての情報を知っている立場から解を得られるので、dijkstra法のような最適化が可能。
- 最適化すれば早いが、スパゲッティになりやすい。
- ネストが深くなりがち。
と思っている。
dijkstra法の例では、Nodeはデータにすぎず、ロジックはすべて外側のdijkstraという関数が持っている。
4-2. ドメイン駆動デザインとは？
OOAから導かれたドメインモデルに責務を付与する。各ドメインオブジェクトは責務を全うするために必要なメソッドを持つことになる。
ひとつのドメインオブジェクトが知っている情報は限られるため、複数のドメインオブジェクトが連携して一つの解を導くようなコードになる。
- コードはシンプルなる。
- ネストは深くならないが、コードが断片化する。
- 再起呼び出しになりがち。
再起呼び出しの例ではNodeがドメインオブジェクトであり、Node自身のみがロジックを持っている。そしてNodeが知っている情報は、自分自身の近隣Nodeだけである。
5. 最後に
ドメイン駆動デザインがどんなものなのかもっと詳細に知りたいという方は、「オブジェクト指向分析設計」を調べてください。
DDD自体はオブジェクト指向が流行っていた昔からあった概念ですが、最近再び目にするようになった気がします。とはいえ、オブジェクト指向という考え方は聞かれなくなって久しく、DDDの立ち位置が分かりにくくなっているなあと感じています。
ドメイン駆動デザインで書かれたコードは読みやすいと私は思っています。なぜなら、それはドメインモデルの自然な拡張だからです。
とはいえ現実問題として日本の現場でDDDをちゃんとやる事はとても障壁が大きいとも感じています。皆structに処理を持たせることを嫌がるのですよね。継承も嫌がられますし。
それでもDDDをやるなら、分析設計段階できっちりドメインモデルに責務を割り振ってからやることをおススメいたします。
なお、上のコードは本の例以外で動作確認試していませんので、バグがない事を保障はしません。
あくまで「再起呼び出しで書けるのではないか？」という疑問から実際に書いてみたお試し実装だと承知の上で読んでください。
もし異論反論あれば、コメントで頂ければとても嬉しいです！