2019-06-16

読書記録 C#実践開発手法第2部-第7章

知らぬ間に1月過ぎておりました。
しかしひとまずは継続しているのでセーフです。

さて本日は、第７章のリスコフの置換原則の説明になります。
リスコフの置換原則は、クラスにおけるコントラクト(契約)の話に深く根付いており
非常に重要な原則だと思いますが、一見した時に全容がつかみにくい印象があります。

定義と伝えたいこと

定義としては
「SがTの派生形であるとすれば、T型のオブジェクトをS型のオブジェクトと置き換えたとしても、プログラムは動作し続けるはずである。」
というものです。
ここでは、プログラムが"動作する"ことが重要であって"期待する結果と一致する"ことは求めていません。
具体的には、コンパイルがエラーなく終了し、動作途中でアプリケーションの強制終了が発生しないようにすることが重要になります。

この定義が伝えたいことは、クラスのコントラクトのルールとして

事前条件を派生型で強化することはできない

事後条件は派生型で緩和することはできない

基底型の不変条件は派生型でも維持されなければならない

これらのルールは、引数と戻り値の型の変性に関係しており、派生型は

事前条件を強めてはいけない
事後条件を弱めてはいけない
基底型が知らない例外を投げてはいけない

というものになります。つまり、派生型は基底型が要求しない引数を持たず、出力しない戻り値を出力してはいけないということになります。
ただし、基底型の引数や戻り値の型が派生型のそれを包含しているのは問題ありません。

ここまでは入出力に関するものでしたが、内部で保持している値やその型の不変条件も維持することになります。

少し短いですが今回はこれまでとしておきます。
次回はインタフェース依存に関する内容になります。
更新予定日は7/6としておきます。

2019-04-28

読書記録 C#実践開発手法第2部-第6章

大幅に遅れましたが、個人用なので問題なしです。

本日は第2部第６章の開放と閉鎖の法則の説明になります。

定義

開放と閉鎖の法則(OCP)には2パターンの定義があるそうです。
一つはMeyer(契約による設計を提唱した方です)によるもので

ソフトウェアエンティティは拡張に対して開いていて、変更に対して閉じていなければならない。

というものになります。この「拡張に対して開いていて」と「変更に対して閉じている」の両方を詳細しているのが
次のMartin(アジャイルマニフェストの提唱者の一人)の定義になります。
Martinの定義によると、
拡張に対して開いているは、モジュールの振る舞いを拡張できることを意味しており
変更に対して閉じているは、モジュールの振る舞いを拡張しても、モジュールのソースや
バイナリに変更が生じないこと。
であるそうです。

ただし2つの例外があるそうで、バグの修正と、クライアント側が認識できない変更は許されるそうです。

方法

OCPの定義の次は、どのようにしてOCPを実現するかの説明に移ります。

変更に対して閉じているようにするためには、やはりクラスはインタフェースで依存させておいて、ある程度の変更に耐えうるようにするのが良いようです。
クラス間を疎結合に保つことで、変更に対して閉じている状態を維持できます。

拡張に対して開いているようにするためには、拡張ポイントを各クラスに設ける必要があるそうです。
この拡張ポイントを実装する手段として、仮想メソッドや抽象メソッド、インタフェースの継承があるそうです。
ここでは3つの方法を挙げましたが、この本で推奨しているのはインタフェースの継承でした。
仮想メソッドや抽象メソッドでは、どうしてもサブクラスが元のクラスの実装に依存することになり、元のクラスの変更が難しくなります。
可能な限り継承よりも合成を優先して、継承階層は浅く保つのが良いようです。

適用

OCPを実装で表現するためには、インタフェースの合成や継承を活用しつつ、場合によっては実装の継承などを利用することを説明しました。
次は、どの程度これを実際のソフトウェアに実現するのかの説明になります。
これらの拡張ポイントをすべてのクラスに適用することも可能ではあると思いますが、現実的ではありません。

OCPを適用する場所を決定するためには、あらかじめ将来変更しうるクラスを予測することが重要になります。
この予測に活用できるのが、アジャイル開発におけるユーザストーリの選択です。
ユーザストーリの選択時に、将来の形をイメージする(もしくはチーム内で予測を合わせておく)ことで予測されるバリエーションの情報が得られます。

これで拡張ポイントを決定し、実装を進めていきます。
OCPの実現のためには、インタフェースへの依存が重要になりますので、インタフェースは安定していることが最重要になります。

このようにして適切にOCPを適用してソフトウェアを柔軟に開発していきます。

おわりに

以上が第６章の説明になります。
読書記録に締め切りを設けることで、(今回は超過しましたが)やはり焦燥感のようなものが芽生えていつもよりも進みが早く感じます。
次回の更新は5/18を予定しています。

2019-03-24

読書記録 C#実践開発手法第2部-第5章

今回から第２部に入ってSOLID原則の説明に入ります。
第５章はSの単一責務の原則の解説になります。
一日遅れましたが誤差の範囲内です。

リファクタリングの方針としては、インタフェースを通じた抽象化とStairwayパターンによる分割で積極的にクラスを分けていくことになります。
この作業を怠って複数の処理を含んだクラスを使うと、クラスの仕様を変更するたびに、そのクラスとクラスを使うクライアントの変更が必要になり、仕様変更が難しくなります。
基本的に継承ではなく委譲を利用してクラスを分割する方針なので、使う手立てとしては

Decoratorパターンによる機能追加
Compositeパターンによる連結
Strategyパターンによる分岐処理

になります。
本書の例ではありませんでしたが、これらをそれぞれちゃんと使うときには、Factoryクラスなどを使うことでインスタンスの生成から変更可能にしておかないといけないと思います。

Decoratorパターン

あるクラスで責務の単一化をしようにも、機能分割が難しい場合があります。
例)

ロギング機能
グラフ描画機能
ファイルパース機能　etc

このあたりの機能はある処理とかなり密に依存する場合があり、単一化が難しくなりがちですが、それをDecoratorで分割します。

public class Decorator : IComponent
{
    public Decorator(IComponent component)
    {
        this.Decorated = component;
    }
    
    public void Do()
    {
        //Decoratorでやりたいこと
        DoSomething();
        //被装飾インスタンスで実行する本来の処理
        Decorated.Do();
    }


    private void DoSomething()
    {
        //ロギングや可視化などの処理
    }
}
<||
このようにインタフェースで追加処理を委譲させることで変更に強くなります。

このDecoratorの応用として、述語Decorator、分岐Decoratorなどがあります。
これらの応用で条件分岐や、非同期処理を別クラスに分離することができます。

** Compositeパターン
このデザインパターンは、共通のインタフェースを持つクラスをリストなどのイテレータにまとめます。
こうすることで、複数のインスタンスを1つのインスタンスのように扱うことができます。
これについてはコード例は省略します。

** Strategyパターン
Switch文で複数の条件分岐を記述すると、新しく分岐を追加するときや、条件式の変更への対応が難しくなります。

>|cs|
public class Strategy
{
    private IDictionary<Case, IComponent> Strategies;
    public Strategy()
    {
        Strategies = new Dictionary<Case, IComponent>();
        Strategies.Add(Case.Case1, new Case1Component());
        Strategies.Add(Case.Case2, new Case2Component());
        Strategies.Add(Case.Case3, new Case3Component());
        Strategies.Add(Case.Case4, new Case4Component());
    }

    public void Do(Case caseIndex)
    {
        Strategies[caseIndex].Do();
    }
}
<||

分岐用の値を外部引数として受け取ることで、分岐の追加や条件式の変更が容易になります。
しかし、新しいクラスを追加する際にはIComponentインタフェースを持つことが必要になり、この例だとクライアント側で各条件と対応する値を知っておく必要はあります。

** まとめ
単一責務の原則では、クラスから処理をインタフェースとして抽出して、複数クラスに分散させることになります。

2019-03-02

読書記録 C#実践開発手法第１部-第4章

思いっきり更新日を間違えていました。

今回は第4章ユニットテストに関する読書記録です、と言いたいところですが、ここを読んでいてもテスト駆動開発についてよくわからなかったところがあって、それを補間するために別の本を読み始めています。

ひとまずは読んだ部分について記録していきます。

ユニットテストとテスト駆動開発

テスト駆動開発は実際のコードに先駆けてテストコードを作成して、そのテストコードを正しく実行できるような
コードを記述していく、という流れを繰り返していく開発手法です。

先にテストコードを書くことで次のような恩恵を得ることができます。

コードとテストコードの協調性が保たれやすくなる
リファクタ時に混入するバグの早期発見に役立つ
実装中のクラスをテストすることでよりよい設計が思いつく

では、最初のテストコードの例を示します。

[TestClass]
public class ATest
{
    [TestMethod]
    public void AddNum()
    {
        //テスト対象となるクラスの呼び出し
        var num = new NumClass();
        
        //テスト対象クラスの実行
        num.add(10);

       //期待する動作の記述
       Assert.AreEqual(10,num.get());
    }
}

このテストではNumClassにたいして次のことを期待しています。

引数を要求しないコンストラクタを実行できる
メンバ変数に値を持ち、初期値は0である
整数値を受け取るaddメソッドでメンバ変数を変更できる
getterを持つ

ひとまずはこの程度でとどめておき、これを実行できるようなクラスを作成します。
ここでテスト駆動開発の特徴としては、まずこのテストを失敗するようなコードを作成します。

public class NumClass
{
    public int num;

    public NumClass(){}

    public void add(int a){}

    public int get(){return num;}
}

とりあえずこんな感じのコードを書いておけば、コンパイルエラーを出すことなく作成済みのテストコードに通すことができます。

もちろんテストには失敗しますが、この失敗によって次に修正すべき点が見つかります。
この程度であれば一気に修正して良いとは思いますが、最小限の労力でこのテストを完遂しようとするならば

public class NumClass
{
    public int num;

    public NumClass(){}

    public void add(int a){}

    public int get(){return 10;}
}

このようにgetterでテストが要求する値を返すようにする事になります。

ここまでで

NumClassが引数を要求しないコンストラクタを持つ
getterを持つ

ことには自信を持つことができます。
そこで次のテストとして

[TestClass]
public class ATest
{
    [TestMethod]
    public void Add2Nums()
    {
        //テスト対象となるクラスの呼び出し
        var num = new NumClass();
        
        //テスト対象クラスの実行
        num.add(10);
        num.add(15);

       //期待する動作の記述
       Assert.AreEqual(25,num.get());
    }
}

次のテストコードを追加します。
テストコードの追加によって定数を返すgetterでは全てのテストに対処しきれなくなります。
なので、本格的にaddメソッドを実装して正しく計算が実行できるようなクラスとしていきます。

これ以上のコードは省略しますが、テスト駆動開発ではとりあえず実装してからリファクタリング、という流れになります。

先程の例であれば、少なくとも正常な整数が入力されれば計算可能であることに自信が持てますので

エラー入力への対応
他の演算の追加
メンバ変数のアクセス権の変更

などのリファクタリングを実行して、既存のテストコードを通せることを確認します。

こうすることでリファクタ時にバグが混入してもテストコードを短い間隔で実行することになるので早急なバグの発見が可能になります。

まとめ

読書記録というよりもテスト駆動開発についての説明になってしまいました。

現時点でわかっていないこととして

設計の変更について言及しているが予めどの程度設計してから開発をすすめるのか
過去のテストコードの修正はどの程度許容されているのか

等が挙げられます。

後は感想になります。

個人的に仕事でもテスト駆動開発を実践してますが、結構開発が楽しくなっているように感じます。

やはり自分の進捗が可視化されるとやる気が出てきますし、テストコードを精査することでどの程度自分のコードができているのかがわかります。
これからもテスト駆動開発についての勉強は進めていくので、何かあればまた記事を作りたいと思います。

次回の更新は3/23を予定しています。

2019-02-17

ABC118D Match Matching

ABC118 に参加しました。
結果としては3完で+32という微妙な結果に終わりました。

コンテスト終了後にD問題のMatch Matchingを解いたので、コードを載せてみます。

方針

与えられたマッチを"ちょうど"使った時の最大の数を表示する。
この"ちょうど"というところから、貪欲法でやるよりもDPでやったほうがいいという気持ちになりました。
(コンテスト本番にはDFSでやろうと思ってましたが、計算量や"ちょうど"という制約が面倒になります)

解説の資料には桁数を保存して、後から最大の数値を生成する感じになっています。
私はPython3とC++の両刀使い(どっちつかず)なので、Pythonでやってlong long int の壁を越えることができます。
そこで
$dp(i) := マッチをi本使った時の最大の数$
として、数を文字列に変換せず直接代入しました。

コードは次の通りです。

match = [2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
aa=list(map(int,input().split()))
#9以上多めにとってout of range を防ぐ
dp=[-1]*(n+10)

dp[0]=0
for i in range(n+1):
        for nums in aa:
                #この条件がないと、i本までで表現できる最大の数になる
                if dp[i] == -1 :continue
                dp[i+match[nums-1]] = max(dp[i]*10+nums,dp[i+match[nums-1]])

print(dp[n])

DPはちゃんと勉強していくつもりです。
いつかコンテスト本番でDを解いて見たいです。

2019-02-03

競プロの記録

予定していた読書記録ではありませんが、いくつか面白い問題を解いたので精進のため記録します。
全体を通して得られる教訓は「探索の基本は全探索」ということでしょうか。
解説や提出コードを含みますのでネタバレ注意になります。

ABC114 C問題 755

整数N( $1<=N<=10^9$ )より小さい整数のうち、数字の7、5、3を1度以上ずつ使った数字の個数を数える。
という問題です。
自分の考えていた内容としては

条件を満たしつつM桁の整数を作るとき、その整数が $M!*_{3(M-3)}C_{M-3}$ であるので
※実は証明してません、間違いの場合はコメントにてご指摘いただけると幸いです。
2019/02/17追記上記の式間違ってます。
あとはM+1桁の場合で全通り試そうと考えていました。
しかし、桁上がりを考えていると結構面倒で結局時間切れとなりました。

回答を見るとその方針としては、7、5、3を組み合わせた整数を作成して後から条件を満たすかどうか検査するという方法でした。
次のコードは解説コードの丸写しになりますが、かなりかっこいいと思っています。

N = int(input())
 
def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
        ret += dfs(s + c)
    return ret
 
print(dfs('0'))

これですと計算量が整数の桁数に依るため制限時間内に実行可能になります。
最初から条件を満たすものを考えるのではなく、大まかに数え上げた後に条件を満たさないものだけを切り取っていく方針です。

ARC060 D 桁和 / Digit Sum

整数N( $1<=N<=10^11$ )をb進数で表現した時、各桁を合計した値が整数Sになるかどうかを探索する問題です。
存在する場合には最小のbを出力し、存在しない場合には-1を出力します。
詳しい算出方法は問題にありますが今回は割愛します。

この問題に関しては全くいい方法が思いつきませんでした。
以下は解説を見て自分なりに理解している内容の整理になります。

ひとまず、特殊な場合を先に片付けると

$N = S$ : b=N+1
$N \lt S$ : bは存在しない

ということになります。

次にこれ以外の場合について考えると、bが $\sqrt{N}$ で場合分けできることがわかります。これは $b>\sqrt{N}$ の場合にはNが2桁のb進数で表現できるということに端をなします。Nが2桁になると何がうれしいか言うと、bが一意に求まるようになるからです。
$N=pb+q , p+q=S$
$b=(N-S)/p+1$
これでpを定めることでbが一意に定まりますし、探索範囲を絞ることができたので制限時間内に実行可能になります。

from math import floor
from math import sqrt
 
def f(bb,nn):
    if(nn<bb): return nn
    else: return f(bb,floor(nn/bb))+(nn%bb)
        
 
n=int(input())
s=int(input())
 
if n==s:
    print(n+1)
    exit()
elif n<s:
    print(-1)
    exit()
 # <sqrt(N)まで探索
for i in range(2,int(sqrt(n))+2):
    if s==f(i,n):
        print(i)
        exit()
 
#pが大きいほどbの値は小さくなるので逆順ループで最初に見つかったものが最小
for i in reversed(range(1,int(sqrt(n))+2)):
    if (n-s)%i == 0:
        tmpb=(n-s)//i+1
        if tmpb >= sqrt(n) and f(tmpb,n)==s: 
            print(tmpb)
            exit()
print(-1)

このように割り算で条件を探索するときに、境界条件になりがちな $\sqrt{N}$ は別の問題でもちょっと考えたほうがいいと思います。

まとめ

最初に示した通り「探索の基本は全探索」です。
ここから様々な工夫をもとに計算量の削減を行っていくので、これを最初に考えなかったのがWAの原因かなと反省しております。

2019-01-28

読書記録 C#実践開発手法第１部-第3章

第3章ではインタフェースにまつわる設計や依存関係について解説されています。

インタフェースと依存関係

オブジェクト指向な設計を行う際には、具体ではなく抽象に依存させるという指標があります。
これは、多態性や再利用性を高めるためであり、個人的にはオブジェクト指向で最も大切な指標だと思います。

まずはインタフェースを使用しない例を示します。

public class Motor
{
    private int speed;

    public void Start(){ ...}
    public void Stop(){...}
    public void ChangeStart(int speed){...}
}

public class Car
{

    public Car()
    {
        Motor motor = new Motor();
        motor.Start();
    }
}

一部省略していますが、CarクラスからMotorクラスを生成及び使用している箇所が大切です。
この例では、CarクラスはMotorクラスにStartメソッドがあることを知っている必要があり、呼び出す際に引数を指定してはいけないことを知っている必要があります。
つまりCarクラスはMotorクラスに依存していることになり、Motorクラスの変更によりCarクラスの変更が余儀なくされている状態です。

一方で、インタフェースを使用している例を示します。

public interface IMotor
{
    void Start();
    void Stop();
    void ChangeSpeed(int speed);
}

public class Motor : IMotor
{
    ....
}

public class Car
{

    public Car()
    {
        IMotor motor = new Motor();
        motor.Start();
    }
}

こうなるとCarクラスが依存しているのはMotorクラスという実態ではなく、IMotorインタフェースという抽象になります。
言い換えると、Motorクラスを「モータ」たらしめているのはIMotorインタフェースであり、CarクラスはIMotorインタフェースを持つものしか「モータ」として認めない、ということです。
こうなるとMotorクラスの実態はCarクラスに依存します。
ほかにも「モータ」として動作するクラスを作成するときにも、IMotorインタフェースを追加しないとCarクラスで使えなくなるからです。
これがオブジェクト指向で耳にする依存性の逆転になります。
今回の例ではインスタンスを直接生成していますが、本来はFactoryパターンを活用するべきです。

デザインパターン

紹介されているデザインパターンは大まかにNull Object、Adapter、Strategyの3種類でした。
コードでの説明は省略しますが、ざっくり説明すると

Null Object
結果としてnullを返すのではなく、IObjectインタフェースをもつNullObjectクラスを定義することで、null参照例外の発生を防ぎます。
これによって各所に散らばるnull参照チェックが不要になり保守性の向上につながります。

Adapter
使いたいクラスに実装されていないインタフェースをクライアントが使うとき、使いたいメソッドへ委譲するようなインタフェースを持つクラスを参照することで再利用性を高めます。

Strategy
共通のインタフェースを持つクラスに動的にアクセスして、クラスのふるまいを実行中に変更できるようにします。
条件分などでコンストラクタ部分を制御することで、同じ名前のメソッドでも異なる処理に分岐できます。

まとめ

3.3.1以降の内容は今回は省きます。ここまで書いて疲れました。
ダックタイピングはクラスの汎用性を向上させる非常に有効な手段なので、いずれちゃんと調べます。

出典元は忘れてしまいましたが、「オブジェクト指向におけるクラスの継承は、手続き型言語におけるgotoと同じ」ということを聞いたことがあります。
これは適切な利用により有効性を保てるが、過度な活用は保守性を下げるということも含めて言い得て妙だと思います。
インタフェースも過度に使ってしまうと、クラスの実態を追うのが難しくなったり、新しいクラスの作成時の制限が大きくなってしまいます。

次回の更新は2/17を予定しています。