dackdive's blog

新米webエンジニアによる技術ブログ。JavaScript(React), Salesforce, Python など

「みんなのデータ構造」学習メモ:2.4 ArrayDeque

引き続き、「みんなのデータ構造」という本を読む。
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート

amazon

みんなのデータ構造

みんなのデータ構造

  • 作者:Pat Morin
  • 出版社/メーカー: ラムダノート
  • 発売日: 2018/07/20
  • メディア: 単行本(ソフトカバー)

これまでのメモ

今回は「P35. 2.4 ArrayDeque 配列を使った高速な双方向キュー」。

TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ArrayDeque.ts

メモ

ArrayDeque とは

f:id:dackdive:20200121014052p:plain:w320

  • ArrayStack、ArrayQueue と同じく、List インターフェースを実装したデータ構造の1つ
  • 両端に対しての追加と削除が効率的にできるデータ構造

ArrayDeque の実行時間

  • get(i)および set(i, x) の実行時間は O(1)
  • add(i, x) および remove(i) の実行時間は O(1 + min{i, n - i})
    • resize() を考慮しても、 resize() の実行時間は m 回の操作で O(m) なので、O(1 + min{i, n - i})

ArrayDeque の考え方

基本的にはArrayQueueと同じ。循環配列を用いる。

ArrayQueue との違いとして、ArrayDeque では配列の 両端から 要素の追加と削除を効率よく実行できる必要がある。
これを実現するため、 add(i, x) および remove(i) では、 i < n / 2 かどうかを確認する。
つまり、追加/削除しようとしている場所が、配列全体の左半分なのか右半分なのかで場合分けする。

i < n / 2 の場合、配列の左端から i 個の要素を1つずつ左にずらす。
そうでない場合、配列の i 番めから右端までの n - i 個の要素を1つずつ右にずらす。

f:id:dackdive:20200122005243p:plain

f:id:dackdive:20200122005246p:plain

こうすると、 add(i, x) または remove(i) における操作の回数は min{i, n - i} となる。
i = 0 のときも i = n のときも操作回数が少なく済むことがわかる。


疑問など

f:id:dackdive:20200122010239p:plain

add/remove のサンプルコード内のコメント、実際には a[0],... ではなく a[j % a.length],... な気がする。