search

kzrnm / ac-library-csharp

42 stars 5 forks source link

Expander ライブラリを作成 #50

Closed kzrnm closed 4 years ago

kzrnm commented 4 years ago

Expander の実装方法をいろいろ検討して、C# のみで完結してなおかつオーバーヘッドが小さい手法を思いついたので作成してみました。

の2つの機能にわかれているのでそれぞれ説明します。

GitHub Actions によるソースコード埋め込み

SourceCodeEmbeder を GitHub Actions で実行して、AtCoderLibrary にソースコード埋め込みファイルを自動コミットします。

ソースコード埋め込み用の型には EditorBrowsable(EditorBrowsableState.Never) をつけているので通常のライブラリ利用者からは見れません。

SourceCodeEmbeder が行うこと

GitHub Actions の実行例

https://github.com/naminodarie/ac-library-cs/actions/runs/255529330

埋め込んだソースコードを利用するライブラリ

Expander が埋め込んだソースコードを展開するライブラリです。

README を書いてます。

https://github.com/naminodarie/ac-library-cs/blob/expander_cs/AtCoderLibrary.Expander/README.md

using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using AtCoder;
using FenwickTree = AtCoder.IntFenwickTree;

class Program
{
    static void Main(string[] args)
    {
        var expandMethod = ExpandMethod.All;
        //var expandMethod = ExpandMethod.NameSyntax;
        //var expandMethod = ExpandMethod.Strict;
        Console.WriteLine(expandMethod);
        var sw = Stopwatch.StartNew();

        Expander.Expand(expandMethod: expandMethod);
        Console.WriteLine($"expand time: {sw.ElapsedMilliseconds} ms");
        var fw = new FenwickTree(5);
        for (int i = 0; i < 5; i++) fw.Add(i, i + 1);
        Console.WriteLine(fw.Sum(0, 5));
        Console.WriteLine($"finish time: {sw.ElapsedMilliseconds} ms");
    }
}

struct Monoid : IMonoidOperator<int>
{
    public int Identity => 0;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int Operate(int x, int y) => x + y;
}
class Segtree : Segtree<int, Monoid> { public Segtree(int n) : base(n) { } }

上記のようなファイルでためしたところ実行時間はそれぞれ

ExpandMethod expand time (ms)
All 40 ms
NameSyntax 300 ms
Strict 1200 ms

程度となりました。

21

key-moon commented 4 years ago

かなり本家と毛色が違う Expand 方法なので、これがどのようにコミュニティに受け入れられるかは分からないため議論無しで自信を持ってマージすることができません。

個人的には、便利ではあるが少し自由が効かない方法だという印象を持ちました。毎デバッグの際にこれが実行されるのはあまり嬉しくはなさそうです。

コードベースとして依存フロー解析のコードはとても助かります。GitHub Actionでフロー解析を前処理しておくのは合理的ですし、Expander 自体に埋め込んでしまえば余計なファイルも気になりませんね。 #21 に今までの話を追記しておくので、検討段階での試案や採用しなかった理由/デメリットについても書いて頂けると助かります。

kzrnm commented 4 years ago

毎デバッグの際にこれが実行されるのはあまり嬉しくはなさそうです。

そう思いまして、Combined.csx にタイムスタンプを埋め込む機能を一応作っています。

Program.cs にこっそり書いてるのですが、

// do nothing if file is not updated.
Expander.Expand(checkLastWriteTime: true);

とすると $"Last: {ファイルの更新日時.Ticks}" が Combined.csx の先頭に埋め込まれて、更新されていなかったら何もせずに終了します。

kzrnm commented 4 years ago

21 に検討した内容を書き連ねました。

kzrnm commented 4 years ago

ファイルの中から直接呼び出すのではなくPowerShellから呼び出すサンプルを追加しました。

kzrnm commented 4 years ago

master を取り込みました。

kzrnm commented 4 years ago

Expander はCC0にしたくないので一旦閉じます。