アルゴリズムクイックリファレンス

[cover photo]
  • George T. Heineman、Gary Pollice、Stanley Selkow 著、黒川 利明、黒川 洋 訳
  • 2010年04月 発行
  • 396ページ
  • ISBN978-4-87311-428-6
  • フォーマット Print PDF
  • 原書: Algorithms in a Nutshell

オライリー・ジャパンで書籍を購入:
定価3,456円

Ebook Storeで電子版を購入:
価格2,764円


障害に強い、問題が起こりにくいコードにはまず正しいアルゴリズムの選択から。理論だけでなく実践的側面を重視した、新しいタイプのアルゴリズムの書籍です。適切な問題解決、性能改善という、現場が求める2つの大きな要求に応えるため、どのアルゴリズムを使うべきか、どう実装するのか、さらに性能を向上させる方法はあるのかを、C、C++、Java、Rubyなど、さまざまな言語を使って説明します。図、表、サンプルコードがふんだんに盛り込まれ、付録にベンチマークのための知識、手法を紹介するなど、非常に実際的、実践的な一冊です。

関連書籍

C実践プログラミング 第3版
集合知プログラミング

目次
まえがき

第I部
1章 アルゴリズムは大事だ
    1.1 問題を理解せよ
    1.2 必要なら実験しろ
    1.3 救援のためのアルゴリズム
    1.4 ついでの話
    1.5 この話の教訓
    1.6 参考文献

2章 アルゴリズムの数学
    2.1 問題インスタンスのサイズ
    2.2 関数の成長率
    2.3 最良、平均、最悪時の分析
    2.4 性能でグループ分けする
    2.5 異種の演算の混合
    2.6 ベンチマーク
    2.7 最後に一言
    2.8 参考文献

3章 パターンとドメイン
    3.1 パターン――コミュニケーションの言語
    3.2 アルゴリズムのパターン形式
    3.3 疑似コードのパターン形式
    3.4 設計形式
    3.5 評価実験の形式
    3.6 ドメインとアルゴリズム
    3.7 浮動小数点計算
    3.8 手動メモリ割り付け
    3.9 プログラミング言語を選ぶ
    3.10 参考文献

第II部
4章 整列アルゴリズム
    4.1 概観
    4.2 挿入ソート
    4.3 中央値ソート
    4.4 クイックソート
    4.5 選択ソート
    4.6 ヒープソート
    4.7 数え上げソート
    4.8 バケツソート
    4.9 整列アルゴリズムの選択基準
    4.10 参考文献

5章 探索
    5.1 概観
    5.2 逐次探索
    5.3 二分探索
    5.4 ハッシュに基づいた探索
    5.5 二分木探索
    5.6 参考文献

6章 グラフアルゴリズム
    6.1 概観
    6.2 深さ優先探索
    6.3 幅優先探索
    6.4 単一始点最短経路
    6.5 全対最短経路
    6.6 最小被覆木アルゴリズム
    6.7 参考文献

7章 AIにおける経路発見
    7.1 概観
    7.2 深さ優先探索
    7.3 幅優先探索
    7.4 A*探索
    7.5 比較
    7.6 ミニマックス
    7.7 NegMax
    7.8 アルファベータ法

8章	ネットワークフローアルゴリズム
    8.1 概観
    8.2 最大フロー
    8.3 二部マッチング
    8.4 増加道についての考察
    8.5 最小コストフロー
    8.6 積み替え
    8.7 輸送
    8.8 割り当て
    8.9 線形プログラミング
    8.10 参考文献

9章 計算幾何学
    9.1 概観
    9.2 凸包走査
    9.3 線分走査法
    9.4 最近傍質問
    9.5 範囲質問
    9.6 参考文献

第III部
10章 他のすべてがうまくいかなかったとき
    10.1 主題の変形
    10.2 近似アルゴリズム
    10.3 オフラインアルゴリズム
    10.4 並列アルゴリズム
    10.5 乱択(Randomized)アルゴリズム
    10.6 間違うかもしれないがその確率を減少させたアルゴリズム
    10.7 参考文献

11章 結び
    11.1 概観
    11.2 原則:汝のデータを知れ
    11.3 原則:問題を小さく分割せよ
    11.4 原則:正しいデータ構造を選べ
    11.5 原則:性能を上げるにはストレージを追加せよ
    11.6 原則:解が明らかでないなら、探索を構築せよ
    11.7 原則:解が明らかでないなら、解を持つ別の問題に帰着させよ
    11.8 原則:アルゴリズムを書くのは難しい、アルゴリズムを試験するのはもっと難しい

第IV部
付録 ベンチマーク
    A.1 統計の基礎
    A.2 ハードウェア
    A.3 例
    A.4 報告
    A.5 精度

索引
訳者あとがき

ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。

1刷正誤表

アルゴリズムクイックリファレンス 第1刷正誤表

2010年12月14日更新

位置
pxi
下から
12行目
http://www.oreilly.co.jp/books/9780596514286/(日本語) http://www.oreilly.co.jp/books/9784873114286/(日本語)
p26
下から
8行目
while (hight - low <= 2){
while (hight - low >= 2){
(原書正誤表に従い修正)
p27
2段落
3行目
その導関数をf'(x)=x*cos(x)+sin(x)-5-sin(x)=x*cos(x)-5とする。
その導関数をf'(x)=x*cos(x)+sin(x)-5+sin(x)=x*cos(x)+2*sin(x)-5とする。
(原書正誤表に従い修正)
p27
表2-2
fig2-2before

fig2-2before
(原書正誤表に従い修正)
p39
表2-6
fig2-6before
fig2-6before
(原書正誤表に従い修正)
p65
††訳注
文字""は「文字がない」符号と考えることも可能で 文字"¬"は「文字がない」符号と考えることも可能で
p77
5行目
図4-10の各行は、ループの中で、軸値(この場合は要素「06」)以下の 図4-10の各行は、ループの中で、軸値(この場合は要素「06」)以下の
p88
図4-12
上部
fig4-12before
fig4-12after
(原書正誤表に従い修正)
p89
図4-13
上部
fig4-13before
fig4-13after
(原書正誤表に従い修正)
p92
4.4.5.2
1行目
例4-3の分割法では、 例4-3関数partitionでは、
p92
4.4.5.2
3行目
再帰段階での部分配列のサイズが変動するかもしれない。最初の部分配列と2番目の部分配列との間で、軸値に等しい要素を入れ替えれば釣り合いが取れる。 再帰段階での部分配列のサイズが偏るかもしれない。軸値に等しい要素は、最初の部分配列と2番目の部分配列に交互に入れれば釣り合いが取れる。
p96
図4-14
9.
swap A[i]
swap A[idx]
(原書正誤表に従い修正)
p123
5.3.1
1行目
二分探索の入力は、添え字付きの集まりAである。
二分探索の入力は、整列済みの添え字付きの集まりAである。
(原書正誤表に従い修正)
p128
図5-3
1. 与えられたサイズの配列
2. for i = 0 to n - 1 do
3.  h = hash(C[i])
4.  if A[h]が空である then
5.   A[h] = new Linked List
6.  add C[i] to A[h]
7. return A
1. A = 与えられたsizeの配列
2. for i = 0 to n - 1 do
3.  h = hash(C[i])
4.  if A[h]が空である then
5.   A[h] = new Linked List
6.  C[i]A[h]に追加する
7. return A
p141
12行目
再ハッシュ機能を利用できる。 再ハッシュ機能を導入できる。
p154
4行目
経路<v3, v1, v5, v4, v2, v1, v5, v4, v2 >は閉路となるが、これは 経路<v3, v1, v5, v4, v2, v1, v5, v4, v2 >には閉路が含まれるが、それは
p154
最終行
new int[4096][4096]で2次元配列を作ろうとすると
new int[8192][8192]で2次元配列を作ろうとすると
(原書正誤表に従い修正)
p160
図6-9
1.
foreachv ∈ V do
foreach v ∈ V do
(原書正誤表に従い修正)
p186
例6-8
コメント
1行目
sからtへの経路を節点のベクトルとして
sからtへの経路を節点のリストとして
(原書正誤表に従い修正)
p211
下から
2行目
図の中で濃い灰色の20個の盤面状態は、 図の中で薄い灰色の20個の盤面状態は、
(原書正誤表に従い修正)
p212
下から
5行目
例7-3に示す実装では、 例7-4に示す実装では、
p221
表7-3
BadEvaluatorのh*(n)の記述
空の升目は無視する。

真ん中と空の升目は無視する。
(原書正誤表に従い修正)
p238
1行目
×が対角線でゲームを勝つことができる、負けてしまう盤面も調べていた。 ×が対角線でゲームを勝つことができる、○が負けてしまう盤面も調べていた。
p247
下から
2行目
ネットワーク全体の容量が十分あるとして、 ネットワーク全体の容量を満たすだけの十分な量の商品を流せるとして、
p250
下から
3行目
非負のフローと容量を保証するので、 非負のフローと容量の下で、
p276
下から
2行目
IPointと交差するか、IRectangleを含むか判定できる。 IPointまたはIRectangleを含むか判定できる。
p277
図9-1
IRectangle
5行目
+boolean intersects(IPoint) +boolean contains(IPoint)
p277
図9-1
ILineSegment
9行目
IPoint intersection(ILineSegment) IPoint intersection(ILineSegment)
†訳注:intersectionは、交差がなければnullを返すが、あれば、その点を返す。
p278
3行目
境界値が固定次元の[left, right]であるn次元立方体を表し、 各次元での境界値が[left, right]であるn次元立方体を表し、
p288
6行目
点集合が大きくなくても処理できる。 点集合が大きくても処理できる。
p291
9.2.7
2段落
2行目
実は明示的に整列配列をする必要はない。 実は明示的に配列を整列する必要はない。
p292
図9-12
平行二分木 二分木
(3箇所)
p292
3行目
2種類のデータ分布と 3種類のデータ分布と
(原書正誤表に従い修正)
p295
図9-14
左側
プロセスS1
(図)
プロセスS2
(図)
プロセスS3
(図)
プロセスS4
S1を処理
(図)
S2を処理
(図)
S3を処理
(図)
S4を処理
p308
9.4.3
3行目
①葉の節点が木の同じレベルにあり、 ①葉の節点が木の同じレベルにあるか
p309
下から
8行目
標準選択演算に負けてしまう。 標準的な選択演算に負けてしまう。
p313
下から
9行目
ただし、最近接質問点は、単位正方形内のままにする。 ただし、最近質問点は、単位正方形内のままにする。
p316
9.4.7
1行目
根から親へと節点をさかのぼって走査する。 根から親へと節点を戻って走査する。
p316
図9-24
中央の3.
3.  foreach descendant d of node do 3.  foreach ノードの子孫節点d do
p345
表11-4
タイトル
表11-4 7章のAIでの経路発見 表11-4 7章のAIでの経路発見アルゴリズム
p347
表11-6
直前
表11-6は、9章で取り上げた計算幾何学をまとめる。 表11-6は、9章で取り上げた計算幾何学アルゴリズムをまとめる。
p347
表11-6
タイトル
表11-6 9章の計算幾何学 表11-6 9章の計算幾何学アルゴリズム
p352
7行目
equationbefore equationafter
(原書正誤表に従い修正)
p359
A.3.3
2行目
1章で使ったこの例では、 2例2-7で使ったこの例では、
(原書正誤表に従い修正)
p362
5行目
例A-8の関数largeAddは、n個の数の集まりをまとめて加算する。 例A-8の関数largeAddは、n個の数の集まりをまとめて加算する†。
†訳注:原著者によると、このコードでは次のScheme実装に依存した書き方をしている。必ずしも標準規格に沿ってはいない点に注意。 MzScheme version 207, Copyright (c) 2004 PLT Scheme, Inc.
p365
下から
12行目
プラットフォーム間で実行時間を比較したい時もある。 プラットフォーム間で実行時間を比較したい時に使えない
p365
下から
9行目
表A-3のデータを見直すと、 表A-4のデータを見直すと、

ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。

2刷正誤表

アルゴリズムクイックリファレンス 第2刷正誤表

2010年12月14日更新

位置
pxi
下から
12行目
http://www.oreilly.co.jp/books/9780596514286/(日本語) http://www.oreilly.co.jp/books/9784873114286/(日本語)
p26
下から
8行目
while (hight - low <= 2){
while (hight - low >= 2){
(原書正誤表に従い修正)
p27
2段落
3行目
その導関数をf'(x)=x*cos(x)+sin(x)-5-sin(x)=x*cos(x)-5とする。
その導関数をf'(x)=x*cos(x)+sin(x)-5+sin(x)=x*cos(x)+2*sin(x)-5とする。
(原書正誤表に従い修正)
p27
表2-2
fig2-2before

fig2-2before
(原書正誤表に従い修正)
p39
表2-6
fig2-6before
fig2-6before
(原書正誤表に従い修正)
p65
††訳注
文字""は「文字がない」符号と考えることも可能で 文字"¬"は「文字がない」符号と考えることも可能で
p88
図4-12
上部
fig4-12before
fig4-12after
(原書正誤表に従い修正)
p89
図4-13
上部
fig4-13before
fig4-13after
(原書正誤表に従い修正)
p92
4.4.5.2
1行目
例4-3の分割法では、 例4-3関数partitionでは、
p92
4.4.5.2
3行目
再帰段階での部分配列のサイズが変動するかもしれない。最初の部分配列と2番目の部分配列との間で、軸値に等しい要素を入れ替えれば釣り合いが取れる。 再帰段階での部分配列のサイズが偏るかもしれない。軸値に等しい要素は、最初の部分配列と2番目の部分配列に交互に入れれば釣り合いが取れる。
p96
図4-14
9.
swap A[i]
swap A[idx]
(原書正誤表に従い修正)
p123
5.3.1
1行目
二分探索の入力は、添え字付きの集まりAである。
二分探索の入力は、整列済みの添え字付きの集まりAである。
(原書正誤表に従い修正)
p128
図5-3
1. 与えられたサイズの配列
2. for i = 0 to n - 1 do
3.  h = hash(C[i])
4.  if A[h]が空である then
5.   A[h] = new Linked List
6.  add C[i] to A[h]
7. return A
1. A = 与えられたsizeの配列
2. for i = 0 to n - 1 do
3.  h = hash(C[i])
4.  if A[h]が空である then
5.   A[h] = new Linked List
6.  C[i]A[h]に追加する
7. return A
p141
12行目
再ハッシュ機能を利用できる。 再ハッシュ機能を導入できる。
p154
4行目
経路<v3, v1, v5, v4, v2, v1, v5, v4, v2 >は閉路となるが、これは 経路<v3, v1, v5, v4, v2, v1, v5, v4, v2 >には閉路が含まれるが、それは
p154
最終行
new int[4096][4096]で2次元配列を作ろうとすると
new int[8192][8192]で2次元配列を作ろうとすると
(原書正誤表に従い修正)
p160
図6-9
1.
foreachv ∈ V do
foreach v ∈ V do
(原書正誤表に従い修正)
p186
例6-8
コメント
1行目
sからtへの経路を節点のベクトルとして
sからtへの経路を節点のリストとして
(原書正誤表に従い修正)
p211
下から
2行目
図の中で濃い灰色の20個の盤面状態は、 図の中で薄い灰色の20個の盤面状態は、
(原書正誤表に従い修正)
p212
下から
5行目
例7-3に示す実装では、 例7-4に示す実装では、
p221
表7-3
BadEvaluatorのh*(n)の記述
空の升目は無視する。

真ん中と空の升目は無視する。
(原書正誤表に従い修正)
p238
1行目
×が対角線でゲームを勝つことができる、負けてしまう盤面も調べていた。 ×が対角線でゲームを勝つことができる、○が負けてしまう盤面も調べていた。
p247
下から
2行目
ネットワーク全体の容量が十分あるとして、 ネットワーク全体の容量を満たすだけの十分な量の商品を流せるとして、
p250
下から
3行目
非負のフローと容量を保証するので、 非負のフローと容量の下で、
p276
下から
2行目
IPointと交差するか、IRectangleを含むか判定できる。 IPointまたはIRectangleを含むか判定できる。
p277
図9-1
IRectangle
5行目
+boolean intersects(IPoint) +boolean contains(IPoint)
p277
図9-1
ILineSegment
9行目
IPoint intersection(ILineSegment) IPoint intersection(ILineSegment)
†訳注:intersectionは、交差がなければnullを返すが、あれば、その点を返す。
p278
3行目
境界値が固定次元の[left, right]であるn次元立方体を表し、 各次元での境界値が[left, right]であるn次元立方体を表し、
p288
6行目
点集合が大きくなくても処理できる。 点集合が大きくても処理できる。
p291
9.2.7
2段落
2行目
実は明示的に整列配列をする必要はない。 実は明示的に配列を整列する必要はない。
p292
図9-12
平行二分木 二分木
(3箇所)
p292
3行目
2種類のデータ分布と 3種類のデータ分布と
(原書正誤表に従い修正)
p295
図9-14
左側
プロセスS1
(図)
プロセスS2
(図)
プロセスS3
(図)
プロセスS4
S1を処理
(図)
S2を処理
(図)
S3を処理
(図)
S4を処理
p308
9.4.3
3行目
①葉の節点が木の同じレベルにあり、 ①葉の節点が木の同じレベルにあるか
p309
下から
8行目
標準選択演算に負けてしまう。 標準的な選択演算に負けてしまう。
p313
下から
9行目
ただし、最近接質問点は、単位正方形内のままにする。 ただし、最近質問点は、単位正方形内のままにする。
p316
9.4.7
1行目
根から親へと節点をさかのぼって走査する。 根から親へと節点を戻って走査する。
p316
図9-24
中央の3.
3.  foreach descendant d of node do 3.  foreach ノードの子孫節点d do
p345
表11-4
タイトル
表11-4 7章のAIでの経路発見 表11-4 7章のAIでの経路発見アルゴリズム
p347
表11-6
直前
表11-6は、9章で取り上げた計算幾何学をまとめる。 表11-6は、9章で取り上げた計算幾何学アルゴリズムをまとめる。
p347
表11-6
タイトル
表11-6 9章の計算幾何学 表11-6 9章の計算幾何学アルゴリズム
p352
7行目
equationbefore equationafter
(原書正誤表に従い修正)
p359
A.3.3
2行目
1章で使ったこの例では、 2例2-7で使ったこの例では、
(原書正誤表に従い修正)
p362
5行目
例A-8の関数largeAddは、n個の数の集まりをまとめて加算する。 例A-8の関数largeAddは、n個の数の集まりをまとめて加算する†。
†訳注:原著者によると、このコードでは次のScheme実装に依存した書き方をしている。必ずしも標準規格に沿ってはいない点に注意。 MzScheme version 207, Copyright (c) 2004 PLT Scheme, Inc.
p365
下から
12行目
プラットフォーム間で実行時間を比較したい時もある。 プラットフォーム間で実行時間を比較したい時に使えない
p365
下から
9行目
表A-3のデータを見直すと、 表A-4のデータを見直すと、

ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。

3刷正誤表

アルゴリズムクイックリファレンス 第3刷正誤表

2010年12月14日更新

位置
p26
下から
8行目
while (hight - low <= 2){
while (hight - low >= 2){
(原書正誤表に従い修正)
p27
2段落
3行目
その導関数をf'(x)=x*cos(x)+sin(x)-5-sin(x)=x*cos(x)-5とする。
その導関数をf'(x)=x*cos(x)+sin(x)-5+sin(x)=x*cos(x)+2*sin(x)-5とする。
(原書正誤表に従い修正)
p27
表2-2
fig2-2before

fig2-2before
(原書正誤表に従い修正)
p39
表2-6
fig2-6before
fig2-6before
(原書正誤表に従い修正)
p65
††訳注
文字""は「文字がない」符号と考えることも可能で 文字"¬"は「文字がない」符号と考えることも可能で
p88
図4-12
上部
fig4-12before
fig4-12after
(原書正誤表に従い修正)
p89
図4-13
上部
fig4-13before
fig4-13after
(原書正誤表に従い修正)
p92
4.4.5.2
1行目
例4-3の分割法では、 例4-3関数partitionでは、
p92
4.4.5.2
3行目
再帰段階での部分配列のサイズが変動するかもしれない。最初の部分配列と2番目の部分配列との間で、軸値に等しい要素を入れ替えれば釣り合いが取れる。 再帰段階での部分配列のサイズが偏るかもしれない。軸値に等しい要素は、最初の部分配列と2番目の部分配列に交互に入れれば釣り合いが取れる。
p96
図4-14
9.
swap A[i]
swap A[idx]
(原書正誤表に従い修正)
p123
5.3.1
1行目
二分探索の入力は、添え字付きの集まりAである。
二分探索の入力は、整列済みの添え字付きの集まりAである。
(原書正誤表に従い修正)
p154
最終行
new int[4096][4096]で2次元配列を作ろうとすると
new int[8192][8192]で2次元配列を作ろうとすると
(原書正誤表に従い修正)
p160
図6-9
1.
foreachv ∈ V do
foreach v ∈ V do
(原書正誤表に従い修正)
p186
例6-8
コメント
1行目
sからtへの経路を節点のベクトルとして
sからtへの経路を節点のリストとして
(原書正誤表に従い修正)
p211
下から
2行目
図の中で濃い灰色の20個の盤面状態は、 図の中で薄い灰色の20個の盤面状態は、
(原書正誤表に従い修正)
p221
表7-3
BadEvaluatorのh*(n)の記述
空の升目は無視する。

真ん中と空の升目は無視する。
(原書正誤表に従い修正)
p250
下から
3行目
非負のフローと容量を保証するので、 非負のフローと容量の下で、
p276
下から
2行目
IPointと交差するか、IRectangleを含むか判定できる。 IPointまたはIRectangleを含むか判定できる。
p277
図9-1
IRectangle
5行目
+boolean intersects(IPoint) +boolean contains(IPoint)
p277
図9-1
ILineSegment
9行目
IPoint intersection(ILineSegment) IPoint intersection(ILineSegment)
†訳注:intersectionは、交差がなければnullを返すが、あれば、その点を返す。
p291
9.2.7
2段落
2行目
実は明示的に整列配列をする必要はない。 実は明示的に配列を整列する必要はない。
p292
3行目
2種類のデータ分布と 3種類のデータ分布と
(原書正誤表に従い修正)
p352
7行目
equationbefore equationafter
(原書正誤表に従い修正)
p359
A.3.3
2行目
1章で使ったこの例では、 2例2-7で使ったこの例では、
(原書正誤表に従い修正)
p362
5行目
例A-8の関数largeAddは、n個の数の集まりをまとめて加算する。 例A-8の関数largeAddは、n個の数の集まりをまとめて加算する†。
†訳注:原著者によると、このコードでは次のScheme実装に依存した書き方をしている。必ずしも標準規格に沿ってはいない点に注意。 MzScheme version 207, Copyright (c) 2004 PLT Scheme, Inc.

Feedback

皆さんのご意見をお聞かせください。ご購入いただいた書籍やオライリー・ジャパンへのご感想やご意見、ご提案などをお聞かせください。より良い書籍づくりやサービス改良のための参考にさせていただきます。
[feedbackページへ]