Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

D言語にもDequeがほしい!

Dequeとその実装の話

Dequeについて

dequeは、double-ended queue(両端キュー)の略で、次のような操作ができるデータ構造のことです。

  • insertFront(value): 先頭への値の追加
  • insertBack(value): 末尾への値の追加
  • removeFront(): 先頭の値の削除
  • removeBack(): 末尾の値の削除

先頭・末尾に対して、値の追加・削除ができます。

定番の実装方法は次の2つ。

1. 双方向連結リスト(doubly linked list)による実装

  • 先頭・末尾の値の追加・削除がO(1)
  • 途中の値の追加・削除が(参照をすでに持っていれば)O(1)
  • 要素へのランダムアクセスがO(n)

2. 動的配列による実装

  • 先頭・末尾の値の削除がO(1)
  • 先頭・末尾の値の追加がamortized O(1)
    • 基本的にO(1)だけど、メモリの再割り当て等で最悪計算量はO(n)
  • 途中の値の追加・削除がO(n)
  • 要素へのランダムアクセスがO(1)

競プロで単にdequeと言ったら動的配列の方のdequeを指すことが多い気がする。ぐぐったらarray dequeと言うらしい。

C++だと、双方向連結リストバージョンがstd::listで、動的配列バージョンがstd::dequeですかね。

で、D言語だとstd.container.dlistで双方向連結リストはあるけどarray dequeがない・・・(たぶん)

競プロで必要になってきたので実装しました。

実装方法

wikipediaによればarray dequeの実装方法は次の3つがあるみたい。

  1. リングバッファ(circular buffer)による実装。バッファが一杯になると領域を増やす。
  2. 動的配列を一つ用いる。配列の中心から前方・後方へキューの値を割り当てて、どちらか一方の端までいけば、サイズのより大きい配列へ再割り当てを行う。
  3. 小さな(静的)配列をポインタとしてもつ動的配列を用いる。値の追加にて、確保していた領域の先頭or末尾にいけば、新たな配列を加える。

3の実装、ページング方式みたいでおもしろい。C++std::dequeはこの実装方法が使われてるみたい(ちゃんと確かめてないので違ってるかも)

今回は2の方法を拡張して次のような実装をしました。

  • 動的配列を2つ使う。frontDatabackDataとする。
  • 前方に値が追加されればfrontDataを伸ばしていく。逆に後方に値が追加されればbackDataを伸ばしていく。
  • つまり内部のデータを1つの配列に変換するとfrontData.retro.array ~ backDataとなる。

領域の再割り当てなどの実装を手動でやるのが面倒だったのでD言語の動的配列の恩恵を授かろうというあれ。

D言語の動的配列は拡大するとき、連続した次のヒープ領域が空き領域ならばO(1)、空き領域じゃなかったら配列全体をコピーして別の領域に再割当てするのでO(n)となります。よって、末尾への値の追加はamortized O(1)と思っていいんじゃないかな(適当)。

なので、上記のような単純な実装で大丈夫っしょという軽い気持ちで実装することにした。

ソースコード

下の方にunittestを書いてるのでだいたい使い方はわかると思う。
opSliceopIndexAssignとかの演算子オーバーロードをしたことがなかったので少し勉強になった。

ARC 077 C - pushpush

dequeを使うちょうど良さそうな問題があったので提出したらまともな速度が出たので実用上問題なさそう(ちなみにこの問題はdoubly linked listで機能的に十分なので例としては微妙)

Submission #1935099

その他

これ、ジャッジサーバーのコンパイラのバージョンが古いからかわからないけどなぜかコンパイルエラーが出る。UFCSを使わずに書くと通ったけどなんでエラーが出るんだろう・・・

参考文献