2017-03-16

初めて学ぶ知識をどのように学習しているか

tech

ふと、自分が初めて学ぶ知識をどのように学習しているか疑問に思ったので、考えてみたことをブログに書いておく。初めて学ぶ知識というのは、自分がやったことだと例えばマネジメント、プロジェクト管理、コーチングなどがある。

僕はある知識を初めて学ぶ時、まずはストーリー仕立てで知識を解説してくれる本を読んでいることが多い。特にそのストーリーの背景に体系的な理論が見え隠れするようなものであれば、さらに良いと感じている。例えば以下のブログで紹介したような本を最初に読んでいる。

なぜこのような本を最初に読んでいるかというと、ストーリー仕立ての本は、インプットと同時に実践のイメージができると感じているからだ。

以前知識を効率的に身に付けるためのinputとoutputのバランス - $shibayu36->blog; の記事でも書いたけど、基本的に知識を理解したいと考えた時、インプットするだけでは理解出来ないと考えている。本当に理解するには、インプット前にその知識に関係する経験をしている、もしくはインプットした後に実践などを通じてその知識をアウトプットをする、のどちらかを行う必要があると感じる。

特定の知識を初めて学びたいと思ったときは、殆どの場合「その知識に関係する経験をしている」ということがない。そのため、ちゃんと体系的に学べるような本を買って読んだとしても、なかなか理解できないということが起こる。

その時に役立つのが、ストーリー仕立てで知識を解説してくれる本だ。ストーリー仕立てということは、ケーススタディではあるが、その知識に関係する経験をしながら、知識をインプットできる本だと思う。このような本を読めば、簡単な実践のイメージをしながらインプットができ、知識の理解を早く行うことができると考えている。

以上を理由として、自分はストーリー仕立てで知識を解説してくれる本をまず読んでいる。

一方、ストーリー仕立ての本は理解をしやすいが、体系的にその分野を基礎を学ぶのには適していない。そのため、そこに書かれている内容はできるけど、基礎知識に基づいた応用のようなことは出来ないことが多い。そのため、ストーリー仕立ての本を読んだ後、ある程度の経験を積んだら、ちゃんと分厚い体系的に学べるような本を読まなければならないと感じている。

これらを鑑みて、今まで僕は次のような手順で学習を進めているのだなと感じた。

まず分厚くないストーリー仕立ての本をいくつか読む
- ただしその本はしょうもないビジネス本ではなく、ある程度体系的な知識をベースとしているものが望ましい
本を読んで学んだ知識を使って、実際に実践を行い、その知識に対する経験を積む
ある程度の経験を積んだと感じたら、体系的にまとめられている厚い本を読み、基礎を固める
後は基礎の考え方を利用しながら、自分なりの応用を考える

この進め方は、まず実践まで早くたどり着けるので自分のモチベーションもある程度保てる。さらに実践をした後に基礎的なことを学ぶので、基礎の理解もしやすい。以上2点からこの方法はそこそこ良いと思っている。

この方法はそこそこ良いと感じているので、今後もこのようなやり方をベースにやっていきたい。

2017-03-12

「理論から学ぶデータベース実践入門」読んだ

tech

理論から学ぶデータベース実践入門 ~リレーショナルモデルによる効率的なSQL (WEB+DB PRESS plus)

作者:奥野幹也
技術評論社

Amazon

積ん読に入っていたので読んだ。

この本はリレーショナルモデルを理解することによってRDBの知識を深めようというような本。RDBを実践で使っている人がさらに知識を深めるための本という感じ。内容としては重要な理論がRDBと紐付けられて解説されていて面白かった。一方で、専門用語が文章中に多く使われていて、個人的には何か頭に入ってこなかった点は残念だった。

この本を読みながらわからないところを調べていて見つけたのだけど、この本の著者の昔の発表資料である「データベース設計徹底指南！！」がこの本の端的なまとめになっていて、しかも非常に良い資料なので本当におすすめ。本で紹介されているリレーショナルモデルや正規化理論などがわずか15分程度で理解できる資料となっていた。RDBを利用している人は是非読んだほうが良いと思う。資料は↓。

データベース設計徹底指南 from Mikiya Okuno

またこの本に出て来たRDBでツリー構造を表現する手法はなかなか興味深かった。隣接リストモデル、経路列挙モデル、入れ子集合モデルとかがあるみたい。以下のサイトにさらに詳しく載っていた。

DBは今後も避けることの出来ない分野なので、また良い本があったら読んでいきたい。SQL アンチパターンとかも機会があったら読みたい。

2017-03-11

高速なRandomized Queueのアルゴリズムを実装する

tech

CourseraのAlgorithms, Part Iというコースで、高速なRandomized Queueを実装するという話題があったので、試しに作ってみた。

高速なRandomized Queueとは

Randomized Queueとは、Queueからdequeueするときに、中に入っている要素の中からランダムに一要素取り出すようなQueueである。

また「高速な」とは、enqueue、dequeue、isEmpty、sizeなどの操作の実行時間が、"constant amortized time"であること、つまり何回も操作を繰り返していくと、平均的には定数時間でそれぞれの操作が終わるということである。

この二つを満たすものを高速なRandomized Queueと呼ぶ。

実装

高速なRandomized Queueを実装すると次のようになった。

import java.util.NoSuchElementException;

public class RandomizedQueue<Item> {
  private Item[] queue;
  private int N;

  public RandomizedQueue() {
    N = 0;
    queue = (Item[]) new Object[1];
  }

  public boolean isEmpty() {
    return N == 0;
  }

  public int size() {
    return N;
  }

  public void enqueue(Item item) {
    // queueのサイズが足りなくなったら配列を2倍にする
    if (N == queue.length) this.resize(2 * queue.length);
    queue[N++] = item;
  }

  public Item dequeue() {
    if (this.isEmpty()) {
      throw new NoSuchElementException();
    }

    // ランダムな位置から要素を取り出し、queueの最後の要素をその位置に移動する
    int i = (int) (Math.random() * N);
    Item item = queue[i];
    queue[i] = queue[N - 1];
    queue[N - 1] = null;
    N--;

    // queueのデータ量が、queueの最大長の1/4以下になったらqueueを1/2に縮める
    if (0 < N && N <= queue.length / 4) this.resize(queue.length / 2);

    return item;
  }

  private void resize(int capacity) {
    Item[] newQueue = (Item[]) new Object[capacity];
    for (int i = 0; i < N; i++) {
      newQueue[i] = queue[i];
    }
    queue = newQueue;
  }
}

今回の実装で注目するところは以下の二点。

dequeue操作が定数時間になるために配列を利用する
利用者側が配列の長さを意識しなくて良いように、うまく内部でresizeする

dequeue操作が定数時間になるために配列を利用する

よくあるQueueの実装のときはLinkedListのような構造を使うことが多い。しかしLinkedListで実装した場合、dequeueがランダムに要素を取り出すという仕様だと、取得したい位置までLinkedListを辿る操作が必要となってくる。すると辿る操作はQueueのサイズNに比例する時間がかかるため、O(n)の実行時間となってしまう。

今回はdequeue操作もO(1)で行わなければならないので、LinkedList構造は使えない。そのため、内部では配列を利用することになる。

利用者側が配列の長さを意識しなくて良いように、うまく内部でresizeする

Queueの内部実装で配列を使う場合、今持っている配列の長さ以上にデータをenqueueされた時に配列を拡張する必要がある。これもうまくやらないとO(1)の計算量とならない。

今回は次のように配列の拡張・縮小を行った。

配列の長さ以上にenqueueされたら、内部の配列の長さを2倍に拡張する
dequeueが続き、今の配列の長さの1/4しかデータが入ってない状態になったら、内部の配列の長さを1/2に縮小する

enqueueで2倍に拡張する瞬間はO(n)の計算量が発生するが、それでもenqueueを続けていくと平均的にはO(1)の計算量になるらしい。詳しくはCourseraを見てほしい。

また、1/4しかデータが入っていない時に配列の長さを1/2にする理由は、スラッシングの防止のためである。「配列に1/2しかデータが入っていない状態になったら長さを1/2にする」という実装にしてしまうと、ちょうど1/2のデータ量の時にenqueue, dequeue, enqueue, dequeue, ...と交互に繰り返すと毎回resizeが発生してしまい遅くなってしまう。しかし、今回のような縮小方法にすれば、そのようなときでもresizeがたくさん発生することはない。

ちなみにこのように内部的に長さを2倍にしていくような実装は色んな所で見られるらしい。あまり良く知らないけど、Golangのスライスの実装もこういう風になっているみたいだし、確かLinuxのメモリの確保とかもこんな感じだった記憶がある。

まとめ

今回はCourseraで出てきた高速なRandomized Queueというのを試しに実装してみた。こういう風な簡単な構造でもなかなか考えることが多いし、また他の場所で使われているような配列の拡張のような仕組みが学べて面白かった。

$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

初めて学ぶ知識をどのように学習しているか

「理論から学ぶデータベース実践入門」読んだ

高速なRandomized Queueのアルゴリズムを実装する

高速なRandomized Queueとは

実装

dequeue操作が定数時間になるために配列を利用する

利用者側が配列の長さを意識しなくて良いように、うまく内部でresizeする

まとめ

関連