アルゴリズム - やさしいデスマーチ

アルゴリズム(algorithm)とはある目的を実現する為の一連の手順の事です。

アルゴリズム (algorithm) は、なんらかの問題を解くための手順のことである。算法（さんぽう）と訳されることもある。
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

例えば、「ある集合の中から特定の条件で１つの要素を取り出す事」が目的です。
この目的を実現する方法は１つとは限らず、一般的には幾つもの手順が考えられます。
この手順こそがアルゴリズムであり、アルゴリズムには間違いはありますが唯一の正解はありません。

古典的アルゴリズム

アルゴリズムには古典的アルゴリズムとも言える定番のアルゴリズムが多数あります。
例えばある集合から特定の条件で１つの要素を抽出するアルゴリズムは「探索（検索: Search）」と呼ばれ、線形検索・２分検索などの有名なアルゴリズムがあります。
これらの定番のアルゴリズムを学ぶことはプログラミングの基礎力を付けるのには最適です。

アルゴリズムには唯一の正解はないと書きましたが、優れたアルゴリズムと劣ったアルゴリズムは存在します。
間違ったアルゴリズムは論外ですが、良いアルゴリズムは次のような点で相対的に優れていると言えます。
1.効率（実行速度・メモリ消費）が良い
2.信頼性が高い
3.拡張・応用が効く
4.解りやすい
当然ならが同じ要件（目的）であっても性質の異なる２つ以上の優れたアルゴリズムは存在します。
非常に効率は良く信頼性も高いのですが特定の用途にしか使えず、理解するのも難しいアルゴリズムもあるでしょう。
逆に基本的で解りやすく拡張性も信頼性も高いのですが効率は悪いアルゴリズムもあるでしょう。
全てにおいて完璧なアルゴリズムが存在する場合もありますが、どこかを重視すると他の性能は軽視せざるを得ない場合がほとんどです。

フローチャート（流れ図）

アルゴリズム関係の書籍やWebサイトの記事を見ると必ずといってアルゴリズムとフローチャートはセットで論じられます。
かつてフローチャートは処理の流れを整理する為には非常に便利な記法でしたが、今日ではフローチャートを用いることはありません。
Javaを含めた高級言語では処理の流れはソースを見ただけで解るように記述する事が重要です。

データ集合

この章で扱うアルゴリズムは主に検索（Search）とソート（Sort）です。
検索（Search）は、あるデータ集合に対してなんらかの条件で適合するデータを探し出す事です。
ソート（Sort）は、あるデータ集合の各データをなんらかの大小関係で整列させる事です。
どちらのアルゴリズムでも、目的のデータを定義するところから始めましょう。

データ

扱うデータは具体的なものである方がイメージがしやすい為、データクラスとしてBookクラスを用意します。
Bookクラスは本のタイトルと価格をインスタンス変数に持つ簡単なクラスです。

package example06;

public class Book
{
    // タイトル
    private String title;
    // 価格
    private int price;
    // コンストラクタ
    public Book(){}
    // コンストラクタ
    public Book(String title, int price)
    {
        this.title = title;
        this.price = price;
    }
    public int getPrice() { return price; }
    public void setPrice(int value) { price = value; }
    public String getTitle() { return title; }
    public void setTitle(String value) { title = value; }
}

Object#toString()

データクラスは用意できたので、main()メソッドを持つクラスを作って使ってみましょう。
以下のコードではBookクラスのインスタンスを作成して標準出力に出力しています。

    Book book = new Book("Java入門", 1980);
    System.out.println(book);

このコードを実行すると、次のような文字が出力されるでしょう（環境によって数値は異なります）。
example06.Book@107077e
example06.Bookはクラス名という事は解りますが、107077eの意味はよく解りません。
同じ環境であれば何度実行しても同じ値が出力される事・別のインスタンスを生成すると異なる値が出力される事から、なんらかの識別記号である事は予想できます。

System.out.println(Obect obj)では、ObjectクラスのtoString()メソッドを使って文字列を生成し、標準出力していました。
BookクラスはObjectのサブクラスでありtoString()をオーバーライドしていませんからObjectクラスに実装されたtoString()メソッドが実行されます。
そのtoString()メソッドのJavaDocを参照すると次のように記述してあります。

オブジェクトの文字列表現を返します。通常、toString メソッドはこのオブジェクトを「テキストで表現する」文字列を返します。この結果は、人間が読める簡潔で有益な情報であるべきです。すべてのサブクラスで、このメソッドをオーバーライドすることをお勧めします。
Object クラスの toString メソッドは、オブジェクトの派生元のクラス名、アットマーク (@)、およびオブジェクトのハッシュコードの符号なし 16 進表現から構成される文字列を返します。つまり、このメソッドは次の値と等しい文字列を返します。
getClass().getName() + '@' + Integer.toHexString(hashCode())
http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/lang/Object.html#toString()

後半に現れるハッシュコードというものはよく解りませんが、前段を読むとオーバーライドが推奨されており、人間が読める簡潔で有益な情報であるべきと記述されています。
具体的にBookクラスでこのtoString()メソッドをオーバーライドしてみましょう。

    public String toString()
    {
        StringBuffer buf = new StringBuffer();
        buf.append(title);
        buf.append("[");
        buf.append(price);
        buf.append("円]");
        return buf.toString();
    }

文字列を組み立てる場合はStringBufferを使うことを思い出してください。

再度、実行してみると次のように出力されます。
Java入門[1980円]
これで人間が読める簡潔で有益な情報になったかと思います。

Object#equals()

集合（Set）は順序を持たず重複を許さないデータの集まりです。
整数の集合であれば、{1, 2, 3, 4, 5}と言うように異なる整数（データ）で構成されるでしょう。
Bookクラスの場合も同様に、異なるBook（インスタンス）で構成される集まりになります。

それでは「データが等しい（異なる）」とはいったいどのような事でしょうか？
整数であれば、「等しいデータ（整数）」は同じ整数でしかないでしょう。
文字列であれば、「等しいデータ（文字列）」は全く同じ文字列は確実に含まれるかもしれませんが、それだけと考えるのは早計です。
例えば、「Hello」と「hello」は全く同じ文字列ではありませんが、言語（単語）としては等しいとも言えます。
さらに「Hello」と「こんにちは」と「Guten Tag」と「Bonjour」は文字列としても言語としても異なるかもしれませんが、言葉としては等しいとも言えます。

このようにデータが等しい事を定義するにはなにをもってデータが等しいかを定義しなくてはなりません。
Bookクラスではインスタンス変数としてタイトルと価格を保持しています。
このどちらも等しいのであれば、当然ながら同じBookと考えることができます。
ですが、同じタイトルの本が２つ以上ないという前提とすれば、タイトルが等しい事で同一とみなしても問題ないでしょう。
ここでは簡単のため、Bookクラスが等しいことを「タイトルが文字列として等しい」と定義します。

ところで、Stringクラスを学習したときに、文字列の比較にはObjectクラスのequals()メソッドを使用すると学びました。
toString()と同じようにBookクラスでequals()メソッドをオーバーライドすることでインスタンス同士が等しいことを定義します。

    public boolean equals(Object obj) {
        Book book = (Book) obj;
        if(title.equals(book.title) == false)
        {
            return false;
        }
        return true;
    }

equals()メソッドの引数はObject型である為、全く同じ型でメソッドを定義します。
そのため、Bookとして比較する為にはキャストを行わなくてはなりません。
キャストを行えばBook型として扱えるので、お互いのタイトルを比較できます。
titleはprivate変数ですが、別インスタンスでも同一クラスである事には変わらないので、book.titleという記述が可能です。

それではequalsメソッドに問題がないかを確認してみましょう。

    Book book1 = new Book("Java入門", 1980);
    Book book2 = new Book("Java入門", 1980);
    Book book3 = new Book("Java入門(2)", 1980);
    
    System.out.println(book1.equals(book1));
    System.out.println(book1.equals(book2));
    System.out.println(book1.equals(book3));
    System.out.println(book2.equals(book1));
    System.out.println(book2.equals(book2));
    System.out.println(book2.equals(book3));
    System.out.println(book3.equals(book1));
    System.out.println(book3.equals(book2));
    System.out.println(book3.equals(book3));

期待通りになりましたか？
尚、このequals()メソッドは厳密には様々な問題を内包していますが、それはこの章の最後に解説するとしましょう。