SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

翔泳社 新刊紹介(PR)

視覚的にイメージしにくいアルゴリズムを徹底的にイラストで表現するとこうなる

  • このエントリーをはてなブックマークに追加

 近年、IT企業の社員研修ではアルゴリズムを理解することが重視されるようになってきました。しかし、文字とフローチャートだけでは仕組みをイメージしづらいのも事実。『アルゴリズム図鑑』ではアルゴリズムをまず視覚的にイメージできるように、26種類のアルゴリズムをイラストで解説。3種類のアルゴリズムを紹介します。

  • このエントリーをはてなブックマークに追加

アルゴリズム図鑑』の元となったのは、Appleが2016年末に発表した「ベストApp10選」に選ばれたアプリ「アルゴリズム図鑑」です。

 勉強しようと思っても、文字や少数の図解だけでは仕組み・概念を理解しづらいのがアルゴリズム。アプリではイラストで表現することでその課題を解決し、大変な好評を得ました。本書は紙幅を活かして一覧での見やすさを高め、26種類のアルゴリズムを徹底的にイラストで表現しました。

 今回は本書から、データ構造の「リスト」、グラフを探索するアルゴリズムの「幅優先探索」、データを暗号化するアルゴリズムの「公開鍵暗号方式」、データを似たもの同士に分類するクラスタリングアルゴリズムの「k-means法」を紹介します。

リスト――データ構造

 アルゴリズムの仕組みを理解するのであれば、そこで扱うデータの構造について知っておく必要があります。データはメモリに蓄えられており、その際にデータの順番や位置関係などを規定したものがデータ構造です。

 データ構造の一つが「リスト」。データを一直線に並べた構造をしていて、データの追加や削除がしやすいメリットがある反面、アクセスには時間がかかるというデメリットもあります。

リスト1-1

 これはリストの概念図で、三つのデータが格納されています。各データを繋いでいるのがポインタで、メモリ上の位置を指し示します。

リスト1-2

 リストではポインタが位置関係を規定するため、メモリ上の連続した領域に格納される必要がありません。データは一般的に離れた領域に格納されています。

リスト1-3
リスト1-4

 格納場所が異なるため、各データにはポインタを順に辿らないとアクセスできません(順次アクセス、またはシーケンシャルアクセス)。RedにアクセスしたいときはBlueからアクセスし、Yellowを経る必要があります。

リスト1-5

 データを追加するときは、追加する前後のデータのポインタを指し替えるだけなので簡単です。BlueとYellowの間にGreenを追加したいときは……

リスト1-6

 BlueのポインタをGreenに、GreenのポインタをYellowに向けます。これでデータが追加されたことになります。もちろんGreenのデータはメモリ上のどこにあっても構いません。

リスト1-7

 データの削除もポインタの指し替えで行います。Yellowを削除したいなら……

リスト1-8

 GreenのポインタをRedに指し替えましょう。Yellowはどこからもアクセスできないので、消す必要もなく、その領域は別のデータに上書きされて再利用されます。

 ここで紹介したリストは最も基本的なもので、拡張されたものもあります。リストの最後尾のデータであるRedはポインタを持っていませんでしたが、Redから先頭のBlueへポインタを指せば「環状リスト(循環リスト)」ができ上がります。常に一定個の最新データを保持したいときに有用です。

 また、各データに双方向のポインタを持たせて、「双方向リスト」を作ることもできます。リストを前からでも後ろからでも辿れるので便利ですが、ポインタの数が増えることでデータ格納のための領域が多くなる欠点もあります。

リスト1-9

次のページ
幅優先探索――グラフ探索

この記事は参考になりましたか?

  • このエントリーをはてなブックマークに追加
翔泳社 新刊紹介連載記事一覧

もっと読む

この記事の著者

渡部 拓也(ワタナベ タクヤ)

 翔泳社マーケティング課。MarkeZine、CodeZine、EnterpriseZine、Biz/Zine、ほかにて翔泳社の本の紹介記事や著者インタビュー、たまにそれ以外も執筆しています。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/10198 2017/06/13 07:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング