Java データ構造とアルゴリズム基礎講座

作者: 長尾和彦
出版社/メーカー: 技術評論社
発売日: 2008/12/26
メディア: 大型本
購入: 4人クリック: 164回
この商品を含むブログ (13件) を見る

えー、結論から言うと、正直微妙。でもまぁ、安いし薄いし、こんなもんかなぁ、とは思う。
ただし、シェルソートの計算量について調べるきっかけを作ってくれたことには超感謝。
あー、以下、目についた悪い点を指摘しているので*1、実際よりも悪い本に見えてしまうことは必至。期待を大きく下回っていたのは確かだけど、「これはひどい本」てわけじゃないので注意してくだしあ。

前書き

本を持っているだけで英語が使えるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。
Java データ構造とアルゴリズム基礎講座はじめに (P.4)

とあって、これには激しく同意。英語だけじゃなくて、アルゴリズムとデータ構造にも直接当てはまることだしね。
でも・・・でも、この本自体が「どんなシチュエーションで使うか」の説明が中途半端。

UML はフローチャートじゃないよ！

問題の定義・分析を行うための図的表現である流れ図 = フローチャート (flow chart) には、複数のものが提案されています。
本書では、JIS 規格として定められている情報処理用流れ図 (JIS 流れ図) と構造化プログラミングに向く PAD 図について紹介します^*4。

*4 最近ではオブジェクト指向プログラミング向けの設計のために UML (Unifiled Modeling Language) が用いられることが多くなりました。本書の対象外になりますので、本書では触れません。
Java データ構造とアルゴリズム基礎講座 1.1.3 アルゴリズムの構造とフローチャート (P.16)

うーん、これだと UML もフローチャートだと読めてしまうんだけど・・・
それに、フローチャートで問題を定義するってのにも違和感が。フローチャート書いた時点で定義はおろか、問題解決の手段 (つまりアルゴリズム) まで出来上がってるんじゃないの？
分析って言葉も、問題領域の分析という意味で使われることが多いから微妙。フローチャートはあくまで「プログラムの処理の流れを分析」するためのツールだと思う。

無限ループ

一見正しく動作しますが、無限ループに陥る場合^*6 があります。
import java.util.Scanner;

public class InfiniteLoop {
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("1+2+...+n-1 の計算");
        System.out.print("  nの値 : ");
        int n = stdIn.nextInt();
        int sum=0;
        for (int i=1 ; i != n ; i++){
            sum+=i;
        }
        System.out.println("1+2+...+n-1 は"+sum+"です");
    }
}
*6 ループのカウンタ変数 i は 1 から大きくなっていきますが、ループの継続条件が i != n となっているため、n < 1 の場合、停止することが出来ません。
Java データ構造とアルゴリズム基礎講座 1.1.4 アルゴリズムの停止性 (P.18-19)

えー、本当にこれ実行してみたの？このプログラムはバグは含んでるけど、無限ループにはならないよ。
何でかって、int は 32 bit だから。だからこのプログラムに n < 1 なものを渡しても、int の限界を突っ切って -2147483648 になり、それ以降もカウントアップは続いて、結果 i == n になる。

例えばこれが long 型だったりしたら「実質無限ループ」とみなしてもいいと思うけど、int じゃなぁ・・・

再帰処理自体は、いつか再帰処理を行わない条件 (終了条件) にたどり着かないといけません。そうでなければ、無限ループに陥ってしまいます。
Java データ構造とアルゴリズム基礎講座 2.3.2 再帰的定義 (P.42)

再帰呼び出しによるスタックオーバーフローも単純なものだと無限ループと呼ぶのはちょっと抵抗がある。
無限ループを名乗るには、これくらいしないと。

public class Workout {
    public static void main(String[] args) {
        workHard();
        System.out.println("It's nap time.");
    }
    
    private static void workHard() {
        try {
            workHard();
        } finally {
            workHard();
        }
    }
}

Java Puzzlers 罠、落とし穴、コーナーケースパズル 45 : 疲れ果てたワークアウト (Exhausting Workout) (P.101)

まぁ、ここではプログラムが示されてないからこっちは言いがかりかもしれないけど。
あと、末尾最適化がかかってループに変換された結果スタックオーバーフローがおきなくなって、無限ループとか。

名前の付け方・フォーマット

なんか、名前の付け方やフォーマットに一貫性がない。例えば、

public class IntPerm {
    int mData[];
    // 略
    public void Perm(){ ... }
    private void _perm(int i){ ... }
    private void swap(int i, int j){ ... }
    
    /**
     * 解の評価
     * オーバーライドして実際の処理をさせる。
     */
    public void eval(){ ... }
}

Java データ構造とアルゴリズム基礎講座 2.1.1 組み合わせの作り方 (P.33)

とか、

public class JobAssign extends IntPerm{
    // コストテーブル[Job][Man]
    int constTable[][]={ ... };
    // 割り当ての記録
    int assign[];
    int min=0;
    public JobAssign(int[] data){...}
    /* 順列の各候補に対する評価処理
     * オーバーライドによる
     */
    public void eval(){ ... }
    /**
     * 最適解の出力
     */
    public void showAnswer()
    {
        ...
    }
}

Java データ構造とアルゴリズム基礎講座 2.1.1 組み合わせの作り方 (P.35-36)

public class CoinsGreedy {
    int Coins[] = ...;
    int Nums[];
    public CoinsGreedy(){ ... }
    
    public int checkCoins(int yen){ ... }
}

Java データ構造とアルゴリズム基礎講座 2.2 欲張り法 (P.40)

とか。がっちがちに縛る必要はないと思うけど、ここまでバラバラだと見ててイラつく。
最初の例ではフィールドにはプレフィックス m つけて、配列の括弧は名前の後ろに付けるのか、と思いきや、JobAssign のコンストラクタでは型に付いてるとか、public メソッドは大文字から始めるのか、と思いきや、eval は小文字からはじめてるし、メソッドの波括弧は改行せずに記述するのかな、と思いきや showAnswer ではそうじゃないし・・・
あと変数名の付け方もちょっと微妙だし・・・
もっと言うと、二項演算子の演算子とオペランドの間の空白にも一貫性がない・・・

継承の使い方については、アルゴリズムとデータ構造の本なので、誇らない限り深くは指摘しない。

分割方法

プログラムを作成するときは、処理の流れに従って機能単位に分割することが好ましいといわれます。処理の流れを直感的に理解できることからもおわかりでしょう。
Java データ構造とアルゴリズム基礎講座 2.3.1 機能的な分割の方法 (P.41)

それはプログラムという大きなくくりじゃなくて、まさに「処理をプログラムに落とし込むとき」の話。
プログラムを機能単位で分割するとか、オブジェクト全盛期にそれはないと思われ (現代魔法楽しみですね！(どうでもいい。

機能分解には、大きな落とし穴があります。つまり、分解した機能を適切な順序で呼び出す「メイン」プログラムが必要となるのです。
・・・
メインプログラムには、すべてを正しく動作させる、すなわち機能の組み合わせとその呼出し順序を正しく制御するという、あまりにも大きな責任が課せられることになるのです。
デザインパターンとともに学ぶオブジェクト指向のこころ (P.4)

オブジェクト指向プログラミング

いろいろなプログラムを作成していると、大体似ているんだけれど、少し違った機能が必要になることがよくあります。〜略〜
クラスの概念自体が、データ構造とそれに伴う操作関数 (メソッド) になっていますので、データと処理を簡潔に扱えるようになっています。さらに、クラスの中で必要なメソッドを追加したり、上書き (オーバーライド) することで、独自のクラスを最小限の作業で実現できます。
本章で見た仕事割り当て問題を解くクラス JobAssign (35 ページのリスト 2-2) では、順列生成クラス IntPerm を拡張する形で実現していました。このようなプログラムができるのもオブジェクト指向プログラミングの実力といえます。
Java データ構造とアルゴリズム基礎講座 COLUMN オブジェクト指向プログラミング(P.51)

このようなプログラムが書けてしまうのもオブジェクト指向プログラミングの弱点ですよね・・・
差分プログラミングとかなくなってしまえばいいのに (言いすぎ。

大体似てるけど少し違う・・・を安直に継承で解決してしまうのは愚の骨頂なのでやめましょう。
なんかもう色々とオブジェクト指向の原則をぶち破ることになります。
そしてそれがオブジェクト指向プログラミングの実力とか言うのもやめましょう。
原則破ってんだからどっちかって言うと弱点です。ダメダメです。

配列

配列はどんなプログラム言語でも利用できるデータ型であり、基本中の基本といえます。
Java データ構造とアルゴリズム基礎講座配列 (P.53)

ただし手続き型言語に限る。
すみませんすみません、どうみても揚げ足取りですすみません。

まぁでも、リストが基本中の基本である言語は少なからずあるし・・・
配列やリストが利用できない言語だってあるし・・・

NULL

文字列やポインタにおける NULL (ヌル) も番兵の一種です。
Java データ構造とアルゴリズム基礎講座 3.1.3 データの終端の表現 (P.56)

Java しか出てこない本でこれはアリなのか？
それに、ヌル文字とヌルポインタは別物だから、書き方もマズイ。

プログラムもちょっと微妙。

final static int SENTINEL = -1;
int size(){
    int i=0;
    for(i=0;i<data.length;i++){
        if(data[i]==SENTINEL)
            break;
    }
    return i;
}

Java データ構造とアルゴリズム基礎講座 3.1.3 データの終端の表現 (P.57)

こっちの方がよくね？スコープ狭くなるし、短くなるし。

final static int SENTINEL = -1;
int size() {
    for (int i = 0; i < data.length; i++) {
        if (data[i] == SENTINEL)
            return i;
    }
    return data.length;
}

れいがい！

public class IntStack{
    int data[];  // データ保存用の配列
    int top;     // データの個数、次にPUSHする場所を示す
    private int max;   // データの最大個数の制限
    private static int LimitSize = 100;
}

Java データ構造とアルゴリズム基礎講座 4.1.1 スタックの実装 (P.68)

private の選定方法とか、命名規約とか、LimitSize は普通 final とか、色々言いたいことはあるけどそこはぐっとこらえる。

/**
 * コンストラクタ
 * @param size
 */
public IntStack(){
    this(LmitSize);
}
public IntStack(int size){
    top = 0;
    max = size;
    try {
        data = new int[max];
    } catch (OutOfMemoryError e){
        max = 0;
    }
}

Java データ構造とアルゴリズム基礎講座 4.1.1 スタックの実装 (P.69)

ドキュメンテーションコメントおかしくないか？ってのもこらえる。
で、コンストラクタだけど、OutOfMemoryError を握りつぶしてらっしゃる。これは・・・いいのか？
ここまで無理して復旧しなくてもいいと思うけどなぁ・・・

public int push(int x) throws RuntimeException{
    if (top >= max)
        throw new RuntimeException();
    return data[top++] = x;
}
Java データ構造とアルゴリズム基礎講座 4.1.1 スタックの実装 (P.70)

data[top++] = x って書き方は置いておくとして、throws RuntimeException は・・・書く必要ないよね？
というか、throw new RuntimeException(); とかやめて欲しい。
この場合だと IllegalStateException でしょ常識的に考えて。
ここの他にも RuntimeException を直接投げてるところがあるけど、もっと適切な例外を投げるべき。

java.util.Stack は・・・非推奨じゃないけど非推奨

Java には Java.util.Stack が標準で提供されています。
Java データ構造とアルゴリズム基礎講座 4.1.1 スタックの実装 (P.68)

パッケージ名は typo だろうからほっとく*2。
で、java.util.Stack だけど、これは Vector を継承するという最低なことをやっているクラスだから、これを紹介するのはいかがなものか。

より完全で一貫性のある一連の LIFO スタックオペレーションが、Deque インタフェースとその実装によって提供されています。このクラスよりもそれらを優先的に使用するようにしてください。例を示します。
Deque<Integer> stack = new ArrayDeque<Integer>();
Stack (Java Platform SE 6)

両端キューは、LIFO (後入れ先出し) スタックとして使用することもできます。従来の Stack クラスよりもこのインタフェースを優先して使用してください。両端キューがスタックとして使用される場合、両端キューの先頭から要素のプッシュとポップが行われます。Stack メソッドは、次の表に示すように Deque メソッドとまったくの等価です。

Stack メソッド等価な Deque メソッド

push(e) addFirst(e)

pop() removeFirst()

peek() peekFirst()

両端キューがキューまたはスタックとして使用される場合、peek メソッドも同様に機能します。どちらの場合も、要素は両端キューの先頭から取り出されます。
Deque (Java Platform SE 6)

Stack メソッド	等価な Deque メソッド
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

良い子の皆は Stack 使わずに Deque 実装したクラス*3を Deque に入れて使いましょう。

Stack、Queue

インターフェイスを使ってないから、この本で紹介した配列による実装しか実装がないと勘違いしそう。

リストと配列の違い

配列と異なり、任意の型のデータを格納することができるようになっています。
Java データ構造とアルゴリズム基礎講座リスト (P.77)

えと、配列も任意の型のデータを格納すること出来るんですけど・・・
ちょっと何を言っているのか分からない。

連結リストに対する幻想

データの挿入・削除の計算量は配列 O(n)、リスト O(1) です。
Java データ構造とアルゴリズム基礎講座 5.1.1 データの挿入と削除 (P.79)

リストは連結リストの typo だろう。
だとしても、O(1) で挿入と削除が出来るかって言うと・・・難しいよね。

連結リストはランダムアクセスが出来ないから、連結リストの任意の場所に挿入したり、任意の場所の要素を削除するためには、まず先頭から辿っていかないといけない。
この操作は O(N) なので、データを挿入・削除する場所が分かっていなければ連結リストでは挿入も削除も O(N) となってしまう。
これを書かないのはちょっとどうかと思うなー。

上はリストに対する過大評価だけど、逆にリストに対する過小評価も見られる。

処理線形リスト双方向リスト

... ... ...

末尾への挿入 addLast(E) O(n) O(1)

... ... ...

リストの長さ size() O(n) O(n)

... ... ...

Java データ構造とアルゴリズム基礎講座表 5-1 計算量の比較 (P.94)

処理	線形リスト	双方向リスト
...	...	...
末尾への挿入 addLast(E)	O(n)	O(1)
...	...	...
リストの長さ size()	O(n)	O(n)
...	...	...

連結リスト (線形リスト) で末尾へ挿入するのは、常に末尾要素を指すものを用意しておくだけで O(1) に出来るし、リストの長さだってこの本に載ってる程度の操作しか実装しないなら O(1) で実装できる。

自己参照型・・・？

フィールド data がデータを、next が次のリストセルへのポインタを格納します。next は自分自身と同じクラスのインスタンスを指すため、自己参照型と呼ばれます。
class Cell<E>{
    E data;         // データ
    Node <E> next;  // 次のデータへのリンク
}
Java データ構造とアルゴリズム基礎講座 5.2.1 リストセルクラス (P.80)

ここでまさかの Node クラスw
もちろん、正しくはこう。

class Cell<E> {
    E data;
    Cell<E> next;
}

木構造・グラフ構造

post-order を戻りがけ順と訳しているけど、帰りがけ順が普通なんじゃ？
まぁ、それはどうでもいいんだけど、平衡木に触れられてもいないのはちょっと・・・
そのくせグラフの探索アルゴリズムとして、

幅優先探索
深さ優先探索
分岐限定法
山登り法
最良優先探索法
A(A*) アルゴリズム

と、かなり豊富*4。でも

本を持っているだけで英語が使えるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。
Java データ構造とアルゴリズム基礎講座はじめに (P.4)

探索アルゴリズムを並べているだけでグラフの探索アルゴリズムが選択できるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。

データの・・・検索？

第 8 章データの検索

8.1 線形検索
8.1.1 番兵による線形検索の改良
8.2 2分検索

Java データ構造とアルゴリズム基礎講座：書籍案内｜技術評論社

検索じゃなくて探索じゃないの？

検索と探索の違いは、検索は目的の情報を探し出す基準が決まっているのに対して、探索は有効な基準（解析的な解法）がない、あるいは用いないときに、実際に試行錯誤することによって解を探す方法を取る事。
アルゴリズム

本格的な用途ではデータベースという仕組みを用いてデータの管理を行います。この仕組みの中でも本章で学習するアルゴリズムが使われています。
Java データ構造とアルゴリズム基礎講座第 8 章データの検索 (P.141)

うーん、線形探索やハッシュ法は使われてるだろうけど、二分探索はどうなんだろ？
インデックスって基本的には B 木系だから、二分探索は使われてないんじゃないかなぁ。

あと、二分探索木と二分探索法の関係に触れてないのはどうかと思う。
・・・って、二分探索木は本文中でも 2分探索木だけど、二分探索法は 2分検索法としてるところを見ると、全くの別物と考えてるとか？
それはないと信じたい。

で、ここでも

本を持っているだけで英語が使えるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。
Java データ構造とアルゴリズム基礎講座はじめに (P.4)

探索アルゴリズムを並べているだけで適切な探索アルゴリズムが選択できるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。

シェルソートの計算量

シェルソートの比較回数と交換回数は n log n に比例しており、計算量 (オーダ) は O(n log n) と非常に高速です。
Java データ構造とアルゴリズム基礎講座 9.5.1 ギャップの選択 (P.168)

ん？シェルソートって O(n^1.5) とか、O(n^1.25) てのはよく聞くけど、O(n log n) になる数列なんてあったっけ？
・・・と思って調べてみたら、あるみたい。これに関しては後で書く。
だとしても、その数列は定数項が大きすぎて、全然実用的な速度が出ないので、「O(n log n) と非常に高速です」と書いてしまうのにはちょっとというかかなり疑問が。
追記：
やっぱりないみたい。正確には、まだ見つかっていない。あるかもしれないし、ないかもしれない。
で、どうやら O(n log² n) を O(n log n) と等価であると思っているっぽい・・・？
O(n log² n) は O(n^1.25) よりはるかに低速なので、定数項云々関係なく低速。失礼しました。

あ、それと、挿入ソートがソート済みの並びに対して O(n) になると書いてないのは独特というか、他に類を見ない感じ。

ソート

安定なソートに関する記述がないのはどうなんだろ。
そしてもちろんここでも

本を持っているだけで英語が使えるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。
Java データ構造とアルゴリズム基礎講座はじめに (P.4)

ソートアルゴリズムを並べているだけで適切なソートアルゴリズムが選択できるようになるわけではありません。どんなシチュエーションで使うかを知らなければ、宝の持ち腐れです。

で、結局どうなの？

これは、半期の授業で使う用の本だと思う。あまりにも言葉が足りなさすぎる。
なので、この本で勉強しようとは思わない方がいい。
この本を買うくらいなら、あとほんの少し出して

Javaプログラマのためのアルゴリズムとデータ構造

作者: 近藤嘉雪
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2004/03
メディア: 単行本
購入: 1人クリック: 70回
この商品を含むブログ (16件) を見る

こっちの方がおすすめ。
ただ、古い本だからジェネリック非対応なんだよなぁ・・・

追記：
ジェネリック対応を謳った最新版、全然対応できていない非常に残念な本になってしまった。
普通に Object 使いまくってるあれのどこがジェネリック対応なんだろう・・・

*1:ほめるのって難しいよね(うわ、最低)

*2:P.72 では Java.Util.Queue にパワーアップ

*3:ArrayDeque とか LinkedList とか

*4:しかしこの選択・・・微妙

前書き

UML はフローチャートじゃないよ！

無限ループ

名前の付け方・フォーマット

分割方法

オブジェクト指向プログラミング

配列

NULL

れいがい！

java.util.Stack は・・・非推奨じゃないけど非推奨

Stack、Queue

リストと配列の違い

連結リストに対する幻想

自己参照型・・・？

木構造・グラフ構造

データの・・・検索？

第 8 章 データの検索

シェルソートの計算量

ソート

で、結局どうなの？

第 8 章データの検索