連結リスト(LinkedList)の使い所

こんにちは。技術部平山です。 今回は地味ネタです。図すらありません。

私は一年に何回か、連結リスト(線形リスト、とも) を使いたくなる時があります。 基本的なデータ構造として教科書には必ず載っていますが、 その割に使っている方が少ない印象を受けます。

この記事では、「こんな時に使えるよ」という使い所を具体的に紹介しようと思います。

99%配列か辞書

Unityに限らず、私が今までプログラムを書いてきた感じ、 配列か辞書があれば99%は足ります。

ここで言う「配列」は広い意味の配列でして、C#であれば List も含みます。数が不定ならList、固定なら(狭い意味の)配列、というのが良い使い分けでしょう。

辞書は主にDictionary ですが、 キーだけあれば良いケースでは HashSet も辞書の一種と考えて良いでしょう。 さらに、キーでforeachした時に特定の順番で出てきてほしい、という時には、 SortedDictionary を使いますが、これも辞書の一種です。検索、挿入、削除の3操作をO(logN)以下でできるデータ構造は、全て辞書として扱えます。

SortedDictionary(中身は探索木)は最も高機能ですので、微妙な速度の差が気にならないなら、 辞書に全てSortedDictionaryを使ってもさしたる問題はありません。5倍遅くなることはないでしょう。 それどころか、全ての配列を辞書に置き換えても、それほど性能は落ちません。10倍遅くなることはないでしょう。 その意味で、辞書は最強のデータ構造である、と言えます。

しかしその最強のデータ構造でも足りない時があるのです。

具体例

今AssetBundleがらみのライブラリを作っているのですが、 ダウンロードに関する処理で以下のような処理があります。

  • ダウンロード項目には「ダウンロード中」と「ダウンロード待ち」と「ダウンロード済み」の3種類がある。
  • 「ダウンロード中」の項目は最大数を固定とし、毎フレーム状態を監視する。終わっていたら「ダウンロード済み」に移す。最も古い「ダウンロード待ち」を「ダウンロード中」に移す。
  • 「ダウンロード待ち」の間に不要になった場合は、「ダウンロード待ち」から削除する。

さてどんなデータ構造を用意しましょうか。

まず、3種類とも同じ型なのであれば、種別問わず辞書に入れておくと便利ですね。 名前で引けば出てきます。

Dictionary<string, Item> _items;

Itemという型にダウンロード状態が入っているとしました。stringがキーの辞書なので名前で検索したり、 消したりできます。

次に、「ダウンロード中」は毎フレーム全部監視するので固定の配列を別に用意しましょう。 これをforで毎フレーム回して中にあるUnityWebRequestを監視します。 毎フレームやっても8個や16個なら負荷は問題になりません。

Item[] _goingItems;

「ダウンロード済み」は、実のところ何も仕事がないので、何も用意しません。 「ダウンロード中」でも「ダウンロード待ち」でもないものが「ダウンロード済み」 でいいでしょう。

「ダウンロード待ち」のデータ構造

さて、問題は「ダウンロード待ち」を何で表現するかです。 とりあえず、先に処理を考えてみましょう。

  • 「ダウンロード中」の項目は最大数を固定とし、毎フレーム状態を監視する。終わっていたら「ダウンロード済み」に移す。最も古い「ダウンロード待ち」を「ダウンロード中」に移す。

をコードにすれば、

for (int i = 0; i < _goingItems.Length; i++)
{
    if (_goingItems[i].done)
    {
        _goingItems[i] = ダウンロード待ちの先頭;
        _goingItems[i].StartDownload();
        ダウンロード待ちの先頭を削除;
    }
}

こんな感じでしょうか。「ダウンロード中」のi番が終わっていれば、 そこに「ダウンロード待ち」から一つ取ってきて移し、 ダウンロードを開始します。 そして、「ダウンロード待ち」の先頭は削除します。

ここだけ見れば、「ダウンロード待ち」は キュー で良いかな、という気がします。先に頼んだものは先に処理したいですから、 順番は守ってほしいわけです。 標準ライブラリのQueue の中身は配列ですが、「先頭からしか削除できず、末尾にしか追加できない」という機能制限が加わって使いやすくなったものです。 Listや配列でもいいですが、バグって途中をいじる危険を排除してコードを短くしたければ、Queueを使うのは良い考えと言えます。

しかし、

  • 「ダウンロード待ち」の間に不要になった場合は、「ダウンロード待ち」から削除する。

が問題です。どれが消されるかわからないので、 途中が見えないキューでは困ります。 仕方なく配列にしましょう。 しかし、配列で途中を消すのは泣くほど遅い処理です。

//List<Item> _waitingItems; が定義されていると考えて

int to = 0;
for (int i = 0; i < _waitingItems.Count; i++)
{
    _waitingItems[to] = _waitingItems[i];
    if (_waitingItems[i].name != cancellingName)
    {
        to++;
    }
}
_waitingItems.RemoveRange(to, _waitingItems.Count - to);

配列から検索しながら削除する、といえば、だいたいこうなります。 List.RemoveAll(Predicate) の中身はたぶんこんなです。

to(コピー先)なる変数を用意して、to番にi番をコピーしながらループします。 toは消さない要素であれば++し、消す要素なら++しません。 最後に個数を減らすRemoveRange です。Countが10でtoが7なら、3個消えた、ということになります。 結果、消える要素の分だけ詰まった配列ができます。

「ダウンロード待ち」が少ないとわかっていればこれでもいいのですが、 数が増えれば比例して遅くなります。 私が想定しているのは、「ダウンロード待ちが7000個」とかいう状況ですので、 それに比例して毎フレームの処理が増えると耐えられません。

では、辞書ならどうでしょう? 「ダウンロード待ち」が辞書に入っていれば一発で見つけて消せます。 でもダメです。今度は「入れた順番に取り出したい」が叶わなくなります。 SortedDictionaryにしても同じです。 キーと関係なく、入れた順で出したいので、意味がないのです。

入れた順番に取り出せる辞書

つまり、欲しいものは「入れた順番に取り出せる辞書」です。 これを最もお手軽に作る方法が、辞書+連結リスト、です。

Dictionary<string, Item> _items;
LinkedList<Item> _waitingItems;

class Item
{
    public LinkedListNode<Item> waitingItemsNode;
}
  • 名前で引ける辞書を用意する(_items)
  • 連結リストを用意する(_waitingItems)
  • データに連結リストのノードを足す(waitingItemsNode)

ミソは最後の「データの中に連結リストのノードを記録する」です。 自分がリストのどこにいるかを知っているようにすることで、削除が高速化します。 連結リストは配列と違って途中削除がタダ同然でできるのです。

まず、

  • 「ダウンロード中」の項目は最大数を固定とし、毎フレーム状態を監視する。終わっていたら「ダウンロード済み」に移す。空いた所に最も古い「ダウンロード待ち」を移す。

をLinkedListを使ってコードにしてみましょう。

for (int i = 0; i < _goingItems.Length; i++)
{
    if (_goingItems[i].done)
    {
        _doneItems.Add(_goingItems[i]);
        _goingItems[i] = _waitingItems.First.Value;
        _waitingItems.RemoveFirst();
    }
}

LinkedList.First で先頭が取れますが、返ってくるのはLinkedListNode です。これが「連結リスト中の位置」を表すクラスで、これを指定して削除や挿入ができます。 今は先頭を消せば良く位置の指定が不要なので、すぐに中の Value を取り出します。 そして、RemoveFirst() で先頭を消します。

次に、_waitingItemsへの追加です。

var node = _waitingItems.AddLast(newItem);
newItem.waitingItemsNode = node;

LinkedList.AddLast() で末尾に追加し、 返ってくるLinkedListNodeをデータの中に覚えておきます。これを使って、

  • 「ダウンロード待ち」の間に不要になった場合は、「ダウンロード待ち」から削除する。

を実装しましょう。

Item item;
if (_items.TryGetValue(cancellingName, out item))
{
    _waitingItems.Remove(item.waitingItemsNode);
}

まず、辞書からキャンセルしたい項目を名前をキーに探します。 ContainsKey してから 添字 で取り出すと、検索を二度やることになって遅いので、 TryGetValue が良いでしょう。

そして見つかれば、そこに持たせておいたLinkedListNodeを使って、 LinkedList.Remove() します。かくして、全操作O(1)になります。「ダウンロード待ち」が何万ファイルになったとしても、遅くなりません。

効率化

さて、上記の実装は基本でして、真面目に書くならばこのままにはしません。 何故なら、LinkedListに足す度にLinkedListNodeのnewが必要になって性能が落ちるからです。

じゃあどうするか?

自分のデータ型が、そのままLinkedListNodeのように振る舞えるようにします。

class Item
{
    //public LinkedListNode<Item> waitingItemsNode; これはやめる
    public Item waitingItemsNext;
    public Item waitingItemsPrev;
}

LinkedListNodeを持つのをやめて、 一つ前のItemと、一つ後のItemの参照を持たせます。 あとは、連結リストの操作をいくつか実装するだけです。 つまりLinkedListも使わず自作します。

自作と言っても、今回の例では、

  • 末尾追加
  • 任意位置削除

の2つしかいらないので、実装は簡単です。こんな感じになります。

// LinkedList<Item> _waitingItems; のかわりに以下の2行にする
Item _waitingListFirst; // 先頭
Item _waitingListLast; // 末尾

void AddLastToWaitingList(Item item)
{
    _waitingListLast.waitingItemsNext = item;
    item.waitingItemsPrev = _waitingListLast;
    // TODO: 1個もない時の処理は別途考えてね!
}

void RemoveFromWaitingList(Item item)
{
    var prev = item.waitingItemsPrev;
    var next = item.waitingItemsNext;
    prev.waitingItemsNext = next;
    next.waitingItemsPrev = prev;
    // TODO: 消すのが先頭だったり末尾だったりした時の処理は別途考えてね!
}

最初の一個の追加や、先頭あるいは末尾の削除は特別な配慮がいりますが、 nullチェックして分岐するだけなので、丁寧に場合分けすれば難しくはありません。 それが面倒なら、ずっと消えないダミー要素を先頭と末尾に一個づつ用意しておきましょう (番兵というテクニックです)。 分岐が不要になります。

と、効率化のお話をしてきましたが、今作っているライブラリではLinkedListのままです。 実戦投入して「GCAlloc多いんだけどどうにかして」と言われればどうにかしますが、 その時には上記のItemに当たる型のインスタンスの使い回しも一緒に実装することになるでしょう。

なお、このようにして効率化できるのは連結リストに限りません。 以前記事にしたデバグUI の実装のUI要素基底クラス は、連結リストの要素であるのみならず、木構造の要素にもなっており、 親や子の参照も持っています。ご興味があればどうぞ。 こうなると.netで用意されたコンテナをそのまま使うとnewだらけになる上に コードも複雑化しますので、自作してしまった方が速いのです。

余談ですが、連結リストは余計な容量なしでマージソートができるという面白い性質もあります。 マージソートは「同じ値の要素の順番が変化しない」という便利な性質がありますが、 配列でやると余計なメモリを食うので面倒なのです。しかし連結リストなら迷わずマージソートを選べます。 今の例で言えば、「ダウンロード待ちをサイズ順にソートするが、同じサイズなら古い方を優先したい」 みたいな時にマージソートを実装すれば勝手にそうなります。

おわりに

配列と辞書で何か足りない時は、連結リストという選択肢も持っていると良いと思います。 「入れた順にアクセスしたい辞書」は一つの例です。

また、連結リストで頻繁にGCAllocしてしまう問題は、 自分のデータ型を連結リストの要素にできるようにすれば解決します。 このテクニックはIntrusive Linked Listとも呼ばれます。

連結リストに限らず、データ構造は使えると便利なので、いつでも使えるように 頭の中の道具箱に入れておくといいんじゃないかなと思います。 例えば私の道具箱に入っているのは以下のような感じです。

  • 固定サイズ配列(Array): 最初にこれで足りないか考える
  • 可変サイズ配列(List): 個数可変ならこっちにするが、必要な操作が限られているならキューかスタックを検討する
  • キュー(Queue): 途中に触る必要がなく、入れた順に出すならこれ
  • スタック(Stack): 何かをプールしとく時は大抵これ。可変サイズ配列の類では一番制約が厳しいのでバグりにくく速い。
  • 連結リスト(LinkedList): すでに他のデータ構造に入ってるものに順序をつけたい時にこれを併用する
  • ハッシュ(Dictionary): 検索が必要な時の第一選択
  • キーだけのハッシュ(HashSet): DictionaryでValueがいらない時。単にダブリを消したい時なら配列でソートする方がメモリを汚さない。
  • 探索木(SortedDictionary): キーの順序でループしたい辞書、といえばこれ。
  • : 子の配列を持つより、「最初の子と次の兄弟」形式の方が大抵は効率がいい。親の参照は不要なら持たない方がいい。
  • ヒープ: 何かをプールする時に、何かの値で順序をつけたい時にはStackでなくこっち。

最後のヒープの使い所がイマイチわかりにくいと思うので補足しましょう。 ヒープには「最小値(最大でもいいが)が高速に見つかる」という特徴があり、これを使います。

例えば、「効果音用にAudioSourceを64個用意しているが、全部埋まってて新しい音が鳴らせない時に、 一番早く鳴り終わる音を止めてそこを使う」ということをしたい場合、 「鳴り終わり時刻」をキーにしてヒープを構成しておくと、64個全部を見て最小値を探す必要がなくなって高速です。 鳴り終わった音は当然「鳴り終わり時刻」も小さいので、単に空きを探す処理も高速化します。

ヒープも標準ライブラリにないので自作しますが、これも連結リスト同様に「参照でつながったデータ構造」 ですので、自分のデータ型に左の子と右の子の参照を持てば、余計なGCAllocなしでヒープを実装できます。

まあ、64個くらいなら全部見て最小値見つければいいと思いますけどね。

おまけ

IntrusiveListのサンプルコードをgithubに置いておきます。 番兵あり版と、番兵なし版を用意しました。番兵を使うことでコードが大きく削減でき、 実行速度も上がりますが、余計なGCAllocが2回必要です。 なお、コンパイルは通りますが動作テストはしてません。

実際にはこうやって抽象化すると性能が落ちますし、 大抵は限られた操作だけあればいいので、 必要な型ごとにベタで書いた方が良いと思います。