選択ソートをPerlで実装してみた

選択ソート

選択ソート(selection sort)は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す(厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後(残り)は必ず最大値になるからである)。大小が入れ替わる降順の場合も同様の手法である。


■入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2行目に、N 個の整数が空白区切りで与えられます。

■出力
出力は 2 行からなります。1行目に整列された数列を 1 行に出力してください。数列の連続する要素は1つの空白で区切って出力してください。2 行目に交換回数を出力してください。

■制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 100

Aizu Online Judge

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&input_nums;

sub input_nums {
    print "数列の長さを表す整数を入力してください。\n";
    my $input_num_length = <STDIN>;

    print "整数を空白区切りで入力してください。\n";
    my $input_lines = <STDIN>;

    chomp($input_lines);
    my @input_lines_arr = split(/ /, $input_lines);

    &selection_sort($input_num_length, @input_lines_arr);
}

sub selection_sort {
    my ($input_num_length, @input_lines_arr) = @_;
    $\="\n";
    my $flag = 0;

    for (my $i = 0; $i < $input_num_length; $i++) {
        my $minj = $i;

        for (my $j = $i; $j < $input_num_length; $j++) {
            if ($input_lines_arr[$j] < $input_lines_arr[$minj]) {
                $minj = $j;
            }
        }
        if ($input_lines_arr[$i] == $input_lines_arr[$minj]) {
            next;
        }

        my $tmp = $input_lines_arr[$i];
        $input_lines_arr[$i] = $input_lines_arr[$minj];
        $input_lines_arr[$minj] = $tmp;
        $flag++;
    }
    my @output_lines_arr = join(' ', @input_lines_arr);
    print @output_lines_arr;
    print $flag;
}


[hogefuga@localhost:sort_algorithm]$ perl selection_sort.pl
数列の長さを表す整数を入力してください。
6
整数を空白区切りで入力してください。
5 2 4 6 1 3
1 2 3 4 5 6
3

バブルソートをPerlで実装してみた

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。

全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。なおこの繰り返しは、入れ替えが起こらなくなった時点で(それ以降は何度繰り返しても変化が起こらなくなるので)中断することができる。

この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。


■入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2行目に、N 個の整数が空白区切りで与えられます。

■出力
出力は 2 行からなります。1行目に整列された数列を 1 行に出力してください。数列の連続する要素は1つの空白で区切って出力してください。2 行目に交換回数を出力してください。

■制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 100

Aizu Online Judge

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&input_nums;

sub input_nums {
    print "数列の長さを表す整数を入力してください。\n";
    my $input_num_length = <STDIN>;

    print "整数を空白区切りで入力してください。\n";
    my $input_lines = <STDIN>;

    chomp($input_lines);
    my @input_lines_arr = split(/ /, $input_lines);

    &bubble_sort($input_num_length, @input_lines_arr);
}

sub bubble_sort {
    my ($input_num_length, @input_lines_arr) = @_;
    $\="\n";
    my $flag = 0;

    for (my $i = 0; $i < $input_num_length; $i++) {
        for (my $j = $input_num_length - 1; $j > $i; $j--) {

            if ($input_lines_arr[$j - 1] > $input_lines_arr[$j]) {
                my $tmp = $input_lines_arr[$j - 1];
                $input_lines_arr[$j - 1] = $input_lines_arr[$j];
                $input_lines_arr[$j] = $tmp;
                $flag++;
            }
        }
    }
    my @output_lines_arr = join(' ', @input_lines_arr);
    print @output_lines_arr;
    print $flag;
}


[hogefuga@localhost:sort_algorithm]$ perl bubble_sort.pl
数列の長さを表す整数を入力してください。
5
整数を空白区切りで入力してください。
5 3 2 4 1
1 2 3 4 5
8


気づいたこと

$j + 1にするより$j - 1 にした方が良い。$j + 1にすると、$j + 1が$input_num_lengthに一致する場合繰り返しを終了するという条件文が必要になるので。

挿入ソートをPerlで実装してみた

挿入ソート

挿入ソート(insertion sort)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する(配列の場合、前の要素を後ろに一つずつずらす)。この操作で、2番目までのデータが整列済みとなる(ただし、さらにデータが挿入される可能性があるので確定ではない)。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。


■入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

■出力
出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は1つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。

■制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 1,000

Aizu Online Judge


use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&input_nums;

sub input_nums {
    print "数列の長さを表す整数を入力してください。\n";
    my $input_num_length = <STDIN>;

    print "整数を空白区切りで入力してください。\n";
    my $input_lines = <STDIN>;

    chomp($input_lines);
    my @input_lines_arr = split(/ /, $input_lines);

    &insertion_sort($input_num_length, @input_lines_arr);
}

sub insertion_sort {
    my ($input_num_length, @input_lines_arr) = @_;
    $\="\n";

    for (my $i = 0; $i < $input_num_length; $i++) {
        my @output_lines_arr = join(' ', @input_lines_arr);
        print @output_lines_arr;
        return if $i + 1 == $input_num_length;

        if ($input_lines_arr[$i] < $input_lines_arr[$i + 1]) {
            next;
        }

        for (my $j = 0; $j < $input_num_length; $j++) {
            if ($input_lines_arr[$j] < $input_lines_arr[$i + 1]) {
                next;
            }
            my @fixed_arr = grep $_ != $input_lines_arr[$i + 1], @input_lines_arr;
            splice(@fixed_arr, $j, 0, $input_lines_arr[$i + 1]);
            @input_lines_arr = @fixed_arr;
            last;
        }
    }
}


[hogefuga@localhost:sort_algorithm]$ perl insertion_sort.pl
数列の長さを表す整数を入力してください。
6
整数を空白区切りで入力してください。
5 2 4 6 1 3
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

アジャイル開発の種類

スクラム開発

概要

スクラム開発はアジャイル開発の代表的な手法の一つで、中でも“チームのコミュニケーションを重視した手法”である。ラグビーで両陣が、8名ずつ肩を組んで一つの集団を作り、ぶつかり合う際のフォーメーション「スクラム」が語源。その姿から集団が力を合わせることを”スクラムを組む”と表現することもある。

特徴

・プロダクトへの要望を優先順位ごとに並べかえ、その順に機能を作る。
・固定の短い期間(1~4週間程度)の単位で開発を区切り、その中で計画を立てる。
・プロジェクトの状況や進め方に問題がないか、メンバー同士で毎日確認しあう。
・作っている機能が正しいかどうか、定期的に確認の場を設ける。


用語

【スプリント】
スプリントは、1週間や2週間といった、時間枠(タイムボックス)のことである。スプリントでは、スプリント計画、デイリースクラム、スプリント実施、スプリントレビュー、スプリント振り返りなどのアクティビティがある。


【スプリント計画(スプリントプランニング)】
次のスプリントで何をやるかを決定する。プロダクトバックログを元にしてスプリントバックログを作成する。この時、スプリントバックログは、プロダクトバックログアイテムをタスク単位に細分化しても問題ない。


【デイリースクラム
デイリースクラムでは、1日の作業の開始時に開発チームが実施する活動である。ここでは、誰がどのスプリントバックログに着手するか、問題は発生していないかなどを15分で確認する。またデイリースクラムを行なわずに開発チームは常にコミュニケーションを行い、把握するという方法もある。


【スプリントレビュー】
スプリントレビューでは、スプリントの実施によって生み出されたインクリメントの検査と適応を行う。開催はスクラムチームが行う。スプリントレビューにはプロジェクトの利害関係者全員が参加し、スプリント実施が完了した直後に行う。デモを実施し、利害関係者にインクリメントを説明する。そして、次の質問をする。

利害関係者は、デモの結果を気にいっているか
今でも顧客に受け入れられるか
重要な機能が不足していないか
不必要な機能を作成していないか
コストをかけすぎていないか
これらの質問の答えが、プロダクトバックログのグルーミングの参考になり、リリースプランのインプットになる。



【スプリント振り返り(スプリントレトロスペクティブ)】
スプリントレビューでは、プロダクトについてのレビューを実施しますが、スプリント振り返りでは、スクラムチームの成長や、プロセスの改善を行うことが目的である。

今回のスプリントでうまくいったことは何か
今後も続けたいことはなにか
問題や課題になったことはなにか
改善したほうがよいことはなにか



KPT
KPTは、左上にKeep、左下にProblem、右半分にTry、最上部にテーマ、というように区分したフレームワークである。Keep は今後も続けること、Problem は問題点であること、Try は試すこと。

エクストリームプログラミング

概要

エクストリーム・プログラミング、XP(英: extreme programming)は、ケント・ベックらによって定式化され、提唱されているソフトウェア開発手法である。柔軟性の高い開発手法であるため、難易度の高い開発やビジネス上の要求が刻々と変わるような状況に向いた開発手法である。事前計画よりも柔軟性を重視する。1999年に書籍『XPエクストリーム・プログラミング入門―ソフトウェア開発の究極の手法』によって発表された。

XPは、軽量開発手法あるいはアジャイルソフトウェア開発手法と呼ばれる、同種の開発手法のなかで代表的なものである。柔軟性の高い開発手法であるが、古典的には開発が進むにつれ変更コストは大きくなると言うことを前提に開発手法が構築されているのに対して、自動テストを導入するなど様々な対策をすることにより開発が進んでも変更コストが大きくならないような工夫を持ち込むことにより、変更に対する柔軟性を実現している。この変更コストが増大しないという前提が破綻すると、この手法も破綻する。

XPは比較的少人数の開発にもっとも適用しやすく、5つの価値と19の具体的なプラクティス(実践)が定義されている。XPはドキュメントよりもソースコードを、組織的開発の歯車となることよりも、個人の責任と勇気を重んじる人間中心の開発プロセスであるとしている。

共同のプラクティス

【反復】
開発を反復から構成する(⇒反復型開発)。全体の開発期間はイテレーションと呼ぶ1〜2週間の短い期間に区切り、イテレーションごとに部分的な設計・実装・テストを行い、半完成品システムのリリースを繰り返し、徐々に完全なシステムを構築していく。またより小さな単位の単体機能の実装も、コード修正とテストの繰り返しによって進める。このことで、リスクを最小限に抑えつつ、イレギュラーな変更に対応した開発が可能になる。


【共通の用語】
用語集を作成し、チーム全員(開発者・管理者・顧客)の使用する用語とその概念の不一致を解消する。


【開けた作業空間】
会話しやすく、作業に打ち込める雰囲気を作る。顧客も含めて一箇所に集まって作業を行う。


【回顧(頻繁な振り返り)】
現在の状態を明確に把握しつつ、過去のフィードバックを迅速に反映させるよう心がけ、そのための環境、体制を構築しておく。

開発のプラクティス

テスト駆動開発
実装を行うより先に、テストを作成する。実装は、そのテストをパスすることを目標に行う。テストを先に作成することで、求める機能が明確化され、シンプルな設計が可能になる。なお、このテストは、部品単位での正確性を確認するユニットテストホワイトボックステスト)と、全体が顧客の要求を満たしているかを確認する受け入れテスト(ブラックボックステスト)の観点で作成する。テストは、自動テストであることが推奨される。なぜなら、それによって、コードの共同所有、リファクタリング、頻繁な結合が可能になるため、開発が進んでも変更コストの増大を抑制することができる。


ペアプログラミング
プログラミングは、二人一組で行う。一人がコードを書き、もう一人はそれをチェックしながら、仕様書を確認したり全体構造を考えたりするなど、ナビゲートを行う。二人は、この役割を定期的に交代しながら仕事を進める。ナビゲータのサポートにより、以下の効果が得られる。
細々とした問題の解決に要する時間が短くなる。
常にコードレビューを行うことができる
集中力が持続する。
コードの詳細を理解したメンバーが常に2人以上いることで後々のコード共有に役立つ。



リファクタリング
完成済みのコードでも、随時、改善処置を行う。この際、外部から見た動作は変更させずに、内部構造がより見通し良く優れたものになるようにする。テストが作成されていることが前提になる。


ソースコードの共同所有】
誰が作ったソースコードであっても、開発チーム全員が断りなく修正を行うことができる。ただし、全てのコードに対する責任を、全員が担う。


継続的インテグレーション
単体テストをパスするコードが完成するたび、すぐに結合テストを行い、問題点や改善点を探す。少なくとも一日に一回は、結合テストを行う。また、全体のコンパイルおよび自動テストを行うための継続的インテグレーション用のコンピュータを準備することが推奨されている。


YAGNI
You Aren't Going to Need It.(必要なことだけ行う)。先を見据えて、前払い的に機能を増やし、実装を複雑化させることは避ける[6]。むしろ無駄な機能があれば削りとり、今必要な機能だけのシンプルな実装に留めておく。これにより、後のイレギュラーな変更に対応しやすいようにする。シンプルで洗練され、安定性の高い機能・コードのまま、同時に将来的な汎用性も高めることは問題ないが、把握を難しくし、不安定化を招く機能・コードは、可能な限り削り落とす。

リーンソフトウェア開発

概要

リーン開発の手法は、トヨタなどの企業が過去数十年に渡り完成させたリーン生産プロセスから生まれたものである。リーン開発の目標は、ビジネスが競合力を保つために必要とされる複雑なソフトウェアシステムを定義し、構築し、引き渡すという取り組みに対処することである。リーン開発は、技術的なプラクティスではなく、ソフトウェア開発のプロジェクトマネジメント面を重視している点でスクラムと似ており、特にプロジェクトのコストとROIの属性を焦点にしている。

リーン開発の大きな柱になっているのが、「正しい」要件の収集である。要件はビジネスへの影響に基づいて評価し、明確で完全で検証可能な方法で定義しなければならない。不完全な要件、見つからない要件、間違った要件、検証不可能な要件、競合している要件は、要件定義プロセス時に除外されます。

このように要件を重視するため、リーンプロセスでは顧客が絶対不可欠な役割を果たす。生産の観点から見れば、リーン開発は新製品の開発のようなものと考えることができる。要件に焦点を置くことは、顧客が果たす役割と価値を具体化するのに役立つ。開発チームが対処しているビジネス価値と機能要件について顧客からコンスタントなフィードバックを得ることが、リーンアプローチの中心的要素である。

機能駆動型開発(FDD

概要

機能駆動型開発(FDD)は、5つの基本活動からなるモデル駆動型の短期反復方式の開発工程である。ソフトウェア開発プロジェクトの正確な状態報告と監視のために、各 feature についての進捗を示すマイルストーンが定義されている。最初の3つの逐次的な活動によって、全体モデルの形が決まる。その後の2つの活動は feature 毎に反復的に実施される。

【全体モデル開発】
プロジェクトは、システムの範囲とその内容についての高レベルなウォークスルー(ソフトウェア開発において、ソフトウェア成果物の品質向上を目的に、その作成者が主体となって開催するレビューのこと)から開始される。次に、部門毎の詳細なウォークスルーが、各モデリング分野ごとに行われる。各部門のサポートを受けて、複数のウォークスルーモデルが少人数で制作され、査読と議論のたたき台とされる。提案されたモデルのうちの1つまたは複数をまとめたものが、その特定の分野のモデルとして選択される。分野ごとのモデルが結合されて全体モデルとなり、全体モデルとしてその後調整が行われる。


【feature リスト構築】
初期のモデリングで収集された知識は機能(feature)のリストアップに使われる。このとき、領域を顧客が重要と考えている点ごとに分類する。この分類された各点にはそれぞれ何らかのビジネス活動が含まれ、各ビジネス活動内のステップ群に feature リストが対応する。この観点での feature とは、顧客にとっての価値を生む小規模な機能単位であり、 という形式になっている。例えば、「売り上げの合計を計算する」(Calculate the total of a sale) あるいは「ユーザーのパスワードを検査する」(Validate the password of a user) などである。完成に2週間以上かかると予想される feature は、さらに分割すべきである。


【feature 毎の計画】
feature リストが完成すると、次はその開発計画を立案する。feature をクラスに割り当て、各クラスに関して責任を持つプログラマ(オーナー)を決め、分担させる。


【feature 毎の設計】
各 feature ごとの設計パッケージを作る。オーナーは2週間で開発すべき feature 群を選択する。関連するクラスのオーナーと共同で、feature ごとの詳細なシーケンス図を作成し、全体モデルを更新する。次に、クラスとメソッドのプロローグを書き、最後に設計インスペクションを行う。


【feature 毎の構築】
feature ごとの設計インスペクションが完了したら、feature を実現するコードを書く。単体テストとコードインスペクションが完了したら、その feature はメインのビルド環境に入れられる。


【マイルストーン】
feature は小さいので、feature を1つ完成させるのは小さな作業である。ソフトウェア開発プロジェクトとしての進捗状況を監視して報告するには、それぞれの feature の進捗状況を全て把握する必要がある。そこで、FDD では feature ごとに6つのマイルストーンを定義し、それらが順次完了していく状況を監視する。最初の3つのマイルストーンはfeature 毎の設計活動のもので、残る3つはfeature 毎の構築活動のものである。進捗を把握する補助として、各マイルストーンに進捗率が設定されている。次の表にそれらマイルストーン(と進捗率)を示す。これによると、コード作成中の feature の進捗率は 44%(ドメイン・ウォークスルーが 1%、設計が 40%、設計インスペクションが 3% で、合計で 44%)である。


参考:
エクストリーム・プログラミング - Wikipedia
ユーザー機能駆動開発 - Wikipedia

システム開発手法

ウォーターフォールモデル

概要

プロジェクトによって工程の定義に差はあるが、開発プロジェクトを時系列に、「要求定義」「外部設計(概要設計)」「内部設計(詳細設計)」「開発(プログラミング)」「テスト」「運用」などの作業工程(局面、フェーズ)にトップダウンで分割する開発手法。原則として前工程が完了しないと次工程に進まない(設計中にプログラミングを開始するなどの並行作業は行わない)事で、前工程の成果物の品質を確保し、前工程への後戻り(手戻り)を最小限にする。ウォーターフォール・モデルの利点は、工程の進捗管理がしやすいことである。

歴史

1968年、NATO後援の国際会議にて、ソフトウェア開発を職人芸的な作成方法から工業製品としての作成方法に変える方法として、製品製造過程のように開発をいくつかの工程に分け、各工程の終了を意味する文書を作成することで進捗を管理し、早いうちから品質の作りこみをしようとするウォーターフォール・モデルの原形が提唱された。

ウォーターフォール・モデル」という用語は、文字通り「滝」を意味し、W. W.ロイスによって1970年に発表された論文「Managing the Development of Large Software Systems」の内容が元になったとされる。この論文において、「大規模ソフトウェア開発には、製品製造過程のようにいくつかの工程に分けたトップダウンアプローチが必要」と述べている。しかし論文には「ウォーターフォール・モデル」という記述は無く、また、前工程への後戻り(見直し)も提唱されており、元の論文の内容とは異なっている。

問題点

ウォーターフォール・モデルの問題点は、『前工程に間違いがない』ことを前提または期待していることである。古くから(現代においても)、要求を事前に詳細に定義することは困難であると言われている。要求をユーザーに徹底的に確認したにも関わらず、下流工程になって見え始めたシステムを見たユーザーから修正要望が出ることがある。この要望に応えるには、前工程に戻って進捗度を戻さざるをえなくなる。

前工程への後戻りはスケジュールの遅延の原因であると評価されるため、前工程の完了要件(要件定義局面であれば、要件定義書などの成果物の完成)を徹底して品質を高め、後戻りの発生率を可能な限り低下させるとともに、後戻りが発生する場合は変更管理によって公式に決定し、後戻りや横展開を確実にフォローすることが求められる。

プロトタイプモデル

概要

プロトタイプモデルとは、設計の早い段階から機能を制限したり簡易化したりした試作機(プロトタイプ)を作成し、トータルの開発工数を減らすための開発手法のことである。クライアント企業にとっては初期の段階から本番に近い画面イメージを確認することができるのが最大のメリットである。

歴史

1980年代前半まで主流だった開発手法が、高いところから水を流すように、工程を上流から下流へ最後まで一気に開発をすすめるウォーターフォール・モデルだった。ところがこの手法の問題点は、システム開発の終盤になって初めて発注者側で、システムがイメージ通りだったかどうかを確認できるという点である。

発注者側の要望と違うイメージの製品になってしまった場合には、それを修正するために前の工程へ後戻りしなければならず、いわゆるやり直し作業にかかる時間が増えて生産性が低くなるという欠点がある。また、最悪の場合には前工程に戻っても対処することができずに、最初からやり直しというケースもあり、この場合の損失は極めて大きくなる。

ウォーターフォール型開発のこうした問題点が明確になるにつれて、その問題点を解決するためにできたのがプロトタイプ開発モデルである。開発の早い段階で試作品(プロトタイプ)を作成し、その試作品をエンドユーザーが確認することで、ウォーターフォール型にあった「こんなはずじゃなかった」という悲劇を回避することを目的としている。

問題点

プロトタイプ・モデルでは、試作品とは言え、エンドユーザーに確認、評価してもらえるだけの機能を作りこむ必要がある。システムの機能や特性にもよりますが、完成品の全機能を試作品として開発しないと意味がない、というシステムも中にはあるだろう。その場合は、ほぼ完成品という試作品を作る必要があるので、開発コストが膨らむのは目に見えている。

逆に、エンドユーザーが確認、評価できないような、中途半端な試作品を作ったとする。その場合には、試作品に対する十分なフィードバック(エンドユーザーの確認、評価)を得ることができず、「要件漏れを防ぐ」「仕様精度の向上」といった本来の目的を達成することができない。この場合、試作品を作ったこと自体が無意味になってしまう。

スパイラルモデル

概要

スパイラルモデルとは、ユーザーからのフィードバックや要望に対して具体的に対応しながら、精査や改善を施し、徐々に完成させていく、プロセスモデルの手法のことである。作業工程を分割し、分割した工程を順序だてて実施するウォーターフォールモデルの一つ一つの段階を、エンドユーザーとの認識のズレを補正するプロトタイプの作成などを含め、成長モデル的に進めることで、らせん状(スパイラル)に昇華するような開発工程をたどる。

トップダウン設計は、段階的に詳細にしていく設計技法である。最初にシステム全体を定式化し、その時点では個々の詳細には立ち入らない。その後、システムの個々の部分の設計を段階的に詳細化していく。最終段階では、実装に移せるまで詳細化する。内部構造に立ち入らずに設計を行っている段階では、各部分をブラックボックスとして扱う。

ボトムアップ設計では、最初にシステムを構成する個々の部品を細部まで設計する。そして部品群を組み合わせてより大きな部分を作っていき、最終的にシステム全体が構成される。

問題点

フィードバック毎に様々な問題が浮上した場合、何度も何度もシステムを開発しなければならなくなり、開発に時間がかかる。また、初期の想定よりシステムの仕様が肥大化し、コストがかかってしまう可能性がある。また、顧客にとっては一度金銭的な契約が締結されたら何度でも無料で修正できる手法だと考え、依頼する用件をまとめない傾向にある。

アジャイル開発

概要

アジャイルAgile)とは、直訳すると「素早い」「機敏な」「頭の回転が速い」という意味である。アジャイル開発は、システムやソフトウェア開発におけるプロジェクト開発手法のひとつで、大きな単位でシステムを区切ることなく、小単位で実装とテストを繰り返して開発を進めていく。従来の開発手法に比べて開発期間が短縮されるため、アジャイル(素早い)と呼ばれている。

歴史

近年のアジャイルソフトウェア開発の定義は、1990年代半ばに、「重量ソフトウェア開発手法」への反対運動の一部から発展して形成されてきた。 重量開発手法の特徴は、ウォーターフォール開発モデルを適用した場合に多くみられる、厳格な規律と統制、管理不足などである。 ウォーターフォールモデルのこのような適用に端を発する重量開発手法は、官僚的で、もたもたしていて (slow) 、衰退的 (demeaning) で、そのためソフトウェア技術者が効果的に作業を進めるという観点と矛盾していた。

2001年に、当時軽量のソフトウェア開発を提唱していた17名の技術者やプログラマーが米国ユタ州に集まり、開発手法の重要な部分について統合することを議論した。それをまとめたものが「アジャイルソフトウェア開発宣言」である。アジャイルソフトウェア開発宣言は、ソフトウェア開発とそれに基づく12の原則を定義しており、2017年現在もアジャイル開発の公式文書として広く知られている。

アジャイル開発の流れ

アジャイル開発では、ソフトウェアの計画段階で厳密な仕様を決めずに、だいたいの仕様と要求だけを決める。これは「開発途中に仕様や設計の変更があることは当たり前」という前提があるからである。おおまかな計画のみでは、その後の実装フェーズで問題が起こりそうだが、仕様が決まっていないと途中で変更があっても臨機応変に対応できるため、顧客のニーズに最大限応えることが可能である。

だいたいの仕様と要求を決めたら、イテレーション(iteration)と呼ばれるサイクルを繰り返して開発を進める。イテレーションとは「反復」という意味で、小さな単位に分けられた開発を「計画」→「設計」→「実装」→「テスト」と行いながら、機能のリリースを繰り返す。イテレーションは1週間~2週間ごとが一般的で、イテレーションごとに毎回機能をリリースする。「イテレーション1」「イテレーション2」「イテレーション3」…と繰り返しながら、細かく開発を進めていく。

アジャイル開発は、開発の途中で仕様の変更や追加が予想されるプロジェクトに向いている手法である。例えば、モバイル分野などの日進月歩で技術や仕組みが進化している産業では、開発の途中で仕様の変更や追加が容易に予想できる。アジャイル開発では、リリース計画段階で厳密な仕様を決定しないため、途中変更の多いプロジェクトと相性が良い。

一方、数十年手作業で実行していた工程をシステム化する、20年稼働していたシステムをリプレースするといった場合は、すでに作るべき機能が明確に決まっている。そのため、このようなシステムの場合にはアジャイル開発よりも、ウォーターフォール開発が向いているといえる。


参考:ウォーターフォール・モデル - Wikipedia

分岐予測

分岐予測

分岐予測とは、プログラム実行の流れの中で条件分岐命令が分岐するかしないかを予測することにより、命令パイプラインの効果を可能な限り維持し、性能を高めるためのCPU内の機能である。

条件分岐は、分岐せず (not taken) に分岐命令直後に続く命令の流れをそのまま実行し続ける場合と、分岐して (taken) プログラム内の異なる位置に分岐してそこから命令実行を続行する場合がある。

条件分岐命令が分岐するかしないかは、分岐条件を計算し、条件分岐命令が実行ステージを過ぎるまでわからない。

分岐予測を行わない場合、条件分岐命令が実行ステージを過ぎるまで次にフェッチすべき命令が定まらず、プロセッサはパイプラインのフェッチステージで待つことになる。分岐予測は条件分岐命令が分岐しそうかしそうでないかを推測することで、この無駄な時間を排除しようと試みる。

分岐予測の結果に基づいて次に実行されそうな命令をフェッチし投機的に実行する。後で予測が間違っていたことが判明したら、投機的に実行した、あるいは実行途中だった命令は捨てられ、パイプラインは改めて正しい分岐で処理を再開する。その際、遅延が生じる。

実際のプログラムの大半では、ループ処理や例外処理など各分岐先への分岐比率は偏りが大きいため、分岐予測によるメリットが分岐予測失敗によるデメリットを上回ることが多い。つまり分岐予測の的中率は、使用するアプリケーションと、分岐予測に採用した技法次第である。

命令パイプライン

命令パイプラインは、コンピュータなどのデジタル電子機器で命令スループット(単位時間当たりに実行できる命令数)を向上させる設計技法の1つで、命令レベルの並列性(プログラムの中で並行して実行できる処理がいくつあるか)を高める1技法である。

命令パイプラインのあるプロセッサは、命令の処理を独立して実行できる工程(ステージ)に分割する。各工程は、前の工程の出力を自身の入力とし、自身の出力を次の工程の入力とするように相互接続されている。このような構成で各工程を並列化し、全体としての処理時間を大幅に削減する。

プロセッサ

プロセッサ (processor) は、コンピュータシステムの中で、ソフトウェアプログラムに記述された命令セット(データの転送、計算、加工、制御、管理など)を実行する(=プロセス)ためのハードウェアであり、演算装置、命令や情報を格納するレジスタ、周辺回路などから構成される。

フェッチ

フェッチとは、CPUの動作のうち、メモリから命令コード(インストラクション)を取り出してくる動作のことである。フェッチはCPUの命令実行において最初に行われる。

フェッチ動作によって取り出されたインストラクションはCPU内部のレジスタに転送され、デコードを経た上で、実行される。ちなみに、「フェッチ」とは英語で「取り出す」といった意味である。

アドネットワーク、アドエクスチェンジ、DSP、SSPの仕組み

アドネットワーク

アドネットワークとは

2008年頃から出てきた、広告媒体のWebサイトを多数集めて「広告配信ネットワーク」を形成し、多数のWebサイト上で広告を配信する広告配信手法である。多くのWebサイトを媒体とすることで、全体では多くのトラフィック量を確保することが可能で、広告主にとって大きなメリットがある。媒体側から見ても、アドネットワーク事業者に受注、掲載の手続き等を任せることができるので、両者にとって大きなメリットがある。

アドネットワークという「広告配信ネットワーク」に入札という形態で広告配信することで、広告主は多数のWebサイトに一括で広告を配信することが可能になった。ただ、いいことばかりだけでなく、ブランディングとしてマイナスなサイトに掲載されたり、自社のターゲットとは全く関係のないサイトにも掲載される可能性もあり、特定のサイトに広告を掲載しないようにする仕組みも取り入れられた。

アドネットワークがなかった時代に広告主が抱えていた課題

1.1つ1つのWebサイトに広告掲載をお願いしないといけない
2.良い広告媒体(Webサイト)を自分で探さないといけない
3.課金形態がバラバラで、媒体の選定が難しい
4.媒体から提供されるデータもそれぞれ違い、媒体間の比較が難しい
5.媒体から提供されるデータの信憑性

メディア側も広告主からクリエイティブを受け取ると、Webページにベタ貼りするような運用が多かったので、それなりの工数がかかっていた。自社でアドサーバー保有する大手のメディアは、広告在庫の管理が柔軟に行えるが、それでも、「広告枠を販売するための営業コスト」や「在庫リスク」の課題があった。

トラフィック

トラフィックとは、通信回線上で一定時間内に転送されるデータ量のことである。通信回線の利用状況を調査する目安となる。たとえば、「トラフィックが増大した」といった場合は、通信回線を利用するデータ量が増えた状態を指す。

アドネットワークの仕組み

■広告主にとってのメリット
アドネットワークに入札するだけで、ネットワーク加盟サイトに広告配信できる
インプレッション、クリック、CTR、CV、CVRなど効果測定データを入手できる
効果測定データは第三者(アドネットワーク事業者)が集計したものなので信憑性がある
ネットワークに配信することで、大規模な広告配信が可能
課金形態が統一(クリック課金型、インプレッション課金型)
サイトのジャンルを絞ることで広告とある程度関連性のあるサイトに配信できる
リターゲティング配信、時間指定配信など、効果を上げるためのメニューがある



■Webサイト(媒体)にとってのメリット
ネットワークに加盟することで中小サイトでも顧客を得ることができる
タグを自サイトに貼り付けるだけなので、販売の手間がかからない
クリック数などは全てアドネットワーク事業者(アドサーバー)が計測する
1つの広告枠に対して複数の広告が掲載できる → 売れ残りの可能性が低くなる


ターゲティング配信とノンターゲティング配信

配信先を指定せず全媒体へ配信する「ノンターゲティング配信」と広告主やアドネットワークの保有情報に基づき配信する「ターゲティング配信」がある。ターゲティング配信の中でも「広告主の保有情報」を使ったターゲティングと「アドネットワークの保有情報」を使ったターゲティングの2種類のターゲティングがある。

f:id:wanwan_bowbow_ilovecat:20181015213842p:plain

リターゲティング

アドネットワークを使った広告では、多種多様なジャンルの広告や広告媒体が混在しているため、広告配信効果を最適化する技術として、Cookieのデータをもとにユーザーの傾向を分析する行動ターゲティング広告(BTA)が導入されているケースがほとんどである。

その中でも、最も有名なターゲティングが「リターゲティング」である。これは、1度自社のWebサイトに訪問したユーザーに対して広告を配信する仕組みである。1度Webサイトに訪問したユーザーは、何かしらの経路でそのサイトに興味を持ったユーザーだ。このユーザーに対して広告を配信するということは、興味関心レベルの高いユーザーにアプローチしていることになるため、有効なターゲティング手法だと言える。

f:id:wanwan_bowbow_ilovecat:20181015214301p:plain

アドサーバ

アドサーバーとは、ホームページに 広告を配信するためのサーバーのことである。 広告配信事業者が独自の アドサーバー保有し、 コンテンツ提供者はその アドサーバーへのリンクという形で 広告を展開する。アドサーバーには、入稿・配信・枠管理・効果測定・販売・データマネジメントなど様々な機能がある。単に 広告を配信するだけでなく 広告の インプレッション数やクリック回数などの情報を収集・記録しており、成果の分析や配信の調整が容易に行えるようになっている。

アドエクスチェンジ

アドエクスチェンジとは

アドネットワークが登場してから約2年後、2010年頃に「アドエクスチェンジ」という広告取引市場が登場しました。アドエクスチェンジは広告枠をインプレッションベースで取引する市場であり、需要(広告主)と供給(メディア)のバランスからインプレッションごとに広告枠の価値を評価して価格を決定する。

広告主から見ると、アドネットワークでは「クリック課金型」「インプレッション課金型」など、ネットワークにより課金形態が異なることも多いが、アドエクスチェンジという広告取引市場によって、“入札方式のCPM課金型(広告枠単位)“で仕様が統一された。

リアルタイム入札(RTB)

アドエクスチェンジのうち、広告枠のインプレッションが発生するたびに競争入札を開始し、最も高い金額をつけた購入者の広告を表示するといった方式が「リアルタイム入札(RTB)」と呼ばれる。1番高い金額と言っても、実際はその価格で落札するのではなく、多くは、2位の入札額+1円が落札額となる「セカンドプライスビッディング」と呼ばれる方式がとられる。これは落札額が無暗に高くならないようにするためであり、リスティング広告など入札型の広告ではよく利用される仕組みである。

セカンドプライスビッディングにおいて、フロアプライス(最低入札額)以上での入札が1件だった場合、落札価格はフロアプライス+1円になる。メディアはフロアプライスと呼ばれる最低入札額を設定でき、これに満たない入札額の広告を配信しないことができる。この仕組みにより、低い価格しかつかなかった広告枠(インベントリ)を純広告などの他の広告枠として利用することが可能になる。

アドエクスチェンジでは、ネットワーク単位やメディア単位ではなく、広告枠単位で価格が決まる。

オーディエンスデータ

オーディエンスデータとは、ユーザーのWeb上の行動履歴から“その人(Cookie)がどんな人なのか?”を推測したパーソナルデータのことである。データエクスチェンジャーと呼ばれるデータエクスチェンジを行う事業者が、複数のポータルサイトと提携し、ユーザーのセグメンテーションを行い、オーディエンスデータ(セグメント情報)として販売する。実際のユーザーのWebサイト訪問履歴が公開される訳ではない。

オーディエンスデータを提供しているポータルサイトなどが、自社のWebページの訪問者Cookieリストをデータエクスチェンジャーに販売する。データエクスチェンジャーは、購入したオーディエンスデータのセグメンテーションを行い、そのセグメントデータを広告のターゲティング利用を目的として、アドエクスチェンジやアドネットワークに提供(広告配信側に販売)するという流れになる。

これまでは、広告とメディアの親和性など「枠」でのターゲティングがメインだったが、オーディエンスデータを利用することにより、ユーザーの行動履歴の特徴から「人」をターゲティングして広告配信することが可能になった。このオーディエンスデータを用いた広告ターゲティングのことを「オーディエンスターゲティング」と呼ぶ。

DSP/SSP

DSPの概要

オーディエンスターゲティングが登場したちょうど同じ時期、複数のアドエクスチェンジやネットワークを一元管理する広告配信のプラットフォーム「DSP(Demand-Side Platform)」、広告収益の最大化を目的とした媒体側のプラットフォーム「SSP(Supply-Side Platform)」が登場した。これを利用すると、広告主は、複数のアドエクスチェンジ、複数のアドネットワークに一括して広告配信が行える。

DSPは、広告主や広告代理店のためのシステムで、広告インベントリの買い付け、広告配信、掲載面、クリエイティブの分析、入札単価の調整、オーディエンスターゲティング等、広告主のためにあらゆる最適化をシステマティックに行い、複数のSSPとRTB接続することで、広告インベントリを必要とした時にリアルタイムで入札に参加する。

SSPの概要

DSPとは逆に、こちらは媒体側の収益を最大化させるためのプラットフォーム(Supply-Side Platform)である。インプレッション毎にeCPMを算出し、1番高額と判断された広告が配信される仕組みある。基本的には、広告枠に対して最も高値を提示した広告が表示されるが、それ以外の落札決定要因として、入札価格以外にビットレスポンスなどがある。これは、RTBの仕組み上、表示する広告を瞬時に決定する必要があるためである。

入札 ~ 広告掲載までの流れ

ユーザーがWebサイトに訪問し、広告枠が存在するWebページが表示されたら、まずSSPが広告リクエストを受け、DSPにビッディングをリクエストする。各DSPDSP内でオークションを行い、DSPごとに1つのクリエイティブが決まる。その結果をSSPに返し、SSPは「各DSPで勝利したクリエイティブ同士」でオークションを行い、最終的に表示するクリエイティブ(DSP)が決まり、その結果(勝者DSP)をリクエスト元に伝える。

必ずしも入札額が高い広告が選ばれるわけではない。例えば、ユーザーがWebページに訪問して広告が表示されるまでの時間は0.1秒程度である。この時間内でレスポンスをしないといけないので、DSPのビットレスポンスの速さなども関係し、CVRの高さも影響する場合がある。

フロアプライス(最低入札額)を設定していることが多く、この額以上の入札でないと広告が表示されない。セカンドプライスビッディングでフロアプライス以上の入札が1つの場合は、フロアプライス+1円が落札額となる。リクエスト元はSSPから勝者DSPのタグを受け取り、勝者DSPに広告リクエストする。DSPはそのリクエストに応じて、広告クリエイティブをリクエスト元に配信する(具体的には、クリエイティブを呼び出すためのHTMLコード)。


参考:アドテクの仕組みと成功事例まとめ|デジタルマーケティングラボ