C# で ウェーブレット木 を実装したライブラリをアップデートした

かなり前の記事で書いたのですが、ウェーブレット木を C# で実装したライブラリを作りました。

今回、 Visual Studio 2019 Preview が出たので、それを機にアップデートしてみました。

github.com

アップデート内容

名前空間の変更、クラスの分割

名前空間はもともと単発の予定でつけたので、めっちゃ適当でした。今回は改めて名前を付けなおしました。

あと、最近よくわかってませんが、インターフェースだけ外出しして実装系を別ライブラリにするっていう方法を考えていまして。

今回その方法を試してみました。 IWaveletTree<T> だけを定義するプロジェクトと、それを参照して実装する WaveletTree<T> だけのプロジェクトみたいな。

どちらも .NET Standard 2.0 に準拠しているので、だいたいの実装系で使えます。

使う際は、 WabeletTree<T> を nuget で落としてくる時に依存解決で一緒に。。。と言って感じで想像しています。まだ nuget パッケージ作ってないけど。

WaveletTree.Select<T> メソッドの実装

今回実装にあたり、以下のサイトを参考にしました。

ウェーブレット木の世界 from Preferred Networks

www.slideshare.net

こちらの方のスライド、めちゃくちゃわかりやすいのですが、この中に出てくる「完備辞書」と呼ばれるものを目指してみました。

実装するには Select 関数を実装しなければならないらしいので、書いてみました。

        /// <summary>
        /// 指定された値が最初に出現する位置を取得します
        /// </summary>
        /// <param name="value">位置を取得する値</param>
        /// <returns>位置</returns>
        public int Select(T value) => this.Select(value, 0);

        /// <summary>
        /// 指定された値がn回目に出現する位置を取得します
        /// </summary>
        /// <param name="value">位置を取得する値</param>
        /// <param name="index">n</param>
        /// <returns>位置</returns>
        /// <exception cref="ArgumentOutOfRangeException"><c>index</c> is out of range of tree values.</exception>
        public int Select(T value, int index) => _ids.ContainsKey(value) ? this._SelectInner(value, index) : throw new ArgumentOutOfRangeException();

まずは公開メソッド。n回目という部分を実装するため、引数は2つ必要でした。というわけで、引数1つの時は強制的に最初に出てくる位置を取得するようにしています。

また、そもそも文字が含まれていない可能性があるので、その場合は例外をスローしています。

        /// <summary>
        /// 指定された値がn番目に出現する位置を取得します
        /// </summary>
        /// <param name="value">位置を取得する値</param>
        /// <param name="index">n</param>
        /// <returns>位置</returns>
        private int _SelectInner(T value, int index) =>
            this._depth == 0 ?
                (0 <= index && index <= this.Pairs.Count()) ? index : throw new ArgumentOutOfRangeException() :
            this._CheckTop(value) ?
                this._rightPairs?[this.Right?.Select(value, index) ?? 0].Index ?? 0 :
                this._leftPairs?[this.Left?.Select(value, index) ?? 0].Index ?? 0;

        /// <summary>
        /// 最上位ビットを見て0か1を判定します
        /// </summary>
        /// <param name="value">検査する値</param>
        /// <returns><c>true</c>: 1, <c>false</c>: 0</returns>
        private bool _CheckTop(T value) => (this._ids[value] & (1 << (this._depth - 1))) != 0;

そして内部の実装。結構考え込んで、このような形にしました。

何をしているかというと、実は「n番目に出てくる要素Xのインデックスを取得しろ」という情報を「Xを持っている葉」まで伝達しています。

すると、「Xを持っている葉」にとって「n番目に出てくる要素Xのインデックス」は「n」なので、そのまま受け取った「n」を返します。

その親は X がどちらの節にあるかを判別し、「その節のn番目に出てくる要素は、自分自身ではy番目」という逆引きを行い、それを返します。

というアルゴリズムを続けて、最後にオリジナルのシーケンスの中でのインデックスが変えるという寸法です。

めちゃくちゃ回りくどいです。もはや無駄です。ですが LINQ を使ったいい方法がこれしか思いつきませんでした…

安直に while 回したほうが早かったかもしれません。

感想

今回のアップデートは、破壊的というか根本的に名前空間を変えているのであれですが、極力クラスの内部は変えないように心がけました。

LINQ を使った実装を頑張ったので、ちょっと実用的でないコードがたくさんありますが、楽しかったから良し。

もしアドバイス等あれば、コメントお待ちしております。