SegmentTree/LazySegmentTree/FenwickTreeの演算の受け渡しについて #24
Comments
|
モノイドのマージ処理は軽い処理がループ内で何度も呼ばれるという都合上、2.だとやはりデリゲート呼び出し時のオーバーヘッドが不安かな……と思います。1.ならJIT時のインライン化も期待できるので、こちらの方が個人的には嬉しいです。 モノイドを毎回作成するのは面倒ですが、そこはよく使うモノイドを各自で予め用意しておくなりスニペット化するなりするのが良いのかな……と。 またC#8.0以降ならインターフェースに静的メソッド（演算子のオーバーロード含む）を持たせることができるようになったため、 またこれはライブラリ本体には直接関係がないため完全に余談ではありますが、モノイドをclassにすると毎回ヒープのメモリ確保が生じてしまうため、実際に使用する際はstruct（可能ならreadonly struct）にすると高速化が期待できるかもしれません。 |
オーバーヘッドを考えた場合も1の方が良いかもしれないですね。貴重な意見ありがとうございます🙇♂️ |
|
私のライブラリでは、SegTreeの実装自体は抽象クラスとしてモノイドは抽象メソッドで表現しています。 |
|
#20 に書いた
BenchmarksBenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1082 (1909/November2018Update/19H2)
Codeusing System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Linq.Expressions;
using System.Runtime.CompilerServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Running;
class Program
{
static void Main()
{
BenchmarkRunner.Run<AclBench>(DefaultConfig.Instance.AddDiagnoser(MemoryDiagnoser.Default));
}
}
public class AclBench
{
const int N = 100_000_000;
[Benchmark]
[BenchmarkCategory("Add")]
public long AddDirect()
{
var ft = new LongFenwickTree(N);
for (int i = 0; i < N; i++)
ft.Add(0, i);
return ft.Sum(0, N);
}
[Benchmark]
[BenchmarkCategory("Add")]
public long AddOperator()
{
var ft = OperatorFenwickTree.Long(N);
for (int i = 0; i < N; i++)
ft.Add(0, i);
return ft.Sum(0, N);
}
[Benchmark]
[BenchmarkCategory("Add")]
public long AddOperatorInline()
{
var ft = OperatorFenwickTree.LongInline(N);
for (int i = 0; i < N; i++)
ft.Add(0, i);
return ft.Sum(0, N);
}
[Benchmark]
[BenchmarkCategory("Sum")]
public long SumDirect()
{
long sum = 0;
var ft = new LongFenwickTree(N);
for (int i = 0; i < N; i++)
sum += ft.Sum(0, i);
return sum;
}
[Benchmark]
[BenchmarkCategory("Sum")]
public long SumOperator()
{
long sum = 0;
var ft = OperatorFenwickTree.Long(N);
for (int i = 0; i < N; i++)
sum += ft.Sum(0, i);
return sum;
}
[Benchmark]
[BenchmarkCategory("Sum")]
public long SumOperatorInline()
{
long sum = 0;
var ft = OperatorFenwickTree.LongInline(N);
for (int i = 0; i < N; i++)
sum += ft.Sum(0, i);
return sum;
}
}
public class LongFenwickTree
{
private readonly long[] data;
public LongFenwickTree(int n)
{
this.data = new long[n + 1];
}
public void Add(int p, long x)
{
Debug.Assert(unchecked((uint)p < data.Length));
for (p++; p < data.Length; p += p & -p) // p < data.Lengthで比較すると配列アクセスにJIT最適化がかかる
{
data[p] += x;
}
}
public long Sum(int l, int r)
{
Debug.Assert(0 <= l && l <= r && r < data.Length);
return Sum(r) - Sum(l);
}
private long Sum(int r)
{
long s = 0;
for (; r > 0; r -= r & -r)
{
s += data[r];
}
return s;
}
}
public static class OperatorFenwickTree
{
public static OperatorFenwickTree<long, LongOperator> Long(int n) => new OperatorFenwickTree<long, LongOperator>(n);
public static OperatorInlineFenwickTree<long, LongOperator> LongInline(int n) => new OperatorInlineFenwickTree<long, LongOperator>(n);
}
public class OperatorFenwickTree<TValue, TOp>
where TValue : struct
where TOp : struct, INumOperator<TValue>
{
readonly TOp op;
private readonly TValue[] data;
public OperatorFenwickTree(int n)
{
this.data = new TValue[n + 1];
}
public void Add(int p, TValue x)
{
Debug.Assert(unchecked((uint)p < data.Length));
for (p++; p < data.Length; p += p & -p) // p < data.Lengthで比較すると配列アクセスにJIT最適化がかかる
{
data[p] = op.Add(data[p], x);
}
}
public TValue Sum(int l, int r)
{
Debug.Assert(0 <= l && l <= r && r < data.Length);
return op.Sub(Sum(r), Sum(l));
}
private TValue Sum(int r)
{
var s = op.Zero;
for (; r > 0; r -= r & -r)
{
s = op.Add(s, data[r]);
}
return s;
}
}
public class OperatorInlineFenwickTree<TValue, TOp>
where TValue : struct
where TOp : struct, INumOperator<TValue>
{
static readonly TOp op;
private readonly TValue[] data;
public OperatorInlineFenwickTree(int n)
{
this.data = new TValue[n + 1];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(int p, TValue x)
{
Debug.Assert(unchecked((uint)p < data.Length));
for (p++; p < data.Length; p += p & -p) // p < data.Lengthで比較すると配列アクセスにJIT最適化がかかる
{
data[p] = op.Add(data[p], x);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public TValue Sum(int l, int r)
{
Debug.Assert(0 <= l && l <= r && r < data.Length);
return op.Sub(Sum(r), Sum(l));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private TValue Sum(int r)
{
var s = op.Zero;
for (; r > 0; r -= r & -r)
{
s = op.Add(s, data[r]);
}
return s;
}
}
public interface INumOperator<T> : IComparer<T> where T : struct
{
public T Zero { get; }
public bool IsZero(T v);
public T MaxValue { get; }
T Add(T v1, T v2);
T Sub(T v1, T v2);
}
public readonly struct IntOperator : INumOperator<int>
{
public int Zero => 0;
public bool IsZero(int v) => v == 0;
public int MaxValue => int.MaxValue;
public int Add(int v1, int v2) => v1 + v2;
public int Sub(int v1, int v2) => v1 - v2;
public int Compare(int x, int y) => x.CompareTo(y);
}
public readonly struct LongOperator : INumOperator<long>
{
public long Zero => 0;
public bool IsZero(long v) => v == 0;
public long MaxValue => long.MaxValue;
public long Add(long v1, long v2) => v1 + v2;
public long Sub(long v1, long v2) => v1 - v2;
public int Compare(long x, long y) => x.CompareTo(y);
} |
|
#33 のFlowも合わせて、このinterfaceで統一するのはありかなと思っています。 |
|
ベンチマークありがとうございます。かなり速度に差が出ないですね。 クラスにオペレータを持たせる(
|
|
私は普段 /// <summary>
/// モノイド
/// </summary>
/// <typeparam name="T">自分</typeparam>
public interface IMonoid<T> where T : IMonoid<T>
{
T Identity { get; }
T Merge(T other);
}
/// <summary>
/// 作用付きモノイド
/// </summary>
/// <typeparam name="TMonoid">作用先</typeparam>
/// <typeparam name="TMonoidWithAction">自分</typeparam>
public interface IMonoidWithAction<TMonoid, TMonoidWithAction> : IMonoid<TMonoidWithAction>
where TMonoid : IMonoid<TMonoid>
where TMonoidWithAction : IMonoidWithAction<TMonoid, TMonoidWithAction>
{
TMonoid Act(TMonoid monoid);
}
public class SegmentTree<TMonoid>
where TMonoid : struct, IMonoid<TMonoid>
{
}
public class LazySegmentTree<TMonoid, TMonoidWithAction>
where TMonoid : struct, IMonoid<TMonoid>
where TMonoidWithAction : struct, IMonoidWithAction<TMonoid, TMonoidWithAction>
{
}この実装の個人的に嬉しい点としては、上とも若干被りますが、
あたりです。 このあたりの実装はどうしても趣味が入っちゃいますね……。 |
これに関しては、結局 MFGraphInt や MFGraphLong のようにラッパークラスを提供するのであれば、使う際には特に問題にならないかと思います。 segment treeに関しては、数値型だけ決めればいいFlowやFenwickTree とはまた話が違ってきそうな気がしています。 |
その点については同じことを考えていました。 |
|
型引数が多い問題に関しては、内部の利用で留めればいいというのは確かだと思います。Flow 周りはこの実装でやるのが良さそうですね。 話は少し変わりますが、FenwickTree はアーベル群に対する作用として考えられるので、SegTree と同じ実装方針にしたいなという気持ちはありました。 IEquatable 相当の実装した Monoid がクラスだった際に展開が行われずパフォーマンスが損なわれるかも、ということが気になっているのですが、class として実装したい場面はありますかね? セグ木を使用する側の実装で同じオブジェクトを使用していて class でないと不具合が生じる、などが考えられはしますが、そこまで多くはなさそう? |
|
あたりが思い浮かぶところでしょうか？競プロでセグ木を使いたい、という文脈で言うなら、使用側としてはそこまで困ることはないのかな……？と思っています。（パッと思い付けてないだけかもしれません） 逆に |
|
同様の手法について調べたところ、3年前から検討が続いてる言語仕様がまさに 演算子クラスを作成する(IEqualityComparer 相当) に近い手法でした。 dotnet/csharplang#110 class として実装すると展開されないのはこちらでもたぶん同じです。 もう一つ、IEqualityComparer 相当のメリットとしてはC++版のsegtree, lazy_segtreeは関数と初期値を渡す実装になっているので、segtreeについてはC++版と近い形式になるというのがあります。(逆に、fenwick_treeは追加の型引数が必要となってしまいますが) |
こういうイメージでしょうか？ public interface IOperator<T>
{
T Identity { get; }
T Operate(T x, T y);
}
public class SegmentTree<TValue, TOp>
where TOp : struct, IOperator<TValue>
{
static readonly TOp op;
//省略
}
public readonly struct IntRangeMaxQueryOperator : IOperator<int>
{
public int Identity => 0;
public int Operate(int x, int y) => System.Math.Max(x, y);
}
public class Program
{
static void Main()
{
var seg = new SegmentTree<int, IntRangeMaxQueryOperator>();
}
}おそらく使う側で IOperator の struct を定義しないといけないケースが多々出て来ると思いますが、コンストラクタにラムダ式を渡すのと同じようなものだし大丈夫ですかね……？ |
|
本ライブラリとは特に関係ないですが、 |
C++における実装においては、関数ポインタを定数template引数に渡す(SegmentTree/LazySegmentTree), テンプレートに渡される型が整数型であると仮定して、そうでない場合はコンパイルエラーとする(FenwickTree) と言った手法を取っています。
しかし、C#で同様のことを行おうとしても
や
といったことはできない状況となっています。
そのためC++による元ライブラリの仕様をまるごと移植するのは諦め、何らかの代替策を取る必要があります。
考えうる案としては、
といった手法があります。（他の手法も提案していただけると嬉しいです。）
それぞれの手法のメリットは、
デメリットとしては、
となります。
see also: #20 , #1 , #2 , #3
The text was updated successfully, but these errors were encountered: