こんにちは、@yshr10icです。
先日、某試験の受験が終わったので、自分の好きなことに時間を割けるようになりました。
ふと、仕事をしていたときに、そういえばアルゴリズムって昔勉強したことあるけど、きちんと理解できているか不安だな、と思いました。そこで基礎から勉強したいと思い、「アルゴリズム図鑑」を購入しました。
本記事では、読んだことを読書メモとして残したいと思います。
本の紹介
本の章立ては次の通りです。
- 第1章 データ構造
- 第2章 ソート
- 第3章 配列の探索
- 第4章 グラフ探索
- 第5章 セキュリティのアルゴリズム
- 第6章 クラスタリング
- 第7章 その他のアルゴリズム
読んだ感想や気付き
本書は、以下の写真のように、非常に分かりやすく、データ構造やアルゴリズムについて説明されています。（写真はAmazonの試し読みから引用しました。）
第1章 データ構造
データ構造であるリスト、配列、スタック、キュー、ハッシュテーブル、ヒープ、2分探索木について説明されています。
それぞれのデータ構造がどういう特徴を持っていて、「データの追加や削除」「データへのアクセス」の計算時間はどれくらいなのか、説明されています。
普段の仕事では、せずリストまたは配列を使うことがほとんどで、ほとんど計算時間について考えていませんでした。
データの追加や削除は多いのか少ないのか、データへのアクセスは多いのか少ないのか、今後は考えてから使うようにしたいと思います。
第2章 ソート
バブルソート、選択ソート、挿入ソート、ヒープソート、マージソート、クイックソートについて説明されています。
それぞれのソートについて、どういう風にソートされるかを絵で説明しており、ソートの計算時間はどれくらいなのか、説明されています。
普段の仕事では、ソートを行う際にはライブラリが提供している標準メソッドを使用するのですが、そのライブラリがどのアルゴリズムを使っていて、どれくらいの計算時間なのか考えたこともありませんでした。
試しに、私が普段使用している.Net Frameworkのソートについて調べてみました。
List.Sort メソッド
・パーティションサイズが16要素以下の場合は、挿入並べ替えアルゴリズムが使用されます。
・パーティションの数が2つのログn( nは入力配列の範囲) を超えている場合、 heapsortアルゴリズムが使用されます。
・それ以外の場合は、クイックソートアルゴリズムを使用します。
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.8
第3章 配列の探索
線形探索、2分探索について説明されています。
それぞれの探索について、どういう風に探索されるかを絵で説明しており、探索の計算時間はどれくらいなのか、説明されています。
第4章 グラフ探索
幅優先探索、深さ優先探索、ベルマン-フォード法、ダイクストラ法、A*（エー・スター）について説明されています。
グラフとは？という説明から入り、それぞれの探索について、どういう風に探索されるかを絵で説明しており、探索の計算時間はどれくらいなのか、説明されています。
第5章 セキュリティのアルゴリズム
本章は他の章とは少し異なっていて、セキュリティのアルゴリズムの説明です。
ハッシュ関数、共通鍵暗号方式、公開鍵暗号方式、ハイブリッド暗号方式、ディフィ-ヘルマン鍵交換法、メッセージ認証コード、デジタル署名、デジタル証明書について説明されています。
データをやり取りする際の問題として、「盗聴」「なりすまし」「改ざん」「事後否認」の4つを挙げ、それらの問題を解決する技術について説明しています。
上に挙げられている単語のうち、「ディフィ-ヘルマン鍵交換法」以外は聞いたこともあったのですが、人に説明できるような知識は持っていませんでした。
第6章 クラスタリング
k-means法について説明されています。
第7章 その他のアルゴリズム
ユークリッドの互除法、素数判定法、ページランク、ハノイの塔について説明されています。
本章の内容については、なかなか普段から使うことはないような気がしています。
ハノイの塔については、大学のプログラミングの授業でやったのを思い出しました。（あの頃はチンプンカンプンでしたねｗ）
まとめ
すべてが絵で描かれているため、非常に分かりやすかったです。
今までは計算時間など特に気にせず実装していましたが、今後は計算時間など考えて実装していきたいと思います。（まずは何でもリストにしてしまうクセを辞めます。）
その他おすすめな本
