key-moon commented 4 years ago

20 より。

class MFGraph<T, CapT> { }

のようなインターフェイスにすると、オーバーヘッドなしに C++ のようなインターフェイスが実装できる。

ただ、元々 int か long しか入ることが想定されていないため、long でのみとりあえず実装してしまえば良いかもしれない。

terry-u16 commented 4 years ago

前者の方針の場合、利用者側に仕様の理解を求めるのはややハードルが高いかもしれない（C++版のmcf_graph<int, int>のような使い方ほどには直感的でない）ので、int版やlong版のラッパークラスも併せて用意してあげると親切かもしれませんね。

そこまでするならわざわざインターフェース化までする必要はないのでは、という話になってしまうかもしれませんが、同コード量でintとlongの両方の使い方に対応でき、将来的な拡張の余地（doubleとか……？）も残せるのは嬉しいかな……と。

key-moon commented 4 years ago

となると SCC のように、内部的な実装のラッパーという形で提供するのがいい落とし所だったりするのではないかと思っていますが、どうでしょうか?

terry-u16 commented 4 years ago

良さそうに思えます。

TはintだけどCapTはlongにしたい、みたいな需要はおそらく稀なので、問題になることもほとんどなさそうですね。

（2020/9/10 18:45編集）型引数について誤解していてよく分からないことを言っていました（MCFGraph<TCap, TCost>のことだと空目）。すみません……。

key-moon commented 4 years ago

@takytank 前の Issue にて提案されていたので、上記の提案について意見をお聞きしたいです…!

takytank commented 4 years ago

public class MFGraphInt : MFGraph<int, CapInt> のように派生クラスを作って、基本的にはそれを使ってもらうという認識であってますでしょうか？この方針自体には賛成です。

ただ、 #20 の方にも書いた通り、現時点で自分が挙げた実装には若干懸念点があります。具体的には、C# の仕様でinterfaceに ==演算子の実装が追加できず、TCap型で == 演算子を使うことが出来ません。

今回移植した範囲では == 0 の比較が多かったので、そこに関しては、IsZero関数を追加して回避しました。ただ、1箇所C++では

if (d <= 0) continue;

となっている部分が

if (d.IsZero() || d < ICap<TValue, TCap>.Zero) continue;

のように冗長になっており、特に ICap<TValue, TCap>.Zero のZeroプロパティは毎回デフォルトインスタンスを生成する動作になっているため、あまり効率が良くないと思われます。（Assertの部分にも <= 比較があって、こちらは一旦コメントアウトで逃げてます）

この辺りをどうするか先に話し合っておかないと、実装の段階になって議論がひっくり返ってしまうかもしれません。

key-moon commented 4 years ago

以下のようなインターフェイスを実装すると、オペレータでの比較ができて多少高速になるので嬉しい気がします。（比較をする限り、オペレータを介した方が早かったのでそう展開される方がありがたいです）

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);
    bool LessThan(ICap<TValue, TCap> value);
    bool LessThanEquals(ICap<TValue, TCap> value);
    bool GreaterThan(ICap<TValue, TCap> value);
    bool GreaterThanEquals(ICap<TValue, TCap> value);
}

また、デフォルトインスタンスの生成に関してはデフォルトであればかなり軽いので、そこまで問題にならないかと思います。（IL/機械語の段階で0が定数として埋め込まれないというのは問題としてありますね。）

実測すると、かなり早くなりました。

terry-u16 commented 4 years ago

好みの問題だとは思いますが、インターフェースのメンバ数が増えてきたようにも感じるので、少々整理してみました。いかがでしょうか……？ structに対して、defaultが0埋めとなることを利用したコードです。

using System;
using System.Diagnostics.CodeAnalysis;

class Program
{
    static void Main(string[] args)
    {
        var mfGraph = new MFGraph<OreOreInt>(n);
        var mcfGraph = new MCFGraph<OreOreInt, OreOreInt>(n);
    }
}

internal interface IAbelian<T>
{
    T Add(T other);
    T Subtract(T other);
}

internal interface IMaxLimit<T>
{
    T MaxLimit { get; }
}

internal readonly struct OreOreInt 
    : IAbelian<OreOreInt>, IMaxLimit<OreOreInt>, IComparable<OreOreInt> //, IEquatable<T>, ... (as required)
{
    public int Value { get; }

    public OreOreInt(int value) => Value = value;

    public OreOreInt MaxLimit => new OreOreInt(int.MaxValue);
    public OreOreInt Add(OreOreInt other) => new OreOreInt(Value + other.Value);
    public OreOreInt Subtract(OreOreInt other) => new OreOreInt(Value - other.Value);
    public int CompareTo([AllowNull] OreOreInt other) => Value - other.Value; // or Value.CompareTo(other.Value);

    public override string ToString() => Value.ToString();
    public static implicit operator int(OreOreInt value) => value.Value;
}

internal class MFGraph<TCapacity> 
    where TCapacity : struct, IAbelian<TCapacity>, IMaxLimit<TCapacity>, IComparable<TCapacity>
{
    public TCapacity Flow(int s, int t) => Flow(s, t, default(TCapacity).MaxLimit);

    public TCapacity Flow(int s, int t, TCapacity flowLimit)
    {
        // 0
        TCapacity d = default;

        // Add / Subtract
        d = d.Add(d);
        d = d.Subtract(d);

        // TCapacity.MaxValue
        d = default(TCapacity).MaxLimit;

        // dが0と等しい
        if (d.CompareTo(default) == 0)
        {
            // do something
        }

        // dが0以下
        if (d.CompareTo(default) <= 0)
        {
            // do something
        }
    }
}

internal class MCFGraph<TCapacity, TCost>
    where TCapacity : // 後略

CompareToの速度はインライン化がかかってもさすがに比較演算子には勝てない（引き算が1回増える）かと思いますが、アルゴリズム全体から見れば誤差の範囲かな……と思っています。

takytank commented 4 years ago

すみません。インターフェースには直接関係無いのですが、確認に使っているコードのDinic部分で思いっきりこのミスをしていました。 https://twitter.com/rsk0315_h4x/status/1303978562228084736

以後気をつけます。

修正版の提出です。 https://atcoder.jp/contests/practice2/submissions/16612423

takytank commented 4 years ago

好みの問題だとは思いますが、インターフェースのメンバ数が増えてきたようにも感じるので、少々整理してみました。いかがでしょうか……？

ジェネリック型指定が1つに減ったのに感動しながら試してみました。

https://atcoder.jp/contests/practice2/submissions/16612853 https://atcoder.jp/contests/practice2/submissions/16612917

AddEdgeやChangeEdgeの引数もTCapになったので、コードから呼び出すときの利便性を考えて、int -> CapInt 方向の暗黙の型変換も追加しました。あとは、Add関数だと += したいときに左辺と右辺に同じものを書かないといけないので、やっぱり + や - 演算子のオーバーロードは欲しいなって気持ちです。

kzrnm commented 4 years ago

https://github.com/key-moon/ac-library-cs/issues/20#issuecomment-690100121 にも記載したようなINumOperatoer<T>による実装を試してみました。

    public interface INumOperater<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);
    }

https://atcoder.jp/contests/practice2/submissions/16613913

ICap<TValue, TCap>を置き換えたほかは https://atcoder.jp/contests/practice2/submissions/16607810 のコピペです。

同等の速度が出ていることが確認できます。

key-moon commented 4 years ago

24 の話をまとめると、上で実装して頂いた

https://atcoder.jp/contests/practice2/submissions/16613913

のインターフェイスが MinCostFlow/MaxFlow の実装においてふさわしいのかなと感じます。

代数的なインターフェイスは今後増えていくことが予想されるので、直下に Algebra などのディレクトリを切るのが良いでしょうか？命名は今後変更する機会があるため、とりあえずは現行のままで大丈夫だと思います。

どなたか実装して頂けると幸いです。

takytank commented 4 years ago

では、引き受けます。

kzrnm commented 4 years ago

入れ違いになりましたが、書きました。

https://github.com/key-moon/ac-library-cs/pull/38

takytank commented 4 years ago

ちなみに、 #25 に書いた通り、MinCostFlowの実装に PriorityQueue が必要なのですが、これはこれで実装方針に議論があると思います。とりあえずは、MinCostFlowのクラス内に private class で置いて、隠蔽した状態で MinCostFlow を実装してしまい、 PriorityQueueに関しては後で差し替えで構わないでしょうか？

terry-u16 commented 4 years ago

privateにする分には問題ないと思います！余裕が出てきたら #25 の話もしていけるといいですね。

key-moon commented 4 years ago

遅くなってしまって申し訳ありません🙇 PriorityQueue に関してはその方針で問題ありません。別途 Interna lに隔離するかどうかするか等は今後 #25 の話で決定していきたいです。

38 にて `INumOperator` を実装して頂いているので、そちらの仕様も確認して頂けると嬉しいです。

takytank commented 4 years ago

最小費用流の移植をしていて

g[to].push_back(_edge{from, int(g[from].size()) - 1, 0, -cost});

の -cost の部分が今の INumOperator では実現できないことに気付きました。これは、 INumOperator に Inverse 関数を追加して対応すればよいでしょうか？

key-moon commented 4 years ago

完全に忘れていました…! そのような対応をお願いしたいです。

key-moon commented 4 years ago

インターフェイスは確定したので、一旦この issue を閉じようと思います。皆さん本当にありがとうございました……!

kzrnm commented 4 years ago

op.Subtract(default, cost) で実現可能なはずですが、単項マイナス演算子の追加で良いと思います。ただ、Inverse だと逆数みたいなので ~~Minus~~ Negate の方が良いと思います。

key-moon commented 4 years ago

Expression の命令では単項マイナス演算子の生成は Expression.Negate になっていました。ただ、命名は後からいじるチャンスがあるので Minus で良いと思います。

kzrnm commented 4 years ago

他の演算子は Expression と同じ名称にしているので、 Negate が良いかなと思います。

takytank commented 4 years ago

UIntOperator と ULongOperator の Minus はどうしましょうか？無難に値を変えずに返しておくのがいいでしょうか？

key-moon commented 4 years ago

私は例外の送信が良いかと思います

takytank commented 4 years ago

こちら、一旦 reopen してもらえないでしょうか？

最小費用流の実装を進めていて、新たに二つ問題が発生しています。

TCap 型の -1 での初期化
TCap 型と TCost 型の演算

-1 での初期化

C++のコードの122行目

Cost cost = 0, prev_cost = -1;

の部分です。コード中に出て来る 0 の部分は、これまで default を使うことによって対処してきたのですが、 -1 は同じようにはいきません。こちらに関しては、特に異論が無ければ、INumericOperator に Increment と Decrement 関数を追加し、

op.Decrement(default);

とすることで対処しようと思います。

TCap 型と TCost 型の演算

C++側が

template <class Cap, class Cost> struct mcf_graph {

となっているため、それに合わせて

public class McfGraph<TCap, TCapOp, TCost, TCostOp>
    where TCap : struct
    where TCapOp : struct, INumOperator<TCap>
    where TCost : struct
    where TCostOp : struct, INumOperator<TCost>
{
    static readonly TCapOp capOp = default;
    static readonly TCostOp costOp = default;
}

のように、流量の型と費用の型を別々に取るように実装していました。しかし、C++のコードの138行目が、

cost += c * d;

のように流量と費用のかけ算となっています。（cost と d が TCost で、c が TCap です）これに関して INumOperator を変更しての上手い解決方法が思い浮かばず、相談したいです。

最終手段としては、流量と費用で型を分けないという解決策になると思いますが、その場合に問題になりそうなケースというのは何かありますでしょうか？

terry-u16 commented 4 years ago

気付きませんでした……これは罠ですね……。

TCap 型の -1 での初期化

uintの場合などを一瞬考えましたが、そもそもint/ll想定なので問題ないですね。他にあるとすれば、-1ではなくMinValueで初期化する、等でしょうか？

TCap 型と TCost 型の演算

真面目にやろうとするとかなり大変そうですね……。同じ型を使うという方針で問題になるケースは正直思い付かないので、まとめてしまっても良いかなと思います。

takytank commented 4 years ago

セグ木の方を見ると、それぞれ独自の Operator interface を使用しているみたいなので、

public interface IMcfOperator<TCap, TCost>
{
    TCap Multiply(TCap x, TCap y);
    TCost Multiply(TCost x, TCost y);
    TCost Multiply(TCap x, TCost y);
    //その他
}

みたいな独自 operator を用意して

public class McfGraph<TCap, TCost, TOp>
    where TCap : struct
    where TCost : struct
    where TOp : IMcfOperator<TCap, TCost>
{
}

とすればいけそうだなと思いました。ただ、折角 INumOperator があるのに同じようなものを定義するのはなんだかな、というかオリジナルの IMcfOperator の実装を作るのがかなり手間になるので、 IMcfOperator には TCost と TCap の乗算だけを定義することにして

public interface IMcfOperator<TCap, TCost>
{
    TCost Multiply(TCap x, TCost y);
}

public class McfGraph<TCap, TCapOp, TCost, TCostOp, TMcfOp>
    where TCap : struct
    where TCapOp : struct, INumOperator<TCap>
    where TCost : struct
    where TCostOp : struct, INumOperator<TCost>
    where TMcfOp : IMcfOperator<TCap, TCost>
{
}

とすれば、型指定が5つになるのを置いておけば幾分マシでしょうか？その上で、

public interface IMcfOperator<TCap, TCapOp, TCost, TCostOp>
    where TCap : struct
    where TCapOp : struct, INumOperator<TCap>
    where TCost : struct
    where TCostOp : struct, INumOperator<TCost>
{
    TCost Multiply(TCap x, TCost y);
    public TCap Multiply(TCap x, TCap y) => default(TCapOp).Multiply(x, y);
}

public class McfGraph<TCap, TCapOp, TCost, TCostOp, TMcfOp>
    where TCap : struct
    where TCapOp : struct, INumOperator<TCap>
    where TCost : struct
    where TCostOp : struct, INumOperator<TCost>
    where TMcfOp : IMcfOperator<TCap, TCapOp, TCost, TCostOp>
{
}

の様に interface のデフォルト実装を持たせると、McfGraphクラス内で使う operator クラスが1つにまとまってすっきりするんですけど、defaultとはいえ毎回インスタンスを作らないといけないので、これはパフォーマンス的に良く無さそうですね（未検証）

kzrnm commented 4 years ago

方式としては、 T FromLong(long num) と long ToLong(T num)を用意して

cost += costOp.FromLong(capOp.ToLong(c) * costOp.ToLong(d));

としてしまうのはどうでしょうか。 intのときは無駄な変換になりますが…

takytank commented 4 years ago

cost += costOp.FromLong(capOp.ToLong(c) * costOp.ToLong(d));

これが許されるなら、クラスの出入り口でlongとの変換をかまして内部の実装は全部 long でやるでも良かったのでは？って気持ちにはなりますね…… もちろん、 TCap が int の時に、全部が longになるのと一部が long になるのでは速度が変わってくるとは思いますが。

key-moon commented 4 years ago

すでにまとまりかけているところ、遅くのコメント申し訳ありません。

TCap 型と TCost 型の演算

キャストの案は、long より表現力が大きい型での実装で困らないようにしたいので最終手段感がありますね。

IMcfOperator の案で、 INumOperator<TCap>/INumOperator<TCost> を両方実装し、かつTCost Multiply(TCap x, TCost y) を実装するインターフェイスを用意するというのが最もC++に忠実で、かつ重複した実装にならない実装になるかなと思います。双方 TValue にするというのもユーザーに優しくありますし、ユーザー側が感じる不便とライブラリ忠実さを考え、ラッパとして TValue で統一するものを用意するのが現実的な落とし所なのかなと思います。

-1 での初期化

MinValue での初期化が意味的にはすっきりする気もしますが、BigInteger などの場合も考えると難しそうだなと思えてきます。ボトルネックになる場所でないですし、明確にｰ1を表すものがローコストですぐ作れるならばそれが良いと思います。

terry-u16 commented 4 years ago

今更ですみません。

IMcfOperator の案で、 INumOperator<TCap>/INumOperator<TCost> を両方実装し、かつTCost Multiply(TCap x, TCost y) を実装するインターフェイスを用意するというのが最もC++に忠実で、かつ重複した実装にならない実装になるかなと思います。

誤解してたら申し訳ないのですが、こういうイメージでしょうか？

public interface IMcfOperator<TCap, TCost> : INumOperator<TCap>, INumOperator<TCost>
    where TCap : struct
    where TCost : struct
{
    TCost Multiply(TCap x, TCost y);
}

public class McfGraph<TCap, TCost, TMcfOp>
    where TCap : struct
    where TCost : struct
    where TMcfOp : IMcfOperator<TCap, TCost>
{
}

public class McfGraphWrapper<TValue, TMcfOp> : McfGraph<TValue, TValue, TMcfOp>
    where TValue : struct
    where TMcfOp : IMcfOperator<TValue, TValue>
{
}

これでできれば綺麗だなと思ってちょっと試そうとしたのですが、1行目のところで同じインターフェースを複数実装するなとコンパイラに怒られてしまいました……。やっぱりやるならTCapOp, TCostOp, TMcfOpの3つを渡す必要がありそうです。

key-moon commented 4 years ago

1行目のところで同じインターフェースを複数実装するなとコンパイラに怒られてしまいました……

本当ですね、気が付きませんでした……（本当に申し訳ないです。）

本家 ACL と同等のことを実現できるようにはしたいため

public class McfGraphWrapper <TCap, TCapOp, TCost, TCostOp, TMcfOp>

を作り、かつ public class McfGraphWrapper<TValue, TMOp> も作成すると良さそうだなと思いました。

なお、CostとCapを別にしたいクリティカルな場面は片方が浮動小数点数になっている、のような場面しか思い浮かびませんでした……

kzrnm commented 4 years ago

演算インターフェイスと同様、キャストインターフェイスとするのはどうでしょうか。

public interface ICastOperator<TFrom, TTo>
    where TFrom : struct
    where TTo : struct
{
    TTo Cast(TFrom y);
}
public struct SameTypeCast<T> : ICastOperator<T, T> where T : struct
{
    public T Cast(T y) => y;
}
public struct IntToLongCast : ICastOperator<int, long>
{
    public long Cast(int y) => y;
}
public struct LongToIntCast : ICastOperator<long, int>
{
    public int Cast(long y) => (int)y;
}

op.Multiply(cst.Cast(cap), cost) と使用できます。

TCap → TCost が暗黙の変換がない(例: long → int)場合は正しくない結果になりえますが、それは IMcfOperator でも同じ話かと思います。

takytank commented 4 years ago

キャスト interface は確かに良さそうです。 IMcfOperator よりも役割が明確かつ汎用性があって、最小費用流の実装にあたっては十分ですから、この方針でいこうかと思います。

public interface ICastOperator<TFrom, TTo>
    where TFrom : struct
    where TTo : struct
{
    TTo Cast(TFrom y);
}

public struct SameTypeCastOperator<T> : ICastOperator<T, T> 
    where T : struct
{
    public T Cast(T y) => y;
}

public struct IntToLongCastOperator : ICastOperator<int, long>
{
    public long Cast(int y) => y;
}

public class McfGraph<TCap, TCapOp, TCost, TCostOp, TCast>
    where TCap : struct
    where TCapOp : struct, INumOperator<TCap>
    where TCost : struct
    where TCostOp : struct, INumOperator<TCost>
    where TCast : ICastOperator<TCap, TCost>
{
    //他は省略
    cost = costOp.Add(cost, costOp.Multiply(c, cast.Cast(d)));
}

public class McfGraphInt : McfGraph<int, IntOperator, int, IntOperator, SameTypeCastOperator<int>>
{
}

public class McfGraphIntLong : McfGraph<int, IntOperator, long, LongOperator, IntToLongCastOperator>
{
}

一番下のint型とlong型を混ぜるラッパーに関しては、こういう風に書きますという例でここには書きましたが、用意する必要は無いのかな思っています。（long型のラッパーは作ります。）

key-moon commented 4 years ago

キャストについて検討したのですが、実装の面で問題が起こることは基本的にはなさそうですね。設計としても #56 で考えたような Operator を個別で実装する実装と近いものがあったため、同様に分けて実装を行うのが良いかなと思いました。

ただ、C++ の完全な移植とはならない部分（BigInteger と int との乗算などに挙げられる別の型同士での乗算がパフォーマンス改善）はありますが、レアケースであるために問題ないかと考えました。

kzrnm / ac-library-csharp

MinCostFlow/MaxFlow のインターフェイスについて #33

20 より。

24 の話をまとめると、上で実装して頂いた

38 にて `INumOperator` を実装して頂いているので、そちらの仕様も確認して頂けると嬉しいです。

-1 での初期化

TCap 型と TCost 型の演算

TCap 型の -1 での初期化

TCap 型と TCost 型の演算

kzrnm / ac-library-csharp

MinCostFlow/MaxFlow のインターフェイスについて #33

20 より。

24 の話をまとめると、上で実装して頂いた

38 にて INumOperator を実装して頂いているので、そちらの仕様も確認して頂けると嬉しいです。

-1 での初期化

TCap 型と TCost 型の演算

TCap 型の -1 での初期化

TCap 型と TCost 型の演算

38 にて `INumOperator` を実装して頂いているので、そちらの仕様も確認して頂けると嬉しいです。