C# で Deque を自作する

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

この記事は、C# Advent Calendar 2023 の25日目です。

はじめに

Deque とは、両端キュー (Double-ended Queue) のことであり、スタックとキューの両方の性質を併せ持つコンテナを指します。

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

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

LinkedList<T> は代用に向いていない

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

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

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

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

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

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

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

使用するアルゴリズム

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

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

両端への要素の追加

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

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

両端からの要素の削除

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

配列の拡張

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

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

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

実装

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

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

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

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

配列の拡張

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

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

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;
    }
}

インデクサ

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;
        }
    }
}

両端への要素の追加

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です。

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) でも同様に計測してみましたが、自前のものと結果はほとんど変わりませんでした。

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