C++ 言語のチュートリアル
このチュートリアルの前半では、前の 2 つのモジュールですでに紹介した基本的な内容を取り上げ、高度なコンセプトについて詳しく説明しています。このモジュールでは動的メモリに焦点を当て、オブジェクトとクラスについて詳しく説明します。継承、ポリモーフィズム、テンプレート、例外、名前空間などの高度なトピックも紹介されています。これらについては、高度な C++ コースで後ほど学習します。
オブジェクト指向の設計
これは、オブジェクト指向設計についての優れたチュートリアルです。ここでは、このモジュールのプロジェクトで紹介した方法論を適用します。
例 3 で学ぶ
このモジュールは、ポインタ、オブジェクト指向設計、多次元配列、クラス/オブジェクトの活用方法に重点を置いています。以下の例で考えてみましょう。優れたプログラマーになるための秘訣は、練習、練習、そして練習を重ねることです。これはいくら強調しても足りないほどです。演習 1: ポインタを使ってさらに練習する
ポインタの使い方をさらに練習する必要がある場合は、こちらのリソースをご覧ください。ポインタのあらゆる側面と、多くのプログラムの例が掲載されています。
次のプログラムの出力は次のようになります。プログラムを実行せずに、メモリの絵を描いて出力を判断してください。
void Unknown(int *p, int num); void HardToFollow(int *p, int q, int *num); void Unknown(int *p, int num) { int *q; q = # *p = *q + 2; num = 7; } void HardToFollow(int *p, int q, int *num) { *p = q + *num; *num = q; num = p; p = &q; Unknown(num, *p); } main() { int *q; int trouble[3]; trouble[0] = 1; q = &trouble[1]; *q = 2; trouble[2] = 3; HardToFollow(q, trouble[0], &trouble[2]); Unknown(&trouble[0], *q); cout << *q << " " << trouble[0] << " " << trouble[2]; }
出力を手動で判断したら、プログラムを実行して正しいかどうかを確認します。
演習 2: クラスとオブジェクトの使い方をさらに練習する
クラスとオブジェクトについてさらに学習する必要がある場合は、2 つの小規模なクラスの実装に関するこちらのリソースをご覧ください。時間をかけてエクササイズを行ってください。
演習 3: 多次元配列
以下のプログラムを検討してください。
const int kStudents = 25; const int kProblemSets = 10; // This function returns the highest grade in the Problem Set array. int get_high_grade(int *a, int cols, int row, int col) { int i, j; int highgrade = *a; for (i = 0; i < row; i++) for (j = 0; j < col; j++) if (*(a + i * cols + j) > highgrade) // How does this line work? highgrade = *(a + i*cols + j); return highgrade; } int main() { int grades[kStudents][kProblemSets] = { {75, 70, 85, 72, 84}, {85, 92, 93, 96, 86}, {95, 90, 83, 76, 97}, {65, 62, 73, 84, 73} }; int std_num = 4; int ps_num = 5; int highest; highest = get_high_grade((int *)grades, kProblemSets, std_num, ps_num); cout << "The highest problem set score in the class is " << highest << endl; return 0; }
このプログラムには、「この行の仕組み」という行があります。 - 答えはわかりますか? こちらで説明をご覧ください。
3 次元配列を初期化し、3 次元の値を 3 つすべてのインデックスの合計で埋めるプログラムを作成します。こちらで解決策をご覧ください。
演習 4: 広範な OO 設計例
プロセス全体を最初から最後まで通じる、詳細なオブジェクト指向設計の例をご覧ください。最終的なコードは Java プログラミング言語で記述されていますが、これまでの知識を身に付ければ、問題なくコードを読むことができます。
時間をかけてこの例全体を処理してください。プロセスとそれをサポートするデザインツールがわかりやすく説明されています。
単体テスト
はじめに
テストは、ソフトウェア エンジニアリング プロセスの重要な要素です。単体テストは、ソースコードの小さな単一のモジュールの機能をチェックするテストです。単体テストは常にエンジニアが行い、通常はモジュールのコーディングと同時に実施します。単体テストの例としては、Composer クラスと Database クラスをテストする際に使用したテストドライバがあります。
単体テストには次の特性があります。広告主は...
- コンポーネントを単独でテストする
- 決定的である
- 通常は 1 つのクラスにマッピングされ、
- 外部リソース(データベース、ファイル、ネットワークなど)への依存を避ける
- 迅速に実行
- 任意の順序で実行できる
大規模なソフトウェア エンジニアリング組織には、単体テストのサポートと整合性を提供する自動化されたフレームワークと手法があります。このレッスンの後半で、いくつかの洗練されたオープンソースの単体テスト フレームワークについて説明します。
単体テストの一環として行われるテストを以下の図に示します。
理想としては、以下をテストします。
- モジュール インターフェースは、情報が正しく入出力されることを確認するためにテストされます。
- ローカルデータ構造は、データが適切に保存されていることを確認するために調査されます。
- 処理を制限または制限する境界でモジュールが正しく動作するかどうかを確認するために、境界条件がテストされます。
- モジュール内の独立したパスをテストして、各パス、つまりモジュール内の各ステートメントが少なくとも 1 回実行されるようにします。
- 最後に、エラーが適切に処理されていることを確認する必要があります。
コード カバレッジ
実際には、テストで完全な「コード カバレッジ」を達成することはできません。コード カバレッジとは、ソフトウェア システムのどの部分がテストケース スイートによって実行(カバー)されていて、どの部分が実行されていないかを判断する分析方法です。100% のカバレッジを達成しようとすると、実際のコードよりも、単体テストの作成に多くの時間を費やすことになるでしょう。次のすべての独立したパスの単体テストを作成することを検討してください。これはすぐに指数関数的な問題になる可能性があります。
この図では、赤い線はテストされませんが、色付けされていない線はテストされています。
100% のカバレッジを目指すのではなく、モジュールが適切に動作しているという確信を高めるテストに注力しています。次のようなテストを実施しています。
- null ケース
- 範囲検定(例: 陽性/陰性値の検定)
- エッジケース
- 失敗例
- ほとんどの場合に実行される可能性が高いパスをテストする
単体テスト フレームワーク
ほとんどの単体テスト フレームワークは、パスの実行中に値をテストするためにアサーションを使用します。アサーションは、条件が true であるかどうかをチェックするステートメントです。アサーションの結果は、成功、非致命的な失敗、致命的な失敗のいずれかになります。アサーションの実行後、結果が成功または致命的でない失敗であれば、プログラムは通常どおり続行されます。致命的なエラーが発生すると、現在の関数は中止されます。
テストは、状態の設定やモジュールの操作を行うコードと、予期される結果を検証するいくつかのアサーションで構成されます。テスト内のすべてのアサーションが成功した場合(true を返した場合)、テストは成功し、それ以外の場合は失敗します。
テストケースには 1 つまたは複数のテストが含まれます。テストは、テスト対象のコードの構造を反映したテストケースにグループ化されます。このコースでは、単体テスト フレームワークとして CPPUnit を使用します。このフレームワークを使用すると、C++ で単体テストを作成して自動的に実行し、テストの成功または失敗に関するレポートを生成できます。
CPPUnit のインストール
SourceForge から CPPUnit コードをダウンロードします。 適切なディレクトリを見つけて、tar.gz ファイルを配置します。続けて、以下のコマンド(Linux、Unix の場合)を適切な cppunit ファイル名に置き換えて入力します。
gunzip filename.tar.gz tar -xvf filename.tar
Windows で作業している場合は、tar.gz ファイルを抽出するユーティリティが必要になることがあります。次のステップは、ライブラリのコンパイルです。cppunit ディレクトリに移動します。具体的な手順が記載された INSTALL ファイルがあります。通常は以下を実行する必要があります。
./configure make install
問題が発生した場合は、インストール ファイルをご覧ください。通常、ライブラリは cppunit/src/cppunit ディレクトリにあります。コンパイルが機能したことを確認するため、cppunit/examples/simple ディレクトリに移動して「make」と入力します。コンパイルに成功すれば、準備は完了です。
優れたチュートリアルについては、こちらをご覧ください。このチュートリアルに沿って、複素数値クラスと、それに関連する単体テストを作成してください。cppunit/examples ディレクトリには、その他の例もいくつかあります。
この操作が必要な理由
単体テストは、いくつかの理由から業界で非常に重要です。一つの理由として、コードの開発中に作業を確認する方法が何か必要です。ごく小さなプログラムを開発する場合でも、プログラムが期待どおりに動作するように、ある種のチェッカーやドライバを直感的に記述しています。
長年の経験から、エンジニアはプログラムが最初の試行でうまくいく可能性が非常に低いことを知っています。単体テストは、この考えに基づき、テスト プログラムを自己チェックし、再現可能にします。アサーションは、出力を手動で検査する代わりに使用されます。また、結果は簡単に解釈できるため(テストは合格か不合格か)、テストを何度か繰り返し実行して、変更に対するコードの耐性を高めるセーフティ ネットを確保できます。
もう少し具体的に説明してみましょう。完成したコードを CVS に初めて提出すると、まったく問題なく動作します。また、一定期間は問題なく動作し続けます。ある日、誰かがコードを変更したとします。いつか、誰かがコードを壊す。子どもはそれに気づくと思いますか?可能性は低いです。しかし、単体テストを作成する際に、毎日自動的に実行できるシステムがあります。これらは継続的インテグレーション システムと呼ばれます。エンジニア X がコードを壊した場合、そのエンジニアが修正するまで悪質なメールが送られます。エンジニア X があなたにあっても!
ソフトウェアの開発をサポートし、変更があった場合にそのソフトウェアを安全に維持することに加え、単体テストには以下のことが行われます。
- 実行可能な仕様と、コードと同期されたドキュメントを作成します。つまり、単体テストを読み取って、モジュールがサポートする動作を確認できます。
- 要件と実装を切り分けるのに役立ちます。外部から見える動作を主張するため、動作の実装方法について複数のアイデアを混ぜるのではなく、明示的にそれについて検討できます。
- テストをサポートします。モジュールの動作が破損したときに警告するセーフティ ネットがある場合は、さまざまなことを試して、設計を再構成する可能性が高くなります。
- デザインを改善する。徹底した単体テストを作成するには、多くの場合、コードをテストしやすくなります。多くの場合、テスト可能なコードは、テスト不可能なコードよりもモジュール型です。
- 高い品質を維持します。重要なシステムにおける小さなバグによって、企業は多額の損失、さらに悪いことには、ユーザーの満足度や信頼を失う可能性があります。単体テストが提供するセーフティ ネットにより、この可能性は軽減されます。また、バグを早期に発見することで、QA チームは明確なエラーの報告ではなく、より高度で難しい障害シナリオに時間を費やすことができます。
時間をかけて、Composer データベース アプリケーション用の CPPUnit を使用して単体テストを作成します。詳しくは、cppunit/examples/ ディレクトリをご覧ください。
Google の取り組み
はじめにたとえば、中世の修道士が僧院に保管されている何千もの原稿を見ているとしたら、「アリストテレスのあれはどこ?」
幸いなことに、原稿は内容ごとに整理され、それぞれの情報の検索を容易にするために特別な記号が刻印されています。このような組織がなければ、関連する原稿を見つけることは非常に困難です。
大規模なコレクションから書き込まれた情報を保存および取得するアクティビティは、情報検索(IR)と呼ばれます。この取り組みは何世紀にもわたって重要性が高まっており、特に紙や印刷機などの発明においてはなおさらです。かつては、ほとんど全員が占めるような場所でした。しかし、今では毎日何億人ものユーザーが、検索エンジンやパソコンで検索する際に情報検索に携わっています。
情報取得のスタートガイド
スース博士は 30 年間で 46 冊の児童書を執筆しています。彼の本には猫、牛、ゾウ、誰が、にこにこ、オラックスが書かれている。どの生き物がどの物語に登場したか覚えてる?ドクター・スースのどの物語に生き物がいるのかを使用できるのは、子どもの親でない限り子どもだけになります。
(COW と BEE)または CROWS
Google はこの問題の解決に、いくつかの従来の情報検索モデルを適用します。
わかりやすいアプローチはブルート フォースです。ドクター スースの 46 話をすべて手に入れ、読み始めます。書籍ごとに「COW」と「BEE」という単語が含まれている本をメモし、それと同時に CROWS という単語を含む書籍を探します。これで、コンピュータは人間よりもはるかに高速です。ドクター・スースの書籍のテキストがすべてデジタル形式(テキスト ファイルなど)で提供されている場合は、ファイルを grep するだけです。ドクター スースの書籍のような小規模なコレクションでは、この手法がうまく機能します。
しかし、さらに必要な状況も多数あります。たとえば、現在オンラインになっているすべてのデータのコレクションは、grep で処理するには大きすぎます。また、単に条件に一致するドキュメントだけではなく、関連性に基づいてランク付けすることに慣れています。
grep 以外にも、検索を行う前にコレクション内のドキュメントのインデックスを作成する方法もあります。IR のインデックスは、教科書の裏面にあるインデックスに似ています。ドクター・スースの各物語のすべての単語(または用語)のリストを作成し、「the」、「and」などの接続詞、前置詞など(ストップワードと呼ばれます)は除外されます。Google は、ユーザーが簡単に用語を見つけ、関連する記事を特定できるように、この情報を表示します。
たとえば、一番上のストーリーを各行にリストしたマトリックスなどです。列の「1」は、その列のストーリーにそのキーワードがあることを示します。
各行または各列をビットベクトルとして表示できます。ある行のビットベクトルは、どの記事にその用語が含まれているかを示します。列のビットベクトルは、ストーリーに登場する用語を示します。
元の問題に戻ると、
(COW と BEE)または CROWS
これらの項のビットベクトルをとり、最初にビット単位の AND を実行し、次に結果に対してビット単位の OR を実行します。
(100001 と 010011) または 000010 = 000011
答え: 「Brown Can Moo 様、Can You?」と「The Lorax」が表示されます。これは、「完全一致」モデルであるブール値検索モデルのイラストです。
このマトリックスを拡張して、ドクター・スースのすべてのストーリーと、ストーリーに関連するすべての用語を含めるとします。行列はかなり大きくなります。エントリのほとんどが 0 になるのは重要な点です。行列は、おそらくインデックスの最適な表現ではありません。「1」だけを保存する方法を見つける必要があります。
機能強化
この問題を解決する IR で使用される構造は、転置インデックスと呼ばれます。Google は用語の辞書を保持しており、用語ごとに、その用語が使用されているドキュメントを記録するリストを用意しています。このリストは投稿リストと呼ばれます。以下に示すように、1 リンクのリストがこの構造を表すのに適しています。
リンクリストについてよくご存じない方は、「C++ のリンクリスト」で Google 検索してみてください。その作成方法と使用方法について説明したリソースが数多くあります。この点については、別のモジュールで詳しく説明します。
記事の名前の代わりにドキュメント ID(DocIDs)を使用しています。また、クエリの処理を容易にするため、これらの DocID を並べ替えます。
クエリをどのように処理しますか?元の問題では、まず COW の投稿リストを見つけ、次に BEE の投稿リストを見つけました。その後、「統合」します。
- 両方のリストにマーカーを維持し、2 つの投稿リストを同時に検討します。
- 各ステップで、両方のポインタが指している DocID を比較します。
- 同じであれば、その DocID を結果リストに追加します。そうでない場合は、小さい方の docID を指すポインタを進めます。
転置インデックスの作成方法は次のとおりです。
- 対象となる各ドキュメントに DocID を割り当てます。
- ドキュメントごとに、関連する用語を特定します(トークン化)。
- 用語ごとに、用語、それが見つかったドキュメント ID、そのドキュメント内の頻度で構成されるレコードを作成します。複数のドキュメントに特定の用語が含まれている場合は、その用語に複数のレコードが存在することがあります。
- 期間でレコードを並べ替える。
- 用語の単一レコードを処理し、複数のドキュメントに出現する用語の複数のレコードを結合して、辞書と投稿のリストを作成します。DocID のリンクリスト(並べ替え順)を作成します。各用語には頻度も存在します。これは、ある用語のすべてのレコードにおける頻度の合計です。
プロジェクト
テストに使用できる長い平文のドキュメントをいくつか見つけます。このプロジェクトでは、上記のアルゴリズムを使用して、ドキュメントから転置インデックスを作成します。また、クエリの入力用のインターフェースと、クエリを処理するエンジンを作成する必要があります。プロジェクト パートナーはフォーラムにあります。
このプロジェクトを完了するためのプロセスの例は次のとおりです。
- まず、ドキュメント内の用語を識別するための戦略を定義します。考えられるすべてのストップワードのリストを作成し、ファイル内の単語を読み取り、用語を保存して、ストップワードを削除する関数を作成します。反復処理で用語のリストを確認する際に、リストにストップワードを追加しなければならない場合があります。
- 関数をテストする CPPUnit テストケースと、ビルドのためにすべてをまとめる makefile を作成します。特にパートナーと作業している場合は、ファイルを CVS にチェックインします。リモート エンジニアに CVS インスタンスを開く方法を検討することをおすすめします。
- 位置情報(どのファイルとファイル内のどこに用語が置かれているか)を含める処理を追加するページ番号や段落番号を定義する計算方法がある場合は、
- この追加機能をテストする CPPUnit テストケースを作成します。
- 転置インデックスを作成し、位置情報を各キーワードのレコードに格納します。
- さらにテストケースを作成します。
- ユーザーがクエリを入力できるインターフェースを設計します。
- 上記の検索アルゴリズムを使用して、転置インデックスを処理し、位置情報をユーザーに返します。
- この最後のパートのテストケースも必ず含めてください。
これまでのあらゆるプロジェクトと同様、フォーラムとチャットを使用してプロジェクト パートナーを見つけ、アイデアを共有できます。
追加機能
多くの IR システムで一般的な処理ステップは、ステミングと呼ばれます。ステミングの背景にある主な考え方は、「取得」に関する情報を検索するユーザーが、「取得」、「取得済み」、「取得中」などを含む情報を含むドキュメントにも関心を持つようになるということです。ステミングが不十分なためにシステムがエラーが発生しやすくなるため、やや注意が必要です。たとえば、「情報の取得」に関心があるユーザーには、ステミングが原因で「Information on Golden Retrievers」というタイトルのドキュメントが表示される場合があります。ステミングに便利なアルゴリズムは、Porter アルゴリズムです。