10 Nov 2013, 00:34

UnionFindアルゴリズムを実装してみた

UnionFindをC++で実装した。

UnionFindとは、2つの異なる集合がつながっているかを調べるアルゴリズム。詳しくは以下。

Implement

以下のJavaでかかれた実装をC++版に書き直してみた。木構造にデータを保持する場合と、そう強いない場合の2つを実装。

05 Nov 2013, 15:39

「モダンC言語プログラミング」を読んだ!C言語の組込みエンジニアのためのモダンテクニックが満載

とてもエキサイティングな本に出会い、一気に読んでしまいました。感想を書こうと思います。



ターゲット読者層は組込み分野!

この本のターゲット読者はズバリ、組込みエンジニア。ソースコードのサンプルも、ズバリ組込みな内容を扱っています。C言語を使う人=組込みの人と決めつけているよう。書籍のあちこちで、このアプローチを組込み開発で適応するためにはどうすればいいかという考察が入るのがよい。

TIOBEというプログラミング言語の統計を見ると、C言語を利用している人がプログラマの2割程度いることがわかる。自分はこのデータを初めて知ったけれども、まずこの事実をしれたことは嬉しい事だ。C言語はいかに重要なのかという論題が冒頭で熱く語られる。

 内容について

各章のテーマは、広く浅く書かれているので、もう少し各章の突っ込んだ内容がほしいところだけれども、それはこの本の趣旨には合わないのだろう。

内容は、自分の日々考えていることに非常にマッチしていて、とてもエキサイティングな読後感でした。以下、自分の過去記事も整理しつつ、各章の覚書。

開発環境について

開発環境である、Ubuntuの導入方法と、Eclipseの使い方が紹介されていた。ここは、得るものはなしかな。

オブジェクト指向

C言語でオブジェクト指向のようにコーディングするためのテクニックが紹介されている。半分知っているようで、知らなかった。C言語でも、オブジェクト指向なプログラミングは可能だと気づかせてくれる。

あとは、Cでオブジェクト指向を勉強するならば、ズバリこの本でしょう。これもオススメ。



デザインパターン

自分の来年の重点学習目標の一つが、デザインパターンをマスターすること。この章は、C言語を利用したデザインパターンの実装方法が紹介されている。この章は知らないことが多く、とても興味深かった。

以下のパターンが紹介されている。

  • ステート
  • テンプレートメソッド
  • オブザーバ
  • チェインレスポンシビリティ
  • ビジター

C言語に特化したデザインパターンの本をまだ知らない。これが自分が出会った中で、もっともよくかかれた本かも。この本でも勉強するつもり。まだ読んでない。

いづれにしろ、この章は再読しよう。

TDD リファクタリング

テストフレームワークとして、GoogleTestが紹介される。レガシーコードに対するリファクタリングの実践がサンプルとして載っているのがうれしい。しかも、内容が組込みなので、実践的。パフォーマンスに関する考察もある。

namespaceを利用して、static関数を強引にテストケースに組み込む方法が紹介されていた。C++系のxUnitで利用できるテクニック。

namespace unit_test {
    #include "hogehoge.c"

    TEST(hoge,hogehoge) {
        EXPECT_EQ(3, hoge(1, 2));
    }
}

モックやスタブの定義についての言及は、自分の認識とは違うのだけれども、まあよい。モッキングフレームワークはC言語でいいものがないと書かれていた。そんなことはない、CMockやfffがあるではないか!

CでTDDをするならば、この本が必読本。



継続的インテグレーション

Jenkinsの紹介。これもあまり新しきことはなし。

C言語/C++でJenkins実践入門してみるよ | Futurismo

ビルドスクリプトとして、sConsが紹介されている。なかでも、感心したのが、スモークテストでのPytyonを利用した受け入れテストのアプローチ。pyhthonコードからシリアル接続を経由してテストする方法。この作者はPythonが好きなのかな?自分は、Rubyで同じことをやろうとした。

また、Valgrindを使ったメモリ破壊との戦いも、組込みならでは。こういうことにページを割くところも高評価。ValgrindはLinux用ツールなので、まだ使ったことがないけれども、今度調べてみようかな。

まとめ

組込みの現場ではなぜ、これらのテクニックが浸透しないのだろうか?

Eclipseが浸透しないのは、べつによい。エディタはEclipseだけではないし、EmacsやVimはEclipseに負けないくらいだ。

オブジェクト指向やデザインパターンが浸透しないのは、実行速度やメモリが関係しているのだろう。また、TDDもオブジェクト指向のほうが実施しやすい。(とくにMock)CIは、文化的なものだと思う。

  • 古い考えの人がCProgrammerには多いのだろうか?
  • レガシーコードをメンテナンスしていると、新しいテクニックは不要なのだろうか?
  • 過去の手続き型でかかれたレガシーコードを流用しているから、新しいテクニックを試す場がないのだろうか?

どれも、決定的な理由にはならない。一つ思うのは

「無知」

だからということ。自分もCに関わるいろんな情報を集めているものの、ほかの言語とくらべて、Cは圧倒的に情報量が少ない。Eclipsしかり、TDDしかり、Jenkinsしかり。

C Programmerに足りないものは、道標となるような情報や、書籍だ。C言語は使用率第一位の言語なのだ。これからも、こういう書籍がドンドン出てきてほしい。

04 Nov 2013, 14:46

C++ での優先順位付きキューの使い方まとめ (PriorityQueue)

はじめに

優先順位付きキューのを PriorityQueue という.

キューの中で最大 (最小) のものを抜き出す場合などに利用する.

使い方

宣言

<div class="outline-text-3" id="text-unnumbered-3">
  <p>
    デフォルトでは大きい順で pop されるので, 最小のものを pop で取り出すには, greater を宣言時に追記する.
  </p>

  <p>
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> using namespace std;
  </p>

  <p>
    priority_queue <int> maxpq; // default 大きい順<br /> priority_queue<int, vector<int>, greater<int> > minpq; // 小さい順<br /> [/sourcecode]
  </p>
</div>

関数

<div class="outline-text-3" id="text-unnumbered-4">
</div>

<div id="outline-container-unnumbered-5" class="outline-4">
  <h4 id="unnumbered-5">
    要素を追加する (push)
  </h4>

  <div class="outline-text-4" id="text-unnumbered-5">
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> pq.push (1);<br /> [/sourcecode]
  </div>
</div>

<div id="outline-container-unnumbered-6" class="outline-4">
  <h4 id="unnumbered-6">
    先頭の要素を取り出す
  </h4>

  <div class="outline-text-4" id="text-unnumbered-6">
    <p>
      最大 (または最小) の先頭を取り出します.
    </p>

    <p>
      [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> pq.pop ();<br /> [/sourcecode]
    </p>
  </div>
</div>

<div id="outline-container-unnumbered-7" class="outline-4">
  <h4 id="unnumbered-7">
    要素を調べる
  </h4>

  <div class="outline-text-4" id="text-unnumbered-7">
    [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> // キューがからかどうかを調べる<br /> pq.empty ()</p> 

    <p>
      // 要素数をしらべる<br /> pq.size ();
    </p>

    <p>
      // 次に取り出される要素を調べる<br /> pq.top ();<br /> [/sourcecode]
    </p>
  </div>
</div>

Sample

昇順に取り出す

<div class="outline-text-3" id="text-unnumbered-9">
  [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> #include <iostream><br /> using namespace std;</p> 

  <p>
    int main ()<br /> {<br /> priority_queue<int> pq;
  </p>

  <p>
    pq.push ( 2 );<br /> pq.push ( 1 );<br /> pq.push ( 3 );
  </p>

  <p>
    cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();
  </p>

  <p>
    return 0;<br /> }<br /> [/sourcecode]
  </p>
</div>

<div id="outline-container-unnumbered-10" class="outline-4">
  <h4 id="unnumbered-10">
    実行結果
  </h4>

  <div class="outline-text-4" id="text-unnumbered-10">
    [sourcecode language=&#8221;language&#8221; title=&#8221;&#8221;]<br /> 3<br /> 2<br /> 1<br /> [/sourcecode]
  </div>
</div>

降順に取り出す

<div class="outline-text-3" id="text-unnumbered-11">
  [sourcecode language=&#8221;cpp&#8221; title=&#8221;&#8221;]<br /> #include <queue><br /> #include <iostream><br /> using namespace std;</p> 

  <p>
    int main ()<br /> {<br /> priority_queue<int, vector<int>, greater<int> > pq;
  </p>

  <p>
    pq.push ( 2 );<br /> pq.push ( 1 );<br /> pq.push ( 3 );
  </p>

  <p>
    cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();<br /> cout << pq.top () << endl;<br /> pq.pop ();
  </p>

  <p>
    return 0;<br /> }<br /> [/sourcecode]
  </p>
</div>

<div id="outline-container-unnumbered-12" class="outline-4">
  <h4 id="unnumbered-12">
    実行結果
  </h4>

  <div class="outline-text-4" id="text-unnumbered-12">
    [sourcecode language=&#8221;language&#8221; title=&#8221;&#8221;]<br /> 1<br /> 2<br /> 3<br /> [/sourcecode]
  </div>
</div>

おまけ

ダイクストラ法の実装をする際に, C++ の STL があるとは知らずに, 自前で最小優先キューを実装しました. STL を利用すればよかった.

この Java Sourse を参考に C++ に書きなおした.

MinPQ:

04 Nov 2013, 06:10

秀丸のような罫線マクロないかなと思ってelisp作成した

秀丸エディタやサクラエディタには、Ctrl+Alt+Shift+矢印で罫線が引けるすぐれものマクロがある。

こういう便利な機能がほかのエディタでもないかなといろいろ調べてみたけれども、みつからなかった。

AuthHotKeyのキーバインドで罫線を割り当ててみたところ、左右はいい感じに動くけれども、上下が罫線マクロのように賢くできないので、挫折。

秀丸のような罫線マクロないかな・・・

追記(15/01/09)

Emacs用に elispを作成した.

参考

27 Oct 2013, 14:49

C++11のrandomライブラリで1から10の乱数を生成する方法のメモ

C++で乱数を利用する方法について調べてみた。

やりたいこと

1~10の間で、ランダムな数字を取得する

実装方法

C++には、長らく乱数生成はC言語に頼ってきた歴史があるようだが、C++11でようやくrandomライブラリが標準実装されたようだ。

利用するためには、以下をインクルード。

#include 

覚えないと行けないことが2つある。

  • 乱数生成エンジン ・・・ 乱数を生成する。
  • 分布生成器 ・・・ 生成された乱数を分布に従わせる。一様分布、正規分布、ベルヌーイ分布、ポアソン分布、など。

乱数生成エンジンは種類がたくさんあり、正直どれをつかえばいいのかわからないので、とりあえずコレ。

  // 予測不能な乱数生成器(class   
  std::random_device
  // メルセンヌツイスターの32ビット版(typedef)
  std::mt19937

分布は一様分布を利用。これは、intとdoubleでつかうエンジンが異なる。

`// 整数型 std::uniform_int_distribution // 浮動小数点型 std::uniform_real_distribution

追記`

randomライブラリは実行速度がrandに比べて早くないことが判明!なので、srand,randを使った方法も追記。srandはループの外で宣言する必要がある。

実装

-std=gnu++0xをコンパイルオプションにつけることを忘れないように。

こんな感じで、生成されました。

5.28957
8.79693
5.23333
1.76491
3.95931
5.52467
8.1513
6.85362
1.68268
9.75644

27 Oct 2013, 13:48

Eclipse CDTで変数や関数が赤バツになってしまう場合の対処方法(C++11対応も)

Eclipse CDTで変数や関数が赤バツになってしまう場合の対処方法

Eclipseに外部のソースをインポートすると、赤バツがたくさんでることがある。また、C++11対応のソースが赤バツになることがある。

これは、CDTのインデックス機能がインデックスをするときに、ファイルパスの場所やプリプロセッサの定義値を知らないから。

パスおよびシンボルを設定

こんなときは、プロジェクトを右クリックしてプロパティを選択。

  • C/C++一般 -> パスおよびシンボル

ここでMakefileに書くような情報(インクルードパスやdefine値)を設定することで、赤バツが消える。たとえば、

  • インクルードパスを追加する場合にはインクルードを選択。
  • define値を追加するときにはシンポルを選択。

Eclipse CDTで C++11のソースを赤バツにしない方法

すでにEclipseの設定でdefine値が設定してあると、自分の値が反映されないことがある。C++11などはまさにそうだった。この場合は、

  • C/C++一般 -> Prosessor Include, Macro..->エントリ -> CDT User Setting Entrys

であたいを追加する。

__cplusplus = 201103L

27 Oct 2013, 02:40

自由自在にコード内を飛び回る!Eclipseのコードリーディング機能が便利

Eclipseには、コードを読みやすくするための様々な機能が備わっています。

GUIだからマウスをたくさんつかうんだろうという迷信がありますが、実際はキーポードから手を離さなぽことがおおいです。

キーバインドを巧みに利用して、コード内を自由自在に飛び回るためのテクニックを紹介します。

[toc]

[//www.youtube.com/embed/db4vCH7oqG8?rel=0]

宣言を開く(F2,F3)

関数や宣言の場所へジャンプすることができます。いわゆる、タグジャンプ、EmacsのGNU Grobalのようなもの。もっともよく利用する機能です。

F3で飛んで、Alt + 左で元に戻る。これでソースコード内をマウスを利用せずにピョンピョンと移動することができます。

F2を押すと、飛ばずにポップアップで宣言の場所を表示することができます。

呼び出し階層を開く(Ctrl+Alt+h)

関数がメソッドがどこの関数から呼ばれているかを順々に表示してくれる機能。

リファクタリングの時の修正による影響範囲を調査する時、重宝する機能。

型階層を開く(F4)

クラスの型を階層的に表示てくれる機能。継承関係が分かる。

C++だと機能するけれども、Cだとよくわからない機能。あまり利用しない。

エディタバッファを開く(Ctrl + x + b)

ファイル間の移動は、ショートカットで新規にファイルを開くこともあるけれども、もともと開いているファイルに飛ぶこともデキる。

このキーバインドは、Emacsキーバインドを設定しているので、Emacsに慣れている人はそのキーバインドをそのままEclipseでも利用できる。すなわち、Ctrl + x + b。

Alt + 左で前へ戻り、Alt + 右で次へ進むことができる。もはやブラウザでWebページを見るような感じ。

検索で飛ぶ

デフォルトのEclipse CDT検索機能は利用しません。代わりに、プラグインを利用します。

検索結果をクリックするだけで検索箇所へジャンプできるので、コンソールからgrepして検索するよりも効率がよいです。

26 Oct 2013, 17:01

モダンディでイケイケなTDDの最新動向が集結!『Modern C++ Programming with Test-Driven Development』

『Modern C++ Programming with Test-Driven Development』をだいたい読み終わりましたので、感想を書きます。

各章の概要

各章の概要と、学習メモは以下のエントリを参照。

初めは懇切丁寧にTDDの基礎が述べられているので、モダンだからと言ってもTDD実践入門に最適。 使われているフレームワークは、

  • GoogleMock
  • CppUTest

Mockに関する説明は少なかったように思う。一部のテクニックを書くのではなくて、まんべんなく書かれているイメージ。

また、コンパイラはC++11を使っていて、見慣れないC++の文法がたくさん出てきたのが少しつらかったところ。このへんも、モダン。

写経について

この本は、ところどころ写経しながら読みました。写経環境の導入手順は以下にまとめました。あとから思うと、Ubuntuが一番楽じゃないかと思う。

電子書籍なので、本からウェブ上のソースコードにリンクが張ってあります。すべてをそのまま写したところもありますが、ちょっと手を抜いて、サンプルコードをコピペしながら読んだところもあります。 サンプルコードを実際に動かしたり、diffを取ったりしながら読んだほうが、理解が深まりますね。

感想

モダン!( ー`дー´)

この名に恥じない内容だった。新しいテクニックや考え方にワクワクして、明治時代の人がザンギリ頭に触れる喜びを感じた。

西洋のTDD界ではkataだとかdojoだとかMikadoだとかがブームだというおかしなジャポニズムを初めて知った。そんなニッポンはShakyoがブーム?この本を通してKataを知ったのは収穫だった。今後の勉強の進む方向はコッチだ。

個人的には、『test driven development for embedded c』に続く良書。ただし、かつての感動はなかった。もともと、前半の内容は知っていることが多かったので。C++というのも、Cに比べると疎遠なので。

サブタイトルが『Code Better, Sleep Better』となっている。

Code Betterは、リファクタリングについての話題が多め。実際のサードパーティから依存関係を取り除いたり、実際のレガシーコードを利用したリファクタリングしたりする。理想的なTDDなどありえなくて、現実はとてつもないレガシーコードと戦わなければいけない。現実に則した本だ。我らの味方だ。

Sleep Betterがなにを暗示しているのかワカラなかったので、そろそろ寝ます。おやすみなさい(´-ω-`)

26 Oct 2013, 16:02

『Modern C++ with TDD』学習メモ(Chapter6-11)

『Modern C++ with TDD』後半分の学習メモです。前半部分は、ココ。

『Modern C++ with TDD』学習メモ(Chapter2-5) | Futurismo

各章の概略

  • Chapter6: Incremental Design 主にリファクタリングの話題。どうやってシンプルなコードを作っていくかを実践する。1行でも関数として抽出する。インクリメンタルに、デザインを作り上げていくその開発スタイルが『モダン』といっている。
  • Chapter7: Quality Tests テストの書き方について。FIRSTの原則の紹介。一つのテストでひとつのことを検証する、テストの名前付に慎重になる。そして、テストコードのリファクタリングの実践、ほかTips。
  • Chapter8: Legacy Challenges 実際のレガシーコードを使ったリファクタリング体験。いきなり200Stepsのうんこメゾッドが出される。ここでは、CppUTestを使う。テクニックは『レガシーコード改善ガイド』に載っているもの。この章は,必読。涙がでるほど素晴らしかった。
  • Chapter9: TDD and Threading マルチスレッドのプログラムに対するTDDのアプローチの紹介。正直、ここは理解できなかった。
  • Chapter10: パフォーマンスや受け入れテスト、TPPなどの、TDDを発展させた話題を取り扱う。
  • Chapter11: Growing and Sustaining TDD おまけのような、未分類の小さな話など。Code Jodo、マネージャーへのTDDの説得方法、参考リンクなどなど。

StudyMemo

Small Methods

一行の論理でもメソッドとして抽出する。その理由は、

  • Methods名が機能を現してコメント代わりになる。
  • 重複を排除するためのスタートになる。
  • パフォーマンスは瑣末なものだ。

Chapter6は 1990年代では、奇妙なことがよいこととされてきた、と結論づけられる。いまは、このような過剰なリファクタリングは奇妙に見えるけれども、20年後はこれ普通になるのだよ、と。

Chapter10では、実際に簡単な数値実験が行われる。inlineメソッド、Smallメソッド、inline無効にした場合で実験。inlineメソッドとSmallメソッドのパフォーマンスはほぼ同じ、だけどinline無効メソッドは時間がかかる。

最近のコンパイラは頭がいいから、小さな関数は勝手に最適化してくれる。なので、Smallメソッドはパフォーマンスを阻害しないと。他人のいうことに耳を傾けてはいけない、彼らは同じことをいうだけなので。

ここにも、数値実験があった。このリンクの記事はリファクタリングについてよく語っていて興味深い。数値をみると、なるほどと思う。

自分でも実験してみた。だいたい、変わんない。

パフォーマンスが懸念だが、そもそもパフォーマンスがネックというのは迷信なのか?オーバーヘッドは無視していいのか?未来は、パフォーマンスは瑣末な問題になるのだろうか?

コードにコメントを書くことについても、『コード自身が語っているのに、なんで冗長なコメントを書くの』と。

FIRSTの原則

良いテストは以下の5つに従う。

  • F First
  • I Isolated
  • R Repeatable
  • S Self-Verifiying
  • T Timely

Mikado Method

ミカドメソッドとは、大規模なコードをリファクタリングするための方法論。 別記事にまとめました。

Code Kata

これは別記事にまとめました。

Transformation Priority Premise

ボブおじさんが考案した、TDDをより簡単に実施するための方法。

“Uncle Bob” Martin – The Transformation Priority Premise from 8th Light on Vimeo.

26 Oct 2013, 15:29

コーディングをもっともっと加速する!Eclipseのコード補間機能まとめ

Eclipse CDTの強力な(Javaに比べると見劣りする)単語補間、コンテンツ・アシスト機能を紹介します。

これで、超高速なコーディングが可能??

単語補間

途中まで単語を入力したあとに、単語補間を実行すると、エディタ内の似ている単語で補間してくれる。

ちなにみ、単語補間は Alt+/に割り当てて、コンテンツ・アシストは Ctrl+Spaceに割り当てている。キーバインドが競合していると、補間が発動しないので、注意すること。競合していたときは、検索窓から Alt+/で競合コマンドを検索して、アンバインドする。

コンテンツ・アシスト

設定のカスタマイズは、以下を選択。

  • 設定 -> C/C++ -> エディタ -> コンテンツ・アシスト

自動有効化でトリガを設定できるので、とりあえずすべてチェックを入れる。トリガが発動するまでの時間も100ms以下にすると、高速でアシストが発動する。

構造のメンバだったり、関数名だったりを、これでガンガン置換できます。

ちなみに、コンテンツ・アシストで出てくるコードテンプレートは自分でも作成できます。以下の記事参照。メタプログラミングが可能です。

Javaならば、Code Recomennderという強力なプラグインがあるものの、CDTにはない。

クイック・フィックス

赤バツが表示されている時に、どう修正すればいいかを教えてくれる。

Ctrl+,でエラー箇所に飛んで、Ctrl+1を次々に実施してエラー箇所を修正。

Javaに比べると、CDTのクイックフィックスは貧弱。定義がないメソッドがあった場合、Javaならコード生成までしてくれるが、CDTはそこまではしてくれない。

パラメータのヒント

これはおまけのような機能。

引数の型をわすれたときにはこれ。ポップアップで教えてくれる。