C#に存在しない機能を用いた実装について #20
Labels
Comments
Closed
|
一括includeは |
|
整数・実数テンプレート、いくつか手段があると思っていて、
あたりがパッと思い付くものかなと考えています。 個人的には少々面倒ながら4.あたりかなと考えていたのですが、実行速度が気になるところなので、長いですが以下のコードでそれぞれ速度比較を行ってみました。 using System;
using System.Linq.Expressions;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
class Program
{
static void Main(string[] args)
{
BenchmarkRunner.Run<GenericAddTest>();
}
}
public class GenericAddTest
{
const int N = 1_000_000_000;
/// <summary>
/// 1. 生longで足し算
/// </summary>
[Benchmark]
public long LongAdd() => LongAdd(1L);
private long LongAdd(long init)
{
long x = init;
for (int i = 0; i < N; i++)
{
x = x + x;
}
return x;
}
/// <summary>
/// 2. 式木で足し算
/// </summary>
[Benchmark]
public long ExpressionAdd() => ExpressionAdd(1L);
private T ExpressionAdd<T>(T init)
{
var p1 = Expression.Parameter(typeof(T));
var p2 = Expression.Parameter(typeof(T));
var add = Expression.Lambda<Func<T, T, T>>(Expression.Add(p1, p2), p1, p2).Compile();
T x = init;
for (int i = 0; i < N; i++)
{
x = add(x, x);
}
return x;
}
/// <summary>
/// 3. dynamicで足し算
/// </summary>
[Benchmark]
public long DynamicAdd() => (long)DynamicAdd(1L);
private dynamic DynamicAdd(dynamic init)
{
dynamic x = init;
for (int i = 0; i < N; i++)
{
x = x + x;
}
return x;
}
/// <summary>
/// 4. structにインターフェースを実装し、メンバメソッドを呼び出す
/// </summary>
[Benchmark]
public long GenericStructAdd() => GenericAdd(new LongStruct(1L)).Value;
private T GenericAdd<T>(T init) where T : IAddable<T>
{
T x = init;
for (int i = 0; i < N; i++)
{
x = x.Add(x);
}
return x;
}
/// <summary>
/// 5. structにインターフェースを実装し、オーバーロードされた演算子を呼び出す
/// </summary>
[Benchmark]
public long GenericStructAddWithOperator() => GenericAddWithOperator(new LongStruct(1L)).Value;
private T GenericAddWithOperator<T>(T init) where T : IAddable<T>
{
T x = init;
for (int i = 0; i < N; i++)
{
x = x + x; // Boxing!!!
}
return x;
}
/// <summary>
/// 6. classにインターフェースを実装し、メンバメソッドを呼び出す
/// </summary>
[Benchmark]
public long GenericClassAdd() => GenericAdd(new LongClass(1L)).Value;
interface IAddable<T> where T : IAddable<T>
{
public T Add(T other);
public static T operator +(IAddable<T> x, T y) => x.Add(y);
}
readonly struct LongStruct : IAddable<LongStruct>
{
public long Value { get; }
public LongStruct(long value) => Value = value;
public LongStruct Add(LongStruct other) => new LongStruct(Value + other.Value);
public static implicit operator long(LongStruct x) => x.Value;
}
class LongClass : IAddable<LongClass>
{
public long Value { get; }
public LongClass(long value) => Value = value;
public LongClass Add(LongClass other) => new LongClass(Value + other.Value);
public static implicit operator long(LongClass x) => x.Value;
}
}実行結果
上から順番に、
の実行時間です。 2.の式木は生 判断の一助となれば嬉しいです。ツッコミ所等もあれば教えてください……！ |
|
実際に最大流のライブラリで試してみたのがこちらです。 ↓抜粋 public interface ICap<TValue, TCap> : IEquatable<TCap>
where TValue : struct, IEquatable<TValue>, IComparable<TValue>
where TCap : ICap<TValue, TCap>, IEquatable<TCap>, new()
{
public static TCap Zero => new TCap();
public static TCap Limit => new TCap().GetLimit();
TValue Value { get; set; }
bool IsZero();
TCap GetLimit();
TCap Add(ICap<TValue, TCap> value);
TCap Sub(ICap<TValue, TCap> value);
public static TCap operator +(ICap<TValue, TCap> lhs, ICap<TValue, TCap> rhs)
=> lhs.Add(rhs);
public static TCap operator -(ICap<TValue, TCap> lhs, ICap<TValue, TCap> rhs)
=> lhs.Sub(rhs);
public static bool operator <(ICap<TValue, TCap> lhs, ICap<TValue, TCap> rhs)
=> lhs.Value.CompareTo(rhs.Value) < 0;
public static bool operator >(ICap<TValue, TCap> lhs, ICap<TValue, TCap> rhs)
=> lhs.Value.CompareTo(rhs.Value) > 0;
}
public struct CapInt : ICap<int, CapInt>
{
public int Value { get; set; }
public CapInt(int value) => Value = value;
public bool IsZero() => Value == 0;
public CapInt GetLimit() => new CapInt(int.MaxValue);
public CapInt Add(ICap<int, CapInt> value) => new CapInt { Value = this.Value + value.Value };
public CapInt Sub(ICap<int, CapInt> value) => new CapInt { Value = this.Value - value.Value };
public bool Equals(CapInt other) => Value == other.Value;
}
public struct CapLong : ICap<long, CapLong>
{
public long Value { get; set; }
public CapLong(long value) => Value = value;
public bool IsZero() => Value == 0;
public CapLong GetLimit() => new CapLong(long.MaxValue);
public CapLong Add(ICap<long, CapLong> value) => new CapLong { Value = this.Value + value.Value };
public CapLong Sub(ICap<long, CapLong> value) => new CapLong { Value = this.Value - value.Value };
public bool Equals(CapLong other) => Value == other.Value;
}
public class MFGraph<TValue, TCap>
where TValue : struct, IEquatable<TValue>, IComparable<TValue>
where TCap : ICap<TValue, TCap>, IEquatable<TCap>, new()
{
}おそらくGenericStructAddWithOperatorに相当するものだと思うのですが、思っていたよりかは遅くなかったです。（むしろこのALPC-Dの結果だけを見る分には速いです） C++側も、intとlong longのみを想定している様ですし、とりあえずlong限定で書いてライブラリを使えるようにするのがいいのでは？と個人的には思います。 |
ありがとうございます…!
ユーザーに公開するインターフェイスには見えないようにするのが賢明かもしれないとは思いつつ、インターフェイスを変更するのはどうかという思いもあるので今は判断しきれないですね… |
|
Rawusing System;
using System.Linq;
using System.Linq.Expressions;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Running;
class Program
{
static void Main()
{
BenchmarkRunner.Run<AddBench>(DefaultConfig.Instance.AddDiagnoser(MemoryDiagnoser.Default));
}
}
public class AddBench
{
const int N = 1000_000_000;
const long sumN = 499999999500000000;
[Benchmark]
public long Direct()
{
var sum = new SumDirect();
for (int i = 0; i < N; i++)
sum.Add(i);
var result = sum.Value;
if (result != sumN) throw new Exception();
return result;
}
[Benchmark]
public long Addable()
{
var sum = new SumAddable<AddableLong>();
for (int i = 0; i < N; i++)
sum.Add(i);
var result = sum.Addable.value;
if (result != sumN) throw new Exception();
return result;
}
[Benchmark]
public long AdderClass()
{
var sum = new SumAdder<long, LongAdderClass>(new LongAdderClass());
for (int i = 0; i < N; i++)
sum.Add(i);
var result = sum.Value;
if (result != sumN) throw new Exception();
return result;
}
[Benchmark]
public long AdderStruct()
{
var sum = new SumAdder<long, LongAdderStruct>();
for (int i = 0; i < N; i++)
sum.Add(i);
var result = sum.Value;
if (result != sumN) throw new Exception();
return result;
}
}
public class SumDirect
{
public long Value { private set; get; }
public long Add(long val) => this.Value += val;
}
public interface IAddable<T> where T : IAddable<T>
{
public T Add(T other);
}
public readonly struct AddableLong : IAddable<AddableLong>
{
public AddableLong(long val) { this.value = val; }
public readonly long value;
public AddableLong Add(AddableLong other) => new AddableLong(value + other.value);
public static implicit operator AddableLong(long val) => new AddableLong(val);
}
public class SumAddable<T> where T : IAddable<T>
{
public T Addable { private set; get; }
public T Add(T val) => Addable = Addable.Add(val);
}
public interface IAdder<T>
{
public T Add(T v1, T v2);
}
public class LongAdderClass : IAdder<long>
{
public long Add(long v1, long v2) => v1 + v2;
}
public struct LongAdderStruct : IAdder<long>
{
public long Add(long v1, long v2) => v1 + v2;
}
public class SumAdder<T, A> where A : IAdder<T>
{
private readonly A adder;
public SumAdder() { }
public SumAdder(A adder)
{
this.adder = adder;
}
public T Value { private set; get; }
public T Add(T val) => Value = adder.Add(Value, val);
}
// このような取得用クラスを用意してしまうのもアリか。
public static class SumAdder
{
public static SumAdder<long, LongAdderStruct> Long() => new SumAdder<long, LongAdderStruct>();
}
// mcf_graph<Cap, Cost>を実現するならこんな感じになる？
public static class McfGraph
{
public static McfGraph<long, LongOperator, long, LongOperator> LongLong(int n) => new McfGraph<long, LongOperator, long, LongOperator>(n);
public static McfGraph<int, IntOperator, long, LongOperator> IntLong(int n) => new McfGraph<int, IntOperator, long, LongOperator>(n);
public static McfGraph<long, LongOperator, int, IntOperator> LongInt(int n) => new McfGraph<long, LongOperator, int, IntOperator>(n);
public static McfGraph<int, IntOperator, int, IntOperator> IntInt(int n) => new McfGraph<int, IntOperator, int, IntOperator>(n);
} |
Closed
kzrnm
added a commit
that referenced
this issue
Feb 27, 2022
BinarySearch targets only IComparable<T>
|
実装済み |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
存在しない機能を用いた実装について、どう対応するかをまとめたい
今現在問題になりそうなもの
<atcoder/all>)type_traitsThe text was updated successfully, but these errors were encountered: