💨

TypeScriptでFIFO Queueを作る

2024/03/04に公開

JavaScript

JavaScript（およびそれにトランスパイルされるTypeScript）にはキューやスタックなどのデータ構造がありません。配列型としてArrayがありますが、Array.prototype.pushとArray.prototype.shiftでキューの代わりにする場合は注意すべき点があります。

JS/TSのArrayは配列ではない

配列というと、メモリ上に値が並んでいるものを思い浮かべる人が多いでしょう。実際ちょっとググればそういう説明が出てきます。しかしJS/TSの配列は実はMapに近いものとなっています。

このことを詳しく見るために、ECMAScriptの仕様書を見てみましょう。JavaScriptとECMAScriptの関係についてはここでは深掘りしないので、気になる人はググってください。
https://tc39.es/ecma262/multipage/
見るべき箇所は13.3.2 Property Accessorsです。

最初のMemberExpression [ Expression ]の項を見ると、EvaluatePropertyAccessWithExpressionKeyというabstruct operationを実行しています。この定義を読むと、[]の中に書いたキーの値をゴニョゴニョしたあとにToPropertyKeyというabstruct operationを実行しています。さらにこの定義を読むと、ざっくり次のように書かれていることがわかります。

keyがプリミティブでない場合、文字列に変換せよ
keyがシンボルなら、その値をそのままreturnせよ
keyを文字列に変換したものをreturnせよ

つまり、JS/TSの配列でarr[idx]のようなアクセスをしたときには、まずidxを文字列に変換してからその文字列をプロパティ名としてアクセスしたことになります。従って次のようなコードもちゃんと動きます。

sample.ts

const arr = ['foo', 'bar']
// @ts-ignore
arr[{}] = 'baz'
console.log(arr)

ターミナル

$ deno run sample.ts
[ "foo", "bar", "[object Object]": "baz" ]

余談ですが、ここまでの話は配列に限定されないので、JS/TSのほとんどの値は[]でそのプロパティにアクセスできます。

console.log(3['toString'])
// [Function: toString]

なぜそれに注意すべきなのか

キューに対する操作は

最後尾に要素を付け足す（push）
先頭の要素を取り除く（pop）

の2種類があります。一見これは

push: Array.prototype.push
pop: Array.prototype.shift

によって実現できそうな気がします。実際に書いてみると動くことは動くのですが、要素数が増えるとpop操作は遅くなります。
例えば、次のコードを実行すると、僕の環境では1250〜1280くらいの値が出力されます。

const arr = []
const n = 100000
for (let i = 0; i < n; ++i) {
  arr.push(true)
}
const t1 = Date.now()
for (let i = 0; i < 100000; ++i) {
  arr.shift()
  arr.push(true)
}
const t2 = Date.now()
console.log(t2 - t1)

次に、nの値を10倍して1000000にして実行してみると、僕の環境では12400〜12600くらいの値が出力されます。時間を計測している部分のコードは一切変わらないのに、です。

これはArrayが内部的にMapのような実装になっているためです。pop操作によって先頭の要素が取り除かれると、配列の全ての要素に対してkey-valueの結びつきをずらさねばなりません。Array.prototype.shiftの仕様を確認すると、実際にそのように定義されていることが確認できます。

ではどうするのか

先頭の要素をpopしても添え字が変わらないようにします。具体的にはリングバッファのようなことをします。

queue.ts

export class Queue<T> {
  private value: T[] = []
  private start: number = 0
  private __size__: number = 0

  constructor(capacity = 100) {
    this.value = Array.from({ length: capacity })
    this.__size__ = 0
  }

  push(item: T) {
    const idx = (this.start + this.__size__) % this.value.length
    if (this.value.length === this.size) {
      this.value = this.value.slice(idx).concat(this.value.slice(0, idx)).concat([item])
      this.start = 0
    } else {
      this.value[idx] = item
    }
    this.__size__ += 1
  }
  pop() {
    if (this.__size__ === 0) {
      throw new Error('empty queue')
    }
    const ret = this.value[this.start]
    // delete this.value[this.start]
    this.start = (this.start + 1) % this.value.length
    this.__size__ -= 1
    return ret
  }
  peek() {
    if (this.__size__ === 0) {
      throw new Error('empty queue')
    }
    return this.value[this.start]
  }
  get size() {
    return this.__size__
  }
}

popメソッドでdelete this.value[this.start]がコメントアウトされていますが、ここは実際の使われ方に応じてコメントアウトを外したり外さなかったりすることを想定しています（constructorの引数で設定できるようにしてもいいですが）。
deleteを逐一する方がメモリ消費量を抑えられる可能性があります（必ず抑えられるわけではなく、popした値がどこか別の場所から参照可能であり続ける場合は無意味です）が、動作が遅くなります。

この実装は以下のテストをパスします

import { assertEquals } from 'https://deno.land/std@0.218.0/assert/mod.ts'
import { assertThrows } from 'https://deno.land/std@0.218.0/assert/assert_throws.ts'
import { Queue } from './queue.ts'

Deno.test({
  name: 'queue test',
  fn() {
    const queue = new Queue<string>(10)
    assertEquals(queue.size, 0)
    queue.push('foo')
    queue.push('bar')
    queue.push('baz')
    assertEquals(queue.size, 3)
    assertEquals(queue.peek(), 'foo')
    assertEquals(queue.pop(), 'foo')
    assertEquals(queue.peek(), 'bar')
    assertEquals(queue.size, 2)
    queue.pop()
    queue.pop() // now queue is empty
    assertThrows(() => queue.peek())
    assertThrows(() => queue.pop())
  }
})

また、先ほどと同様の処理にかかる時間を測定すると、

import { Queue } from './queue.ts'

const n = 1000000
const q = new Queue(n)
for (let i = 0; i < n; ++i) {
  q.push(true)
}
const t1 = Date.now()
for (let i = 0; i < 100000; ++i) {
  q.pop()
  q.push(true)
}
const t2 = Date.now()
console.log(t2 - t1)

僕の環境ではnが100000でも1000000でもほぼ毎回1が出力されます。
deleteを逐一する場合、nが1000000のとき出力が3程度になります。
いずれの場合も、Arrayのメソッドをそのまま使う場合に比べて大幅に高速化されています。
ちなみにnを1000000としたまま繰り返しの回数を100倍にすると、deleteしない場合38〜39、deleteする場合210〜220くらいの値が出力されます。

まとめ

JS/TSのArrayのメソッドをそのまま使ってキューの代わりにする場合、要素数によっては処理が遅くなることを確認し、またその原因を仕様書から読み解きました。
本来のキューと同様にpop/pushが定数時間で行えるQueueクラスを実装し、大幅な高速化を実現しました。
それでは、よいTypeScriptライフを。

JS/TSのArrayは配列ではない

なぜそれに注意すべきなのか

ではどうするのか

まとめ

Discussion