Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

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

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2017/06/13 07:00

 近年、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

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

著者プロフィール

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

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

バックナンバー

連載:翔泳社 新刊紹介

もっと読む

All contents copyright © 2005-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5