C# で Deque を自作する

🎅 𝑴𝒆𝒓𝒓𝒚𝑪𝒉𝒓𝒊𝒔𝒕𝒎𝒂𝒔 !!

この記事は、[C# Advent Calendar 2023](https://qiita.com/advent-calendar/2023/csharplang) の25日目です。

# はじめに

**Deque** とは、両端キュー (**D**ouble-**e**nded **Q**ueue) のことであり、スタックとキューの両方の性質を併せ持つコンテナを指します。

一般的に両端キューは、任意の要素へのアクセスと、先頭と末尾の両方からの追加・削除を定数時間で行うことができます。

競プロで使われることも多々あるような、非常に便利なコンテナです。

# LinkedList&lt;T&gt; は代用に向いていない

実は .NET には `LinkedList<T>` という、双方向連結リストが用意されており、これが (一応) 両端キューの代用になります。

しかし、双方向連結リストと両端キューにはその特性に大きな違いがあります。
以下の表に列挙してみます。

:::note warn
ここで示す計算量は、一般的な実装をした場合の計算量であり、実装によっては異なる場合があります。
:::

|         比較内容         | 双方向連結リスト | 両端キュー |
| :----------------------: | :--------------: | :--------: |
|   先頭からの追加・削除   |      $O(1)$      |   $O(1)$   |
|   末尾からの追加・削除   |      $O(1)$      |   $O(1)$   |
| 任意の位置への追加・削除 |      $O(1)$      |   $O(N)$   |
|  任意の位置へのアクセス  |   $O(N)$ [^1]    |   $O(1)$   |

[^1]: 要素への参照を保持している場合、それを用いればアクセスは定数時間となります。しかし、任意の要素への参照を持っているとは考えづらいので、ここでは先頭もしくは末尾からのシーケンスアクセスを想定しました。

これを見ると分かる通り、双方向連結リストではランダムアクセスができず、両端キューに劣ります。

また、 `LinkedList<T>` では、要素を参照型 (`LinkedListNode<T>`) でラップしているため、要素の追加ごとにヒープアロケーションが走ってGCに負荷がかかったり、メモリ領域を両端キューより多く消費するといった問題点があります。

もちろん、双方向連結リストの方が勝る部分もありますが、両端キューの代わりとして使用するのには向いていなさそうです。

# 使用するアルゴリズム

動的に確保した配列の中に、要素を連続して並べて扱う方法を用います。

なお、別の方法としては、この配列を輪のように扱うといったものもあります。

## 両端への要素の追加

この操作のアルゴリズムは比較的単純で、動的に確保した配列に対して、中央から両端に向かって要素を埋めていくというものです。

以下の例では、要素数7の配列 (連続したメモリ領域) に対して、先頭への追加と末尾への追加を2回ずつ行っています。

![push.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1299544/25fa55c8-be8c-6361-9b51-daf506061349.png)

## 両端からの要素の削除

両端からの要素の削除は比較的簡単で、単に要素を削除するのみです。

## 配列の拡張

配列の空きがなくなってしまった際には、要素数を2倍にした新しい配列を確保し、そこに要素をコピーします。

この際、元あった要素が中央に来る (左右にほぼ均等に空き領域がある) ように位置を調整します。

以下の例では、要素数4の配列から要素数8の配列へのコピーと、要素の位置調整を行っています。

![expand.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1299544/6f58bc93-1bf2-3e59-dac8-e6cd45989216.png)

# 実装

今回作成する `Deque<T>` クラスは、両端への要素の追加・削除およびランダムアクセスのみの実装とします。

```cs
public partial class Deque<T>
{
    // 格納されている要素の数
    // (_items.Length とは異なる)
    private int _count = 0;

    // 要素を格納する配列
    private T[] _items;

    // キューの先頭の要素の位置
    // (実際に要素が格納されている部分の前後に空白を設けているため, これが必要)
    private int _head;
}
```

## 配列の拡張

要素を格納する配列のサイズを倍にする `Grow` メソッドを実装します。

この時、配列の両端に同じくらいの空きができるように、要素の位置を調整します。

```cs
public partial class Deque<T>
{
    private void Grow()
    {
        int newCapacity = int.Clamp(_items.Length << 1, 1, Array.MaxLength);
        int frontExtraCapacity = (newCapacity - _count) >> 1;

        if (frontExtraCapacity == 0)
        {
            throw new Exception(); // 配列の長さが上限に到達
        }

        T[] newArray = new T[newCapacity];
        Array.Copy(_items, _head, newArray, frontExtraCapacity, _count);
        _items = newArray;
        _head = frontExtraCapacity;
    }
}
```

## インデクサ

```cs
public partial class Deque<T>
{
    public T this[int index]
    {
        get {
            if (index < 0 || _count <= index)
            {
                throw new ArgumentOutOfRangeException(nameof(index));
            }
            return _items[_head + index];
        }

        set {
            if (index < 0 || _count <= index)
            {
                throw new ArgumentOutOfRangeException(nameof(index));
            }
            _items[_head + index] = value;
        }
    }
}
```

## 両端への要素の追加

```cs
public partial class Deque<T>
{
    public void PushBack(T item)
    {
        int index = _head + _count;

        if (index == _items.Length)
        {
            Grow();
            index = _head + _count; // Grow() によって _head の値が変化するため
        }

        _items[index] = item;
        _count++;
    }

    public void PushFront(T item)
    {
        if (_head == 0)
        {
            Grow();
        }

        _head--;
        _items[_head] = item;   // 1行上の文と纏めて `_items[--_head] = item` でも可
        _count++;
    }
}
```

## 両端からの要素の削除

`T` が参照型であればその参照を切ります。

一方で、`T` が値型であれば配列に変更は加えず、先頭の位置や要素数を変更するだけでOKです。

```cs
public partial class Deque<T>
{
    public T PopBack()
    {
        if (_count == 0)
        {
            throw new InvalidOperationException();
        }

        _count--;

        item = _items[_head + _count];
        if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        {
            // 参照を切る
            _items[_head + _count] = default!;
        }

        return item;
    }

    public T PopFront()
    {
        if (_count == 0)
        {
            throw new InvalidOperationException();
        }
        
        _count--;
        _head++;

        item = _items[_head];
        if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        {
            // 参照を切る
            _items[_head] = default!;
        }

        return item;
    }
}
```

これで基本的な部分の実装は終わりました。

あとはインターフェースを実装したり、便利なメソッドを入れたりすれば完成です。

# ベンチマーク

## 追加のみ

両端への追加をランダムに20万回行うプログラムを計測した結果は以下の通りです。

|     Method      |      Mean |     Error |    StdDev | Allocated |
| :-------------: | --------: | --------: | --------: | --------: |
|   `Deque<T>`    |  1.171 ms | 0.0100 ms | 0.0093 ms |   2.00 MB |
| `LinkedList<T>` | 17.459 ms | 0.2884 ms | 0.2698 ms |  18.31 MB |

## 追加・削除

20万回も追加し続けることなんてあまりない気がするので、今度はもう少し実用的な条件下で計測しました。

両端への追加と削除をランダムに20万回行うプログラムを計測した結果は以下の通りです。

|     Method      |      Mean |     Error |    StdDev |   Allocated |
| :-------------: | --------: | --------: | --------: | ----------: |
| `Deque<T>`      |  1.533 ms | 0.0058 ms | 0.0054 ms |     8.24 KB |
| `LinkedList<T>` | 13.594 ms | 0.2109 ms | 0.1973 ms | 14071.25 KB |

Deque の方はメモリ使用量がやけに少ないですが、これは良い具合に追加と削除が交互に入って、配列のサイズが膨れ上がらなかったと推測されます。

一方で LinkedList の方は、要素が参照型であるために、要素を削除してもゴミとして溜まり続けていたと推測されます。

このゴミはGCが走れば回収されますが、その処理も Deque よりかなり高負荷になるかな...と思います。

## おわりに

.NET のライブラリはかなり充実してると思うのですが、なぜ Deque は無いんでしょうか......

ちなみに、おそらく一番使われているであろう有志のライブラリ、 `Nito.Collections.Deque<T>` ([GitHub](https://github.com/StephenCleary/Deque)) でも同様に計測してみましたが、自前のものと結果はほとんど変わりませんでした。