型の複雑度

5 min読了の目安(約4800字TECH技術記事

はじめに

以下のようなモデリングのどちらが良いか?ということについて考えます。(サンプルコードはScalaです。)

// 1. 神クラスを作るモデリング
case class 商品(
    商品ID: String,
    名称: String,
    価格: Int,
    商品種別: 商品種別,
    内容量: Option[Int],
    消費期限: Option[Date],
    著者名: Option[String],
    ISBN: Option[String]
)

// 2. 種類ごとに分けるモデリング
sealed trait 商品 {
    商品ID: String,
    名称: String,
    価格: Int
}
case class 食品(商品ID: String, 名称: String, 価格: Int, 内容量: Int, 消費期限: Date) extends 商品
case class 書籍(商品ID: String, 名称: String, 価格: Int, 著者名: String, ISBN: String) extends 商品

必ずしも正解はないと思いますが、どちらが「わかりやすいか?」という問いを出発点とした場合、以下のように意見が分かれることがあるかと思います。

神クラスの方がわかりやすい

  • 「商品」であることがすぐわかる
    • プログラムの主要な関心事が価格を使った計算なら、ほかの事柄は付属的な情報に過ぎない

分けたほうがわかりやすい

  • 内容量、消費期限、といった情報がnullなのかどうか一見してわからない(= 必要な属性が一見してわかる)

ここでどちらのモデリングを採用すべきか意思決定を行う場合、「どちらがわかりやすいか?」 を基準にして「商品であることがすぐわかる」という価値と「必要な属性が一見してわかる」という価値を比較すると、どちらの価値が高いかはコンテキストに依存し、一般的には比較できないと思います。

このため、より一般的な比較を行いたい場合は、以下のような客観的に計測できるメトリクスを使用するとよいでしょう。

  • 文字数
  • 行数
  • 循環的複雑度
  • 凝集度
  • 結合度

本稿では、これらに加えて 「型の複雑度」 というメトリクスを紹介します。

代数的型システムにおける複雑度

代数的型システム

単純型、直積型、直和型の集合のことを 代数的データ型(Algebraic Data Type) といい、全てのデータ型がそれより小さい代数的データ型から構成される世界のことを代数的型システムといいます。

  • 単純型は型の選択肢が1つしかないような型のことです。
  • 直積型(AND型, Product) は異なる複数の型の値を1つの型に集約した型のことです。
  • 直和型(OR型, Coproduct) はある型が複数のいずれかの型であることを示す型のことです。

本稿のサンプルコード(Scala)では、直積型を case class、直和型を sealed クラスにエンコードして考えます。

型の複雑度

各代数的データ型の型の複雑度は、その型が取りうる値の数によって表現することができます。

単純型の場合

  • Unit の場合は1
  • Boolean の場合は2
  • Int の場合は 4,294,967,295
  • String の場合は 無限

直積型の場合

  • 直積型の場合、それぞれの値がとりうる値の数を掛ける
    • (Boolean, Boolean) の場合は 4 (2 * 2)
    • (Boolean, Boolean, Boolean) の場合は8 (2 * 2 * 2)

直和型の場合

  • 直和型の場合、それぞれの値がとりうる値の数を足す
    • (Boolean | Boolean | Boolean) の場合は 6 (2 + 2 + 2)
      Boolean の値を一つだけ取りうる型ではなく、以下のようなモデルを想定してください。
sealed trait Foo
case class Something(value: Boolean) extends Foo
case class Anything(value: Boolean) extends Foo
case class Thing(value: Boolean) extends Foo

全域関数の複雑度

全域関数(Total Function) は全ての入力に対して出力が定義されている関数のことです。(ここでは、例外を送出しない関数と考えます。)
全域関数は全ての入出力のパターンが型で表現されています。全域関数の複雑度はその関数のシグネチャを満たしうる入力と出力の組み合わせの数(= 出力の複雑度と入力の複雑度の累乗)になります。

  • Unit => Boolean であれば 2(2^1)
No. input = Unit
1 output = true
2 output = false
  • Boolean => Option[Boolean] であれば 9(3^2)
No. input = true input = false
1 output = Some(true) output = Some(true)
2 output = Some(false) output = Some(false)
3 output = Some(true) output = Some(false)
4 output = Some(false) output = Some(true)
5 output = Some(true) output = None
6 output = Some(false) output = None
7 output = None output = Some(true)
8 output = None output = Some(false)
9 output = None output = None
  • Option[Boolean] => Option[Boolean] であれば 27 (3^3)

型の複雑度の比較

冒頭に出てきた神クラスを作るモデリングと種類ごとに分けるモデリングの複雑度を比較してみます。
ただし、Stringといった型はそのままだと複雑度が無限になってしまいます。比較のため、一旦、これ等の型はより抽象的な型に置き換え、それぞれの型の複雑度を定義します。以下のコードでは、ID, Name, Price, Amount, Date という型を設け、それぞれの複雑度を a, b, c, d, e としています。商品種別 は食品と書籍しかないので、複雑度は2です。

// 1. 神クラスを作るモデリング
case class 商品(
    商品ID: ID,             -- a
    名称: Name,             -- b
    価格: Price,            -- c
    商品種別: 商品種別,      -- 2
    内容量: Option[Amount], -- d
    消費期限: Option[Date], -- e
    著者名: Option[Name],   -- b
    ISBN: Option[Name]     -- b
)

// 2. 種類ごとに分けるモデリング
sealed trait 商品 {
    商品ID: ID,     -- a
    名称: Name,     -- b
    価格: Price     -- c
}
case class 食品(
    商品ID: ID,     -- a
    名称: Name,     -- b
    価格: Price,    -- c
    内容量: Amount, -- d
    消費期限: Date  -- e
) extends 商品
case class 書籍(
    商品ID: ID,     -- a
    名称: Name,     -- b
    価格: Price,    -- c
    著者名: Name,   -- b
    ISBN: Name      -- b
) extends 商品

これを使って各モデリングにおける複雑度を計算すると、

  • 神クラスを作るモデリングの複雑度
    • a * b * c * 2 * (d + 1) * (e + 1) * (b + 1) * (b + 1)
    • 一番大きな項の複雑度は `2 * a * (b ^ 3) * c * d * e
  • 種類ごとに分けるモデリングの複雑度
    • (a * b * c) + (a * b * c * d * e) + (a * (b ^ 3) * c)
    • 一番大きな項の複雑度は a * b * c * d * ea * (b ^ 3) * c のどちらか

簡単のため、一番大きな項の複雑度だけを比較すると、神クラスの方が(b ^ 2) * 2 もしくは d * e * 2 ほど複雑、ということができます。(Nameなどは非常に大きな複雑度になるため、全ての項を考慮しても神クラスの方が複雑、ということは言えるかと思います。)

まとめ

  • わかりやすさ、といった基準ではモデルの比較をしづらいことがあります。
  • 文字数や循環的複雑度といった数値化できる尺度を用いると、一般的な形でモデルを比較することができます。
  • 「型の複雑度」という尺度があり、型の複雑度はその型が取りうる値の数のことです。
  • 「型の複雑度」を用いて「神クラスを作るモデリング」と「種類ごとに分けるモデリング」の比較を行い、「種類ごとに分けるモデリング」の方が型の複雑度が低いということを示すことができました。

出典・参考文献