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

George T. Heineman、Gary Pollice、Stanley Selkow 著、黒川利明、黒川洋訳

TOPICS: クイックリファレンス , Programming , C/C++
発行年月日: 2010年04月
PRINT LENGTH: 396
ISBN: 978-4-87311-428-6
原書: Algorithms in a Nutshell
FORMAT

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

正誤表

書籍発行後に気づいた誤植や更新された情報を掲載しています。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷数をご確認の上、ご利用ください。

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)=xcos(x)+sin(x)-5-sin(x)=xcos(x)-5とする。	その導関数をf'(x)=xcos(x)+sin(x)-5+sin(x)=xcos(x)+2*sin(x)-5とする。（原書正誤表に従い修正）
p27 表2-2	■	（原書正誤表に従い修正）
p39 表2-6	■	（原書正誤表に従い修正）
p65 ††訳注	文字""は「文字がない」符号と考えることも可能で	文字"¬"は「文字がない」符号と考えることも可能で
p77 5行目	図4-10の各行は、ループの中で、軸値（この場合は要素「06」）。以下の	図4-10の各行は、ループの中で、軸値（この場合は要素「06」）以下の
p88 図4-12 上部	■	（原書正誤表に従い修正）
p89 図4-13 上部	■	（原書正誤表に従い修正）
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行目	経路<v₃, v₁, v₅, v₄, v₂, v₁, v₅, v₄, v₂ >は閉路となるが、これは	経路<v₃, v₁, v₅, v₄, v₂, v₁, v₅, v₄, v₂ >には閉路が含まれるが、それは
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行目		（原書正誤表に従い修正）
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)=xcos(x)+sin(x)-5-sin(x)=xcos(x)-5とする。	その導関数をf'(x)=xcos(x)+sin(x)-5+sin(x)=xcos(x)+2*sin(x)-5とする。（原書正誤表に従い修正）
p27 表2-2	■	（原書正誤表に従い修正）
p39 表2-6	■	（原書正誤表に従い修正）
p65 ††訳注	文字""は「文字がない」符号と考えることも可能で	文字"¬"は「文字がない」符号と考えることも可能で
p88 図4-12 上部	■	（原書正誤表に従い修正）
p89 図4-13 上部	■	（原書正誤表に従い修正）
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行目	経路<v₃, v₁, v₅, v₄, v₂, v₁, v₅, v₄, v₂ >は閉路となるが、これは	経路<v₃, v₁, v₅, v₄, v₂, v₁, v₅, v₄, v₂ >には閉路が含まれるが、それは
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行目		（原書正誤表に従い修正）
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)=xcos(x)+sin(x)-5-sin(x)=xcos(x)-5とする。	その導関数をf'(x)=xcos(x)+sin(x)-5+sin(x)=xcos(x)+2*sin(x)-5とする。（原書正誤表に従い修正）
p27 表2-2	■	（原書正誤表に従い修正）
p39 表2-6	■	（原書正誤表に従い修正）
p65 ††訳注	文字""は「文字がない」符号と考えることも可能で	文字"¬"は「文字がない」符号と考えることも可能で
p88 図4-12 上部	■	（原書正誤表に従い修正）
p89 図4-13 上部	■	（原書正誤表に従い修正）
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行目		（原書正誤表に従い修正）
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.

目次
まえがき

第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刷正誤表

2刷正誤表

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

3刷正誤表

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

目次

関連書籍

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

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

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