スキップリストの.net実装を更新

スキップリストの.net上の実装を少し更新した。いつもと同様ファイル置き場に置いてある。とは言っても、ヘルプに記載しているサンプルコードに手を入れたのと、パブリックなメソッドの引数名を先頭大文字にした事だけ。この辺の標準的な名前付け規約はまだ良く分かっていないので時々変えるかも。

今回のサンプルコードの変更では、以前は

totalVolume[depth] = SkipList<MyItem, MyNode>
    .GetEnumerableInOrder(start, true, end, true, depth - 1)
    .Sum((n) => n.totalVolume[depth - 1]);
vwap[depth] = SkipList<MyItem, MyNode>
    .GetEnumerableInOrder(start, true, end, true, depth - 1)
    .Aggregate<MyNode, VolumeVwapPair>(new VolumeVwapPair() {
        Volume = 0,
        Vwap = 0
    }, (pair, node) =>
    VolumeVwapPair.Composite(pair, new VolumeVwapPair() {
        Volume = node.TotalVolume[depth - 1],
        Vwap = node.Vwap[depth - 1]
    })).Vwap;

とごちゃごちゃしていた所を、

VolumeVwapPair ret = SkipList<MyItem, MyNode>
    .GetEnumerableInOrder(start, true, end, true, depth - 1)
    .Select((node) => new VolumeVwapPair
                (node.TotalVolume[depth - 1], node.Vwap[depth - 1]))
    .Aggregate(VolumeVwapPair.Composite);
totalVolume[depth] = ret.Volume;
vwap[depth] = ret.Vwap;

とすっきりした記述にした、等等、匿名メソッドを闇雲に使う代わりにSystem.LinqのSelect拡張メソッドを一段階挟んで、VolumeVwapPair.Compositeメソッドが可換半群の合成規則を与えている事が明瞭になるようにした。この変更は「身も蓋もない」のコードにも反映してある。もちろん以前のコードと等価な範囲の変更である。

サンプルコードの全体は以下のようになっている。可換半群の任意の区間に渡る総和計算をスキップリストのツリー状の構造を用いて高速に行う事が実際に簡単に実装できるようになっているのが分かると思う。

---

使用例

時刻、値、出来高を持つ株価の歩み値データを考えます。このデータを時刻によりソートし、任意の区間に対して出来高の総和と出来高を重みとした加重平均値(VWAP値)を高速に計算できるようにしたい場合には次のようにします。なお、以下のコードではEnumerableで定義される拡張メソッドが用いられているためコードの先頭でusing System.Linq;が記述されている必要があります。

まずMyItemクラスを次のように定義します。

C#

class MyItem
{
    private DateTime time;
    private double price;
    private double volume;
    public MyItem(DateTime time, double price, double volume)
    {
        this.time = time;
        this.price = price;
        this.volume = volume;
    }
    public DateTime Time { get { return time; } }
    public double Price { get { return price; } }
    public double Volume { get { return volume; } }
}

次に(重み,平均値)ペアがなす可換半群を表すVolumeVwapPairクラスを定義します。なお、重みが0である全てのペアは同一視されこの可換半群の単位元としての役割を果たします。

C#

class VolumeVwapPair
{
    public double Volume;
    public double Vwap;
    public VolumeVwapPair(double Volume, double Vwap)
    {
        this.Volume = Volume;
        this.Vwap = Vwap;
    }
    public static VolumeVwapPair Composite(VolumeVwapPair pair1,
                                      VolumeVwapPair pair2)
    {
        double totalVolume = pair1.Volume + pair2.Volume;
        if (totalVolume == 0) return new VolumeVwapPair(0, 0);
        return new VolumeVwapPair(totalVolume,
            (pair1.Volume * pair1.Vwap + pair2.Volume * pair2.Vwap)
            / totalVolume);
    }
}

そしてMyNodeクラスを次のように定義します。

C#

class MyNode : SkipListNode<MyItem, MyNode>
{
    private double[] totalVolume;
    private double[] vwap;
    protected override void OnHeightDecided()
    {
        base.OnHeightDecided();
        InitializeParameters(ref totalVolume);
        InitializeParameters(ref vwap);
    }
    protected override void OnMaintainance(int depth)
    {
        base.OnMaintainance(depth);
        if (IsHeader || IsFooter) return;
        if (depth == 0) {
            totalVolume[0] = Item.Volume;
            vwap[0] = Item.Price;
        } else {
            MyNode start = this;
            MyNode end = this.Next[depth].Prev[depth - 1];
            VolumeVwapPair ret = SkipList<MyItem, MyNode>
                .GetEnumerableInOrder(start, true, end, true, depth - 1)
                .Select((node) => new VolumeVwapPair
                (node.TotalVolume[depth - 1], node.Vwap[depth - 1]))
                .Aggregate(VolumeVwapPair.Composite);
            totalVolume[depth] = ret.Volume;
            vwap[depth] = ret.Vwap;
        }
    }
    protected override int Compare(MyItem item1, MyItem item2)
    {
        return item1.Time.CompareTo(item2.Time);
    }
    public double[] TotalVolume { get { return totalVolume; } }
    public double[] Vwap { get { return vwap; } }
}

最後にMySequenceクラスを次のように定義します。

C#

class MySequence : SkipList<MyItem, MyNode>
{
    public double TotalVolume(MyNode former, MyNode latter)
    {
        return Sum(former, latter, (node, depth) => (node.TotalVolume[depth]));
    }
    public double Vwap(MyNode former, MyNode latter)
    {
        return Aggregate(former, latter,
                VolumeVwapPair.Composite,
                (node, depth) => new VolumeVwapPair
                (node.TotalVolume[depth], node.Vwap[depth]),
                new VolumeVwapPair(0, 0)).Vwap;
    }
}

この例では重みの総和に関してはDouble型の総和を計算するSum(TNode, TNode, Func<TNode, Int32, Double>)メソッドを用いて計算し、全平均値に関しては通常の意味での加法によって合成されない可換半群の典型例である(重み,平均値)ペア(重みは通常の和で、平均値は加重平均によって合成される)に対して一般的な可換半群の総和を計算するAggregate<T>(TNode, TNode, Func<T, T, T>, Func<TNode, Int32, T>, T)メソッドを適用する事で計算しています。

ほとんどの場合、可換半群は通常の意味での加法群と等価である事に注意してください。実際、(重み,平均値)ペアと(重み,重み*平均値)ペアとは重みが0である場合を除いて一対一に対応します。そして重み及び重み*平均値はそれぞれ独立に通常の意味での加法によって合成されます。従ってMyNodeクラスのOnMaintainanceメソッド及びMySequenceクラスのVwapメソッドはそれぞれ

C#

protected override void OnMaintainance(int depth)
{
    base.OnMaintainance(depth);
    if (IsHeader || IsFooter) return;
    if (depth == 0) {
        totalVolume[0] = Item.Volume;
        vwap[0] = Item.Price;
    } else {
        MyNode start = this;
        MyNode end = this.Next[depth].Prev[depth - 1];
        totalVolume[depth] = SkipList<MyItem, MyNode>
            .GetEnumerableInOrder(start, true, end, true, depth - 1)
            .Select((node) => node.TotalVolume[depth - 1])
            .Sum();
        vwap[depth] = SkipList<MyItem, MyNode>
            .GetEnumerableInOrder(start, true, end, true, depth - 1)
            .Select((node) => node.Vwap[depth - 1]
　　　　　 * node.TotalVolume[depth - 1])
            .Sum() / totalVolume[depth];
    }
}

及び

C#

public double Vwap(MyNode former, MyNode latter)
{
    double totalVolume = TotalVolume(former, latter);
    if (totalVolume == 0) return 0;
    return Sum(former, latter,
              (node, depth) => node.Vwap[depth] * node.TotalVolume[depth]) 
　　　　　　　/ totalVolume;
}

と書く事もできます。