書評: 「Java データ構造とアルゴリズム」、ロバート・ラフォレ

すべてのプログラマーの強みは、その知識にあります。確かに、Google で検索する能力も最下位ではありませんが、それでも、ある程度の知識が必要であり、それに基づいて開発者の考え方が形成されます。この知識が深くなればなるほど、プログラマーはより興味深いソリューションを思いつくことができます。 そのような「基盤」の一部の 1 つは、データ構造とアルゴリズムです。この方向に知識を広げるにはどうすればよいでしょうか? オプションとして、耐火予備およびさらなる研究の基礎となる知識が得られる本を見つけてください。私にとってそのような本は、Robert Laforet 著の『Java Data Structures and Algorithms』でした。

誰のため

この本の読者は、 Java言語の構文をマスターしたばかりの人にとっても、実務プログラマーにとっても、データ構造とアルゴリズムの特徴をより深く理解するのに役立つため、非常に幅広い人々が対象となります。 。

何について

この本は、プログラミングにおけるデータ構造とアルゴリズムの研究と使用に特化しています。データ構造がメモリ内でデータを編成する方法を決定する方法と、アルゴリズムがこれらの構造に対してさまざまな操作を実行する方法を読者に教えます。もう少し深く掘り下げて、この本が正確に何について書かれているかを見てみましょう。

1. 配列。配列および順序付けされた配列での挿入、検索、および削除の操作について詳しく説明します。順序付き配列と順序なし配列の線形検索と二分探索の操作を示します。O 構文とは何かについても学びます。
2. 並べ替え中。簡単なソート方法としては、「バブルソート」、「選択ソート」、「挿入ソート」の3つが考えられます。この本を読めば、どれが最も遅く、どれが最も単純であるかがわかります。
3. スタックとキュー。スタック、キュー、プライオリティキューなどのデータ構造とその有効性、Javaでの実装について考察します。
4. リンクされたリスト。この本では、二重リンクと二重リンクのリスト、その効率、挿入、検索、削除の操作がどのように実行されるかについて説明します。イテレータとそれに必要なメソッドについても説明します。
5. 再帰。再帰は、三角数と階乗の計算、アナグラムの作成、再帰二分探索の実行、ハノイの塔パズルの解決、マージ ソートの実装、ナップザック問題の解決など、さまざまな状況で考慮されます。
6. 簡単ではない並べ替え。シェル ソート、クイック ソート、基数ソート、そのアルゴリズム、効率など、より高度な方法が検討されています。
7. 二分木。バランスのとれた二分探索ツリー、その動作方法、挿入および削除操作、さまざまなタイプのトラバーサル、最小値と最大値の検索、後続ものの検索について検討します。ハフマンコードについても取り上げます。
8. 赤と黒の木々。バランスの取れたツリーの最も効果的な種類の 1 つである、バランスをとるために必要な回転と色の切り替え操作を検討します。
9. 樹木2-3-4．このタイプのツリーはマルチパス ツリーの例として説明され、その動作と、外部データ ストレージに使用される B ツリーとの関係について説明します。
10. ハッシュテーブル。ハッシュとそのさまざまな方法 (線形および二次プローブ、ダブル ハッシュ、連鎖方法など) がカバーされています。ハッシュを使用して外部ファイル ストレージを整理する方法についても学習できます。
11. ピラミッド。これは、優先キューを効率的に実装するために使用される特別なタイプのツリーです。この本では、挿入、削除、再配置の操作メカニズムについて説明します。また、ピラミッド順列とは何か、およびそれを Java で実装する方法についても学びます。
12. グラフ。重み付けされたグラフと重み付けされていないグラフ、それらを検索するためのアルゴリズム、および最短のトラバース パスを見つけるために使用されるアルゴリズムが示されています。

より明確にするために、各章では問題のデータ構造の独自の実装を示します。たとえば、これが単一リンク リストの場合、説明されている機能を実装するクラスの例が示されます。この本の最終章では、前の章で得た知識を基にして、すべての知識を 1 つの図にまとめ始めます。たとえば、どの状況でどのデータ構造を使用するかについてのアイデアを明確に形成できるようになります。各章の最後には小さな演習もあります。それらの中には、ワークショップアプリを使用して作業を行うものもあれば、コード内で直接小さなタスクを提供するものもあります。

ワークショップアプリとは

ワークショップアプリケーションは、これらの構造とアルゴリズムをデモンストレーションするために使用されます。アプリケーションは、ブラウザーで実行できる Java アプレットとして設計されています。ワークショップアプリケーションは、アルゴリズムやデータ構造がどのように機能するかを示すグラフィカルな図を作成します。たとえば、列を昇順に並べ替えて表示するように設計されたアプリケーションでは、ヒストグラム上のボタンをクリックするたびに、次のステップが実行されます。この場合、このアルゴリズムに関係する変数の値が表示されるので、コードがどのように実行されるかがわかります（デバッガの説明を思い出しますね）。

Workshopのダウンロードとインストール方法

1. アプレットはここからダウンロードできます。
2. WorkshopApplets.ZIPをクリックして、アプレットを含むアーカイブをダウンロードします。
3. アプレットを理解するには、このトピックとそのコメントを読んでください。

この本の良い点

• 非常に読みやすく、多くの例がほとんど「すぐに」説明されています。
• 複雑な数式を使用せずに、多くの「古典的な」事柄に目を開かせます。まあ、ほとんどなしです:)
• 例は Java で示されていますが、コード内で発生するアクションは、次のテキストとコード内のコメントで詳細に説明されています。したがって、コード例は非常に単純であるため、どのプログラミング言語のユーザーでも読むことができ、ほとんど擬似コードのように読めます。

この本の短所

• 「指の上で」という説明にもかかわらず、そこにはギャップがあります。配列ソートを説明するために、著者はフットボール チームの絵を描きますが、そこにはシェル ソートについてはほとんど記載されていません。私はそれを理解できず、インターネットで読んでも理解できませんでした。
• 通常、画像や表にタイプミスがある可能性があります。
• 一部のコードはかなり古いです。

類似体

この本と類似の本、またはそれに続く本をお勧めします (学習を続けたい人向け)。

• 「Java のアルゴリズム」ロバート・セジウィック著。
• 「アルゴリズム: 構築と分析」トーマス・コーメン著。

結論

この本には欠点がほとんどないので、読む価値があります。さまざまなソート、配列、ツリー、コレクション、グラフなど、多くの基本的なトピックを明確に説明しています。この本はJavaと強く結びついていないため、この本を学習して得た知識ベースは他のプログラミング言語でも役立ちます。 開発者であれば必ず読んでください。