読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

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

関連

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

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

f:id:shiba_yu36:20161023134206j:plain:h250


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


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

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

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

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

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


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

  • 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: 半年後までに、任された一機能をやり遂げる


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

まとめ

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

「事業成長にコミットするエンジニア組織への道のり」スライドのメモ

非常に良かった記事とかを見た時、これまではEvernoteにメモを残していたのだけど、よく考えたら別にブログに公開しておけば良いよなと思ったので公開してみる。

今回は「事業成長にコミットするエンジニア組織への道のり」というのが良かったのでメモ。

エンジニアを社内に構える意味は

  • 売上最大化あるいは利益最大化させること
  • 事業成長に負けないように技術的な挑戦をすること

これを見て、確かに技術グループの役割は技術で売上や利益を最大化しつつ、成長する事業をさらに成長させるための技術力を着ける責任を持つということだなーと思った。

事業会社におけるエンジニア像

  • 技術で課題を解決する人
  • プロダクト志向で開発をする人

エンジニアにとっても技術は手段と考え、課題解決が出来ているかと問い続けなければならない。

スプリンタータイプとマラソンタイプ

  • スプリンタータイプ: フロント寄り。高速開発やCVR寄与を目的
  • マラソンタイプ: バックエンド、インフラ寄り。高難易度案件で価値を発揮する

エンジニアの風林火山とかあったけど、この区分も面白い。僕はマラソンタイプ。

短期成長のために中期視点が抜けた場合、導くのはエンジニアの役割

事業が成長しているのに、技術的に成長していなかったときにどこかでつまづく話。短期成長と中期視点という考え方で技術的負債とか言語選択とかそういうタスクを考えていきたい。

組織マネジメントとはひとりひとりが輝ける場所を定義すること
すべてがゴール = 多様性を許容

むっちゃ良い。事業の課題と個人のやりたいことをうまくすり合わせられるように心がけたい