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

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

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

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

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

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

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

• サービス終了のお知らせ
• サービス終了のお知らせ

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

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

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というのを試しに実装してみた。こういう風な簡単な構造でもなかなか考えることが多いし、また他の場所で使われているような配列の拡張のような仕組みが学べて面白かった。

関連

• Algorithms, Part I
• 中置記法の数式文字列から計算結果を求める操車場アルゴリズム - $shibayu36->blog;
  • Courseraの2週目でStackの応用例で出てきたものを実装したやつ

どのようにエンジニアの目標設定を行うか

以前 ゴールを決め目標を決める・解決案ではなく質問する - コーチングの学習で学んだこと - $shibayu36->blog; で、「ゴールを決め、現在位置とのギャップを考え、目標を決める」と良いということをまとめた。イメージとしては以下の図の通り。

しかし、前回の記事だと具体的にどのようにエンジニアの目標設定を行うかイメージが湧かない。そこで、もう少し具体的に最近どのようにやっていたかを書いてみたいと思う。

僕がメンティーと目標設定を行うときは、以下のフローを辿っている。

• なんでも良いのでゴールのイメージを明確にする
• 現在の自分とゴールのイメージのギャップを考える
• ギャップを埋める目標を考え、アクションを定める

ちなみに今回は、チームの成果達成のために個人の目標を決めるのではなく、エンジニアのスキル向上の目標を立てるという前提で書いていく。

なんでも良いのでゴールのイメージを明確にする

まずはいろんな質問や会話をしながら、メンティーが今後どうなっていきたいかなどのゴールイメージを明確にする。

この時に僕はよく以下のような質問をしている。

• 2~3年後にどういうエンジニアになりたいか(なりたい姿を決める)
• 1年後にどういう仕事をしていたいか(やりたいことを決める)
• 最近自分が課題に感じていることあるか(課題を明確をする)
• 自分がこの半年でどういうことやりそうか やる予定のことを明確にする

もし長い目線で考えることが得意そうな人なら、「2~3年後にどういうエンジニアになりたいか」のような質問をし、なりたい姿を明確にしていく。エンジニア像はどういう決め方でも良く、例えばビジネスも分かる・チームを率いることができる・専門スキルが突出しているなどの能力ベースで話しても良いし、社内のこの人・社外のこの人みたいな誰になりたいかベースで話しても良い。

なりたいエンジニア像がはっきりしない場合、次は「1年後にどういう仕事をしていたいか」という質問をし、やりたいことを明確にしていく。例えば、3人くらいのチームを率いるようなリーダーの仕事をしていたいとか、機械学習のスキルを活かせる仕事をしていたいとか、フロントエンドよりの仕事をしていたいとか、そのようなものがありえるだろう。

やりたいことがはっきりしない場合、次は「最近自分が課題に感じていることあるか」という質問をし、メンティーが今感じている課題を明確にする。例えば最近自分の成長が鈍化しているのような自分に対する課題や、社内でデータベースの知識があまり共有されていないのような周りを見た時の課題などがありえるだろう。

課題もあまりなければ、次は「自分がこの半年でどういうことやりそうか」という質問をし、これからやる予定のことを明確にする。例えば、この半年は新サービスの立ち上げをやりそうとか、パフォーマンスが重要な仕事をしそうとか、そういうものがありえるだろう。

このあたりの質問をしていき、「なりたい姿・やりたいこと・課題・これからやること」のどれかが明確になれば、それをひとまずのゴールにできる。ゴールの例としては

• なりたい姿 : 2~3年後にこの人のようになる
• やりたいこと : 1年後にこの仕事をやっている
• 課題 : 半年後にこの課題が解決している
• これからやること : 半年後、○○というタスクをうまくやり遂げている

例えば機械学習の得意なエンジニアと目標設定をするなら

• 2~3年後にどういうエンジニアになりたいか
  • 専門スキルの機械学習を発揮し続けられるようなエンジニア

のように、ゴールを決められるだろう。

これでひとまず簡単なゴールを決めることが出来た。

現在の自分とゴールのイメージのギャップを考える

ゴールイメージが明確になると、現在の自分との比較ができるようになる。そこで続いては、現在の自分とゴールイメージとのギャップを聞いていく。質問例としては以下のようなものがある。

• 2~3年後にこの人のようになるために、自分は今どのようなスキルが足りていないのか
• 1年後にこの仕事をやっているためには、どのようなことが必要か
• 半年後にこの課題を解決するために、どのようなことが必要か
• ○○というタスクをうまくやり遂げるために、どのようなスキルが必要か

先程例に挙げた「専門スキルの機械学習を発揮し続けられるようなエンジニアになりたい」というゴールの場合

• 専門スキルの機械学習を発揮し続けられるようなエンジニアになるために、どのようなスキルが足りていないか
  • 機械学習のスキルを発揮するには、まずベースとなるアプリケーション開発技術が必要
  • しかし、まだサーバーサイドからフロントエンドまで一貫して自分一人で開発はできていない
  • これまでサーバーサイドは行えているが、フロントエンドの経験はほぼない
  • そこで、フロントエンドもある程度できるようにする必要があるのではないか

のように会話していくと、「一機能をサーバーサイドからフロントエンドまで一貫して自分で開発できるスキルがない。特にフロントエンド。」といったギャップが見えてくる。

これでゴールと現在位置とのギャップを明確にできた。

ギャップを埋める目標を考え、アクションを定める

ゴールとギャップが明確になったので、あとはゴールに必要なギャップのうち一つ(もしくは複数)を選び、目標とそれを達成するためのアクションに落とし込むと良い。

僕は基本的に、今後その人が自分で考えていろんなアクションを取れるように、目標の方は柔軟に捉えられるようにしている。逆にアクションの方はかなり具体的になるように、「SMART」の法則で作っている。「SMART」というのは、具体的(Specific)で、計測できて(Measurable)、達成可能で(Achievable)、現実的で(Realistic)、期限が明確である(Timed)というものだ。

例えば先程の、「一機能をサーバーサイドからフロントエンドまで一貫して自分で開発できるスキルがない。特にフロントエンド。」というギャップがあるなら、例えば以下のような目標とアクションを作ることができるだろう。

• 目標: 半年後までにサーバーサイドからフロントエンドまで含めて一機能を作る経験をする
• アクション1: 1か月後までに、使っているJSフレームワークのAngularJSの知識を付けるため、それについて書かれた書籍を最低1冊読む
• アクション2: 2か月後までにAngularJSを使ってTODOアプリのような簡単なアプリケーションを一つ作る
• アクション3: 上司にフロントエンドの技術を学んだことを伝え、大きめな一機能を上から下まで担当させてもらえるよう提案する
• アクション4: 半年後までに、任された一機能をやり遂げる

これで目標と、それに対応するアクションプランを決めることが出来た。

まとめ

今回は、自分がエンジニアの目標設定の面談をどのように進めているかについて具体的にまとめてみた。もちろん場合場合によってやり方は変えるのだけど、基本的には今回のような考え方でやっている。他にもやり方があれば教えてもらえればと思う。

参考

• ゴールを決め目標を決める・解決案ではなく質問する - コーチングの学習で学んだこと - $shibayu36->blog;
• SMARTの法則 （スマートの法則）
• 目標設定の5つのポイント「SMART」とは？【フレームワーク解説／意味・具体的な使い方】 | GLOBIS 知見録