5 minutes note

日記、技術メモ、勉強記録など。

【C++】デザインパターン:Iteratorパターン

集合の各要素に順次アクセスする仕組みを作るパターン。

クラスに集合の役割をもたせ、イテレータを提供させることで、順次アクセス可能にする。

集合の要素を直接参照するのではなく、イテレータを介してアクセスすることで、集合の具体的な実装方法(配列とかListとかVectorとか)に依らず要素を数え上げられるようになることがメリット。

イテレータの振る舞いも好きに実装できるので、例えばある条件に適合する要素だけイテレーションする(部分集合のイテレーション)、みたいなことができると思う。

ソースコード

C++11で記述。

本棚クラスを本クラスの集合として扱う。

本棚クラスにイテレータを提供させ、イテレータを介して本クラスのメンバ関数にアクセスしている。

#include <iostream>
#include <string>
#include <vector>
#include <memory>

class Iterator;
class Book;

// クラスをイテレータをもつ集合として扱うためのインタフェース
class Aggregate {
public:
    virtual std::unique_ptr<Iterator> GetIterator() = 0;
};

// イテレータとしての役割を与えるインタフェース
class Iterator {
public:
    virtual ~Iterator(){};
    virtual bool HasNext() = 0;
    virtual void* Next() = 0;
};

// 本を表すクラス (集合の要素)
class Book {
public:
    void SetName(const std::string name) {
        this->name_ = name;
    }

    std::string GetName() {
        return this->name_;
    }
private:
    std::string name_;
};

// 本棚を表すクラス (集合)
class BookShelf : public Aggregate {
public:
    BookShelf(const int maxSize)
    : bookCount_(0) {
        books_.resize(maxSize);
    }

    Book* GetBookAt(const int index) {
        return &(this->books_[index]);
    }

    void AppendBook(const Book book) {
        this->books_[bookCount_] = book;
        bookCount_++;
    }

    int GetLength() {
        return bookCount_;
    }

    std::unique_ptr<Iterator> GetIterator() override;

private:
    std::vector<Book> books_;
    int bookCount_;
};

// イテレータ
class BookShelfIterator : public Iterator {
public:
    BookShelfIterator(const BookShelf bookShelf) :
        bookShelf_(bookShelf), index_(0) {}

    bool HasNext() override {
        if(index_ < bookShelf_.GetLength()) {
            return true;
        } else {
            return false;
        }
    }

    void* Next() override {
        Book *pBook = bookShelf_.GetBookAt(index_);
        index_++;
        return pBook;
    }

private:
    BookShelf bookShelf_;
    int index_;
};

std::unique_ptr<Iterator> BookShelf::GetIterator() {
    return std::unique_ptr<BookShelfIterator>(new BookShelfIterator(*this));
}

int main() {

    Book book1;
    Book book2;
    Book book3;
    Book book4;
    book1.SetName("Inherit the Stars");
    book2.SetName("2001: A Space Odyssey");
    book3.SetName("The Door into Summer");
    book4.SetName("Do Androids Dream of Electric Sheep?");

    BookShelf bookShelf(4);
    bookShelf.AppendBook(book1);
    bookShelf.AppendBook(book2);
    bookShelf.AppendBook(book3);
    bookShelf.AppendBook(book4);

    auto it = bookShelf.GetIterator();

    while(it->HasNext()) {
        Book *book = reinterpret_cast<Book*>(it->Next());
        std::cout << book->GetName() << std::endl;
    }
}

参考

以下の書籍、Webページを参考にしました。

myenigma.hatenablog.com

CODE COMPLE 上巻 読了

www.amazon.co.jp

とても有名な本。
密かに尊敬しているエンジニアであるhigepon氏のインタビュー記事で興味をもった。

書籍の概要は以下のとおり。(Amazon商品ページから引用)

米ソフトウェア界の第一人者Steve McConnellが執筆した名著「Code Complete」(1993年発行)の第2版。Jolt賞を受賞した初版の内容を受け継ぎ、さらに新しいトピックを盛り込んで、プログラミングのベストプラクティスを集大成した待望の書です。上巻は「ソフトウェアコンストラクション」から始まり、変数名、データ型、ループ、条件判定、ルーチン、クラスなど、高品質なプログラムを作成するための基本的なテクニックを解説します。初心者はもちろん、経験豊富なプログラマにも開眼のテクニックを実践的に紹介。著者Steve McConnellのプログラミングに対する見識と経験のすべてが詰め込まれた、価値ある1冊です。

読了までにかかった日数はだいたい10日ほど。主に通勤電車内と帰宅後の自宅で読んだ。
600ページ超と、かなりボリューミーで読み応えのある本だったけど、勢いに任せて一気に読み切った。

最近、設計を含むソフトウェア開発全体の力不足に悩んでいた自分にとって、目指すべき指針を与えてくれる、まさにバイブルと呼ぶべき本だった。
こうした知識は一度読んだだけで身に付くようなものではないので、折に触れて読み返しながら実践していきたい。

下巻も注文したので、届き次第読む。

コラム7 封筒の裏で... 【珠玉のプログラミング】

要点

  • 封筒裏の計算」(フェルミ推定として知られている)で見積もりや評価をしよう。
  • 基本テクニック:
    • 2つの異なるアプローチの計算結果を比較して妥当性を確認しよう
    • 次元によるチェック ... 単位も含めて計算しよう
    • 72の法則 ... 指数関数的な動きを見せるものを簡単に評価できる近似計算

      y年間、利率rパーセントでお金を貯金し続けるとします。このルールは、「もし、y x r = 72なら、お金はほぼ倍になっている」というものです。

  • 安全係数を考慮に入れよう。安全係数は自身の無知を補ってくれる。
  • Littleの法則 ... システム内にあるものの平均的な数は、それらがシステムから出ていく平均的な率とシステム内にある平均的な時間の積に等しい。また、もし入るのと出るのが全体的に釣り合っているなら、出ていく率は入ってくる率に等しい
    • 例:お店に入る列に並んだとき、どのくらい待たされるか?

      中には60人ほど入れる。それから、中にいる平均的な時間は3時間くらいだろう。とすると、1時間に20人ずつ入っていることになる。列には20人くらいいるので、ここでは1時間ほど待つことになるだろう。

  • 計算は単純化したほうがいいが、単純化しすぎてはいけない。

問題への回答

1

時速200マイル(時速320メートル)って新幹線の最高時速と同じくらい。
川の流れにしては速すぎでは?

2

通信速度は10Mbps、記憶装置の容量(転送するデータ量)は10GB、自転車の時速は10kmとする。
データ転送にかかる時間は800秒。自転車は800秒で2.5km進む。
よって2km程度の距離なら自転車で運んだ方が効率的。
(ちなみに、運ぶデータ量を1TBで計算したら自転車が有利になりすぎたので、問題設定を変えた)

3

タイピング速度は1分あたり250文字とする。フロッピーディスクの容量は720キロバイト
1文字1バイトとすると、720,000文字でいっぱいになるので、単純計算で48時間かかる。
1日の稼働時間を12時間としても、休みなくタイピングし続けて4日必要。
現実的に考えて休みなく打ち続けるのは無理なので、1 ~ 2週間くらいはかかるんじゃないかな。

4

CPUの動作周波数が2.2GHzなので、世界が100万分の1のスピードで動くとすると、周波数は2.2kHzになる。 1クロックでひとつ命令を処理できるとすると、命令を1つ実行するのにかかる時間は450usくらい。

5

省略。

6

72の法則を使ってみる。
1.33 x 52 ≒ 69 なので、72に少し届かないくらい。
2倍弱増加すると考えると、2050年の人口は100億人くらい。

7

省略。

8

省略。

9

1回のディスクアクセスで読み出すデータ量を1KBとする。
ディスクアクセス速度を1MB/sとする。
1アクセスに1msかかるので、1トランザクションあたり100msかかる。
よって、1時間に処理できるトランザクションは36,000個くらい。

10

省略。

11

分からなかった。

12

分からん。

コラム6 パフォーマンスに関する考察 【珠玉のプログラミング】

要点

  • コンピュータシステムのデザインレベル
    • 問題定義
    • システム構造
    • アルゴリズムとデータ構造
    • コードチューニング
    • システムソフトウェア
    • ハードウェア
  • パフォーマンスチューニングするときは、どのデザインレベルで考えるべきか検討するべし
  • 異なるデザインレベルのチューニングは掛け算で効いてくる
  • どのレベルを考えているときも、全体象は見失わないように

問題への回答

1 ~ 4

省略。

5

人材にかかる時間やお金(学習や採用活動など)、稟議を通すのにかかる時間、設備投資のお金、検証にかかる時間・お金、消費エネルギーなどなど。

6

Appelの例のように、近似計算でも充分に有用な場合もある。

7

交通事故の怪我でいうと、まず交通事故自体を減らすか、怪我の程度を軽くするか、大きな怪我でも治せるようにするか、といった問題定義のレベルがある。 そこから、事故を起こしにくい法整備かなどの法律のレベル、事故が起きにくい・起きても大事になりにくい道路設計かなどのデザインのレベル、事故が起きてもドライバーが怪我をしにくい車体構造かなどの乗り物のレベル、大きな怪我でも治療できるかといった医療技術のレベル、難しい手術もこなせるかといった医師のレベル、大怪我でも治癒できる身体かという本人のレベルなどが考えられる。

コラム5 あと少しの事 【珠玉のプログラミング】

要点

  • アルゴリズムをコード化したら、システムに組み込む前に、充分にテストや実行時間測定をするべし。

  • 関数をテストする際は、システムの中に置くのではなく、関数を呼び出してチェックするための「足場」を作ろう。(単体でテストしよう)

  • 機能の正しさだけでなく、実行時間も確認するべし。実行時間が問題にならないなら、複雑なソートアルゴリズムは必要とされない。

問題の回答

1

この本に出てくる変数名は自分にはかなり短く感じる (スコープが短いからこれで充分といえば充分だけど)。
2分探索の形式や説明については特にコメントがない。
プログラミングスタイルについて、契約プログラミングという手法をこの本で初めて知ったけれど、 複雑なアルゴリズムを安全に書くために有用そうだと思った。

2 ~ 9

とばした

コラム4 正しいプログラムを書く 【珠玉のプログラミング】

自分の回答を乗せる。

1

0除算:
起きない?

オーバーフロー:

  • n-1がuの型で表現可能かチェック
  • (l + u) / 2がmで表現可能かチェック
  • mがpで表現可能かチェック
  • m+1がlの型で表現可能かチェック

配列の範囲外参照:
l, uが0未満、または配列の大きさ以上になっていないかチェック

証明の形式化:
分からなかった

2

分からなかった

3

探索範囲は外から与えるようになる。
中央の値mの計算や条件分岐は変わらない。
question3.cpp参照。

4

nの大きさをn=1からある程度の大きさまでインクリメントしながら2分探索を行い、 与えたnから計算されるlogn2の値と実際の比較回数をプロットする。

5

xが発散するためループは終了しないのでは?

6

黒豆が減るのは取り出した豆が2つとも黒豆のときで、黒豆は1度に1つずつしか減らない。 そのため最後の1つになった黒豆が取り出されることはなく、黒豆が缶の中からなくなることはない。

白豆が増えることはなく、2つとも黒豆という条件の場合以外、白豆は減り続ける。
2つとも黒豆という条件が常に成り立つのは、缶の中に黒豆だけが2個以上残っている場合のみ。
この条件が常に成り立つことはないので、最終的に白豆はなくなる。

缶の中に黒豆しかない場合、黒豆が最後の1つになるまで、2つとも黒という条件が常に成り立つ。
したがって最終的に缶の中には黒豆が1つだけ残る。

7

分からなかった

8

  • 配列を分割して並列処理する
  • CPUの性能を上げる
  • メモリアクセスを高速化する
  • 専用回路を作る

9

9-1

/* a, b, cは長さnの配列 */
i = 0
while i < n
  /* a[i-1] == b[i-1] + c[i-1] */
  a[i] = b[i] + c[i]
  i = i + 1
  /* a[i-1] == b[i-1] + c[i-1] */
/* i == n && a[i-1] == b[i-1] + c[i-1] */

9-2

/* xは長さnの配列 */
max = x[0]
i = 1
while i < n do
  /* x[i-1] <= max */
  if x[i] > max
    /* x[i-1] <= max < x[i] */
    max = x[i]
  i = i + 1
  /* x[i-1] <= max */
/* i == n && x[i-1] <= max */

9-3

/* xは要素数nの配列 */
i = 0
while i < n && x[i] != t
  /* i <= n && x[i-1] != t */
  i = i+1
  if i >= n
    /* i <= n && x[i-1] != t */
    p = -1
  else
    /* i < n && x[i-1] != t */
    p = i
  /* i <= n && x[i-1] != t */
/* (i == n || (i < n && x[i] == t)) && x[i-1] !=t */

9-4

function exp(x, n)
  /*
   * 前提条件:n >= 0
   * 結果:result = x^n
   */
  
  if n = 0
    return 1
  else if nが偶数なら
    /* n%2 == 0 */
    return exp(x, n/2)の2else
    /* n%2 != 0 */
    return x*exp(x, n-1)

10

とばした

11

とばした

感想

なかなか契約プログラミングの考え方に馴染めず時間がかかった。まだうまく飲み込めていない気がする。 数学の苦手な単元に取り組んでいるようなもどかしさがある。

ソースコード

// question3.cpp

#include <iostream>
#include <vector>
#include <numeric>

constexpr int ARRAY_SIZE = 100;

int binarySearch(const int t, const std::vector<int> v, int l, int u) {
  if(l < 0 || u >= v.size()) return -1;
  if(l > u) return -1;

  int m = (l + u) / 2;

  if(v[m] < t) l = m + 1;
  else if(v[m] == t) return m;
  else if(v[m] > t) u = m - 1;

  return binarySearch(t, v, l, u);
}

int main(int argc, char** argv) {
  if(argc != 2) return -1;

  int t = std::atoi(argv[1]);
  if(t >= ARRAY_SIZE) return -1;

  std::vector<int> v(ARRAY_SIZE);
  std::iota(v.begin(), v.end(), 0);

  std::cout << binarySearch(t, v, 0, v.size() - 1) << std::endl;

  return 0;
}

コラム3データで決まるプログラムの構造 【珠玉のプログラミング】

自分の回答を載せる。

1

似た処理の繰り返しなのでまとめられそう。
例えば以下のようなイメージ?もっと効率的な構造がありそうだけど思いつかない。

  int th[n] = {0, 2200, 2700, 3200, 3700, ..., 102200};

  std::map<int, int> offset;
  offset[0] = 0;
  offset[2200] = 0;
  offset[2700] = 70;
  ...

  std::map<int, double> rate;
  rate[0] = 0;
  rate[2200] = 0.15;
  ...
 
  int i  = 0;
  while(1) {
    if(income >= th[i]) i++;
    else break;
  }

  double tax = offset[th[i]] + rate[th[i]] * (income - th[i]);

2

実装イメージ。疑似コード。

a[k] = {...};
c[k+1] = {...};
for(i = 1; i <= m; i++) {
  a_n = 0;
  for(j = 1; j <= k; j++) {
    a_n += c[j] * a[i - j];
  }
  a_n += c[k + 1];
  printf(a_n);
}

ある特定の5次線形漸化式だけを解くなら、ベタ書きするだけなので頭は使わずに済むので簡単?

将来的に次数が変わる可能性が少しでもあるなら一般化したほうがいい。

3

問題の意味が分からない。

4

とばした。

5

ざっくりとした実装イメージ。
用意されたルールの各文字列を反転して配列に格納する。 与えられた単語も反転する。
ルールの配列から1つずつ文字列を取り出す。
与えられた単語と各文字列を1文字ずつ比較する。ただしハイフンは飛ばしてその位置を記録。 文字が不一致したら配列の次の要素へ移る。
ルールの文字列の最後の文字まで一致したら、その文字列が与えられた単語のルールとなる。 配列の最後の要素まで不一致したら適合なし。
最後に、記録したハイフンの回数と位置に基づいて与えられた単語にハイフンを挿入する。

6

3.2の定型文プログラムと同様のプログラムを作成する。 テストのために雛形通りのレコードと雛形と一致しないレコードを与える。

7

単語の正しいスペルと韻を示す辞書:
単語のスペルをキー、韻をバリューにした連想配列にする。

整数列の辞書:
フィボナッチ数列。予めサイズnを決めておき、n番目までの解を計算し配列に入れて返す。

化学構造の辞書:
名前をキー、組成式をバリューにした連想配列をつくる。

歌の韻律の辞書:
1次元配列で表現できそう。

8

7セグに表示したい数字をキー、点灯状態をbitで表現したときの10進数の値をバリューとした連想配列を作る。 question8.cpp参照。

感想

今回の章にあった、見習いたい心構え。

"優秀なプログラマは、コードを書く前に、そのプログラムの入力、出力、中間のデータ構造を徹底的に理解するものだということです。" p.38

ソースコード

//question8.cpp
#include <iostream>
#include <map>
#include <array>

class SevenSegmentDisplay {
public:
  SevenSegmentDisplay() {
    this->segdict[0] = 125;
    this->segdict[1] =  80;
    this->segdict[2] =  55;
    this->segdict[3] =  87;
    this->segdict[4] =  90;
    this->segdict[5] =  79;
    this->segdict[6] = 111;
    this->segdict[7] =  92;
    this->segdict[8] = 127;
    this->segdict[9] =  94;
  }

  ~SevenSegmentDisplay(){}

  std::vector<int> convert(const unsigned short num);

private:
  std::map<unsigned char, unsigned char> segdict;
};

std::vector<int> SevenSegmentDisplay::convert(const unsigned short num) {
  std::vector<int> segdata(5);

  int d = 10000; 
  int n = 0, a = 0, _a = 0;

  for(int i = 0; i < 5; i++) {
    a = a;
    a = num / d;
    n = a - _a * 10;
    segdata[i] = segdict[n];
    d = d / 10;
  }

  return segdata;
}

int main() {

  SevenSegmentDisplay sd;

  std::vector<int> a = sd.convert(12345);

  return 0;
}