「Yay! You’re on Rails!」はどこに？

rails ruby

Railsのチュートリアルをしていて一番最初に気になったのが、
サーバを起動して最初に表示される「Yay! You’re on Rails!」のページでした。

以前はpublic/index.html にあったらしいのですが見当たらないので、置き場所が変わったのかと思い
「Yay! You’re on Rails!」をgrep。
ヒットしない...
routes.rbも空...

答えはここにありました。
ライブラリ側でビルトインとして定義してあるんですね。

規則性に基づいて要素を分割する拡張メソッド

C# .NET LINQ

同じ要素が途切れるところで分割する拡張メソッドがほしかったのでMoreLINQや他のサイトを探したのですが、
それらしいのが見当たらなかったので実装しました。

やりたいことはこんな感じです。※GroupByとかLookupではありません。

[1, 1, 1, 2, 2, 3, 3, 4, 1, 1] → [[1, 1, 1], [2, 2], [3, 3], [4], [1, 1]]

ただ、もう少し拡張性がほしいので、規則性に基づいて要素を分割する拡張メソッドにしました。

では実装です。

public static IEnumerable<IEnumerable<T>> SplitByRegularity<T>(
    this IEnumerable<T> source, Func<List<T>, T, bool> predicate)
{
    using (var enumerator = source.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            yield break;

        var items = new List<T> { enumerator.Current };
        while (enumerator.MoveNext())
        {
            if (predicate(items, enumerator.Current))
            {
                items.Add(enumerator.Current);
                continue;
            }

            yield return items;

            items = new List<T> { enumerator.Current };
        }

        if (items.Any())
            yield return items;
    }
}

やっていることは単純です。

  1. 入力されたシーケンスをループで回す
  2. 引数で渡された規則性があるかを判定するメソッド(predicate)を実行
  3. 結果がtrueの場合は一時リストに追加、falseのときは一時リストを返す

predicateの引数に一時リストそのものを渡しているところがポイントです。


実際の使用例をいくつか紹介します。

  • 同じ要素が連続しているという規則性
var source = new List<int> { 1, 1, 1, 2, 2, 3, 3, 4, 1, 1 };
var result = source.SplitByRegularity((items, current) => items.First().Equals(current));

// [[1, 1, 1], [2, 2], [3, 3], [4], [1, 1]]
  • 増加するという規則性
var source = new List<int> { 1, 2, 4, 1, 2, -1, 0, 3, 2, 1 };
var result = source.SplitByRegularity((items, current) => items.Last() <= current);

// [[1, 2, 4], [1, 2], [-1, 0, 3], [2], [1]]
  • 連続するという規則性
var source = new List<int> { 1, 2, 3, 2, 0, -1, -2, -1, 2, };
var result = source.SplitByRegularity((items, current) => current == items.Last() + 1 || current == items.Last() - 1);

// [[1, 2, 3, 2], [0, -1, -2, -1], [2]]
  • 重複がないという規則性
var source = new List<int> { 1, 2, 3, 1, 5, 6, 5, 7, 8, 9, 9, 9 };
var result = source.SplitByRegularity((items, current) => !items.Contains(current));

// [[1, 2, 3], [1, 5, 6], [5, 7, 8, 9], [9], [9]]

他にも、よく見かけるサイズで分割するSplitなんかもできます。

  • 要素数が3以下という規則性
var source = new List<int> { 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6, 6 };
var result = source.SplitByRegularity((items, current) => items.Count <= 2);

// [[1, 1, 1], [2, 2, 3], [3, 3, 3], [4, 4, 5], [6, 6]]


同じ要素が連続しているや要素数が〇以下は使用頻度が高そうなので、
別に定義してもいいかもしれません。

public static IEnumerable<IEnumerable<T>> SplitBySize<T>(
    this IEnumerable<T> source, int size)
{
    return source.SplitByRegularity((items, current) => items.Count < size);
}

public static IEnumerable<IEnumerable<T>> SplitByEquality<T>(
    this IEnumerable<T> source)
{
    return source.SplitByRegularity((items, current) => items.Last().Equals(current));
}

C#でDiffアルゴリズムを実装してみた

C# .NET

こちらで実装の詳細を書くと言ったので、書きたいと思います。

はじめに

C#実装のDiffライブラリはいくつかあったのですが、自分で実装したのは以下の理由からです。

  1. 差分抽出対象を文字列限定にしたくない
  2. IEqualityComparerを指定して比較方法を外部から指定したい
  3. 最短経路が複数存在する場合に、どの経路を採用するかを制御したい(後ほど詳しく解説します)
  4. 巨大データの差分を抽出するときに精度を落として高速化したい
  5. アルゴリズムの理解を深めたい

実装の解説

アルゴリズムについての詳細は、既に分かりやすく解説してくれているサイトがあるのでそちらを参考にして下さい。
Diff algorithm - 枕を欹てて聴く

1. EditGraph の作成

今回は good と dog の差分を例にして、差分結果が以下のようになることを目標とします。

g d o o g d
- + = - + -

EditGraphを作成すると以下のようになります。


f:id:skanmera:20170924004809p:plain:w500

2. 編集距離(d) = 0

  1. 各k線に対する最遠点の配列farthestPointsと現在の先端ノードのリストheadsを初期化する
  2. 先端ノードのリストに原点のノードを追加する
  3. 追加したノードを斜めに進めるだけ進める

dog と good では(0, 0)から(1, 1)に進めないので以下のようになります。

f:id:skanmera:20170924010321p:plain:w500

3. 編集距離(d) = 1

  1. 右側に進める場合は進める
  2. 下側に進める場合は進める

進めるか進めないかの判定は以下の2点となります。

  1. 進めた先の点～最終点 の距離が、対応するk線における最遠点～最終点 の距離以下か (言い換えると最遠点を更新できるか、もしくは最遠点と同じか)
  2. EditGraphの範囲内か

d = 1のときはどちらも進めるので次のようになります。

f:id:skanmera:20170924011013p:plain:w700

4. 編集距離(d) = 2

同様に右、下に進めます

f:id:skanmera:20170924011957p:plain:w500

このとき(1,1)で複数のノードが存在してしまいます。
ここで指定された条件に最も合うものを採用します。
これが冒頭で述べた最短経路が複数存在する場合に、どの経路を採用するかを制御したいという処理になります。

この時点で ①を採用した場合は

g d
- +

となり
②を採用した場合は

d g
+ -

となります。

今回は差分結果

g d o o g d
- + = - + -

となることを目標にしているので、①を採用する必要があります。

そこで、各ノードにスコアを持たせてスコアで判定するようにします。
スコアは座標が更新されるごとにその座標を加算していくようにします。
①の場合は(0, 0) ⇒ (1, 0) ⇒ (1, 1) なので (2, 1)となり、ScoreX = 2, ScoreY = 1となります。
②の場合は(0, 0) ⇒ (0, 1) ⇒ (1, 1) なので (1, 2)となり、ScoreX = 1, ScoreY = 2となります。

g d o o g d
- + = - + -

は削除優先なのでScoreXが大きいを①を採用すればいいことが分かります。

さらに、(1, 1)から(2, 2)は進めるので、最終的にこうなります。

f:id:skanmera:20170924015104p:plain:w500

5. 編集距離(d) = 3

編集距離が3の場合は次のようになり、今度は(3, 2)で複数のノードが存在します。
①の場合は(0, 0) ⇒ (1, 0) ⇒ (1, 1) ⇒ (2, 2) ⇒ (3, 2) なので (7, 5)となり、ScoreX = 7, ScoreY = 5となります。
②の場合は(0, 0) ⇒ (1, 0) ⇒ (2, 0) ⇒ (2, 1) ⇒ (3, 2) なので (8, 3)となり、ScoreX = 8, ScoreY = 3となります。

ここで削除優先なのでScoreXが大きいほう➂を採用してしまうと

g o d o
- - + =

となり、目標と相違してしまいます。
そこで、ノードにスコアとは別に直進した回数StraightCountを持たせます。

①の場合は一回も直進してないので StraightCount = 0 となります
➁の場合は(0, 0) ⇒ (1, 0) ⇒ (2, 0) で直進しているので StraightCount = 1 となります
※斜めに直進した回数はカウントしません。

StraightCountが一番小さいものを採用します。
もし複数ある場合はその中でScoreXが大きいものを採用すればいいわけです。

結果は次のようになります。

f:id:skanmera:20170924021219p:plain:w500

5. 終了処理

以降は、先端ノードのいずれかが終点に達するまで同じことを繰り返すだけです。
終点に達したら親ノードをたどって経路を返してあげるだけです。

最終的にはこうなります。

f:id:skanmera:20170924021817p:plain:w500

5. 高速化

このアルゴリズムのオーダーはO(ND)なので、入力データが大きくなればなるほど時間がかかります。
そこで巨大なデータの差分を抽出するときはある程度精度を落として、高速化するようにしました。
具体的には、先端のノード数が指定した数を超えた場合に、その時点で最も条件に当てはまるノードを選択して、
それ以外は切り捨てるようにしました。
高速化される分、冗長な差分が含まるようになります。

ソースコードについてはここに書いたことをそのまま落とし込んでるだけなので見ていただければ分かるかと思います。

github.com

エクセルの差分を抽出するツールを作ってみた

.NET C# Excel

久しぶりの更新です。
作業が脱線しまくりで、なにも成果物がなかったのですが、やっと書く内容ができました。

普段仕事でエクセルの差分を見るときはWinMergeのxdocdiffプラグインを使用しているのですが、
変更が多いと差分を確認するのが大変で、ちょっとしたストレスを感じてました。

他に良さげなツールはないかと何回か探しましたが見つからず、この際自分で作ってしまおうと思い作りました。

意外と使えそうだったのでGitHubで公開してます。(プロジェクトがExcelMergeとなっているのはマージ機能を実装する予定だからです)

github.com

以前実装したDiffのアルゴリズムを使用しているので、次回はそちらの詳細を書こうと思います。

UnityのHandlesクラスの拡張

C# Unity

Unityで幾何学のアルゴリズムを実装するときに、イメージがしやすいようにHanldesクラスを拡張してデバッグ描画できるようにしました。
以下のようなコードを書くと追加されたDrawerの順に描画されていきます。

var drawer = new Drawer();
var cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
var mesh = cube.GetComponent<MeshFilter>().sharedMesh;

for (int i = 0; i < mesh.triangles.Length;)
{
    var a = mesh.vertices[mesh.triangles[i++]];
    var b = mesh.vertices[mesh.triangles[i++]];
    var c = mesh.vertices[mesh.triangles[i++]];

    var triangleProp = new TriangleDrawProperty()
    {
        VertexA = a,
        VertexB = b,
        VertexC = c,
        VertexAColor = Color.cyan,
        VertexBColor = Color.cyan,
        VertexCColor = Color.cyan,
        EdgeABColor = Color.green,
        EdgeBCColor = Color.green,
        EdgeCAColor = Color.green,
    };

    var triangleDrawer = new TriangleDrawer(triangleProp);

    drawer.Drawers.Add(triangleDrawer);
}

DrawerManager.Instance.AddDrawer("cube", drawer);
GameObject.DestroyImmediate(cube);



特定の箇所だけ一気に描画できるようにしました。

triangleDrawer.BatchDraw = true;

とるすと一個の三角形を一気に描画します。


drawer.BatchDraw = true;

とするとすべての三角形を一気に描画します。



動画の円を描いている部分は以下のコードです。

var circlesDrawer = new Drawer();
for (int i = 0; i <= 36; i++)
{
    var circleDrawerProp = new CircleDrawProperty();
    circleDrawerProp.Center = UnityEngine.Vector3.zero;
    circleDrawerProp.Angle = 10 * i;
    circleDrawerProp.Color = Color.yellow;
    var d = i / 70f;
    circleDrawerProp.From = new Vector3(0.1f + d, 0.1f + d, 0.1f + d);
    circleDrawerProp.Radius = Vector3.Distance(circleDrawerProp.Center, circleDrawerProp.From);
    var vec1 = circleDrawerProp.From - circleDrawerProp.Center;
    var vec2 = new Vector3(-0.1f - d, -0.1f - d, 0.0f) - circleDrawerProp.Center;
    var normal = Vector3.Cross(vec1, vec2).normalized;
    circleDrawerProp.Normal = normal;
    var circleDrawer = new CircleDrawer(circleDrawerProp);
    circlesDrawer.Drawers.Add(circleDrawer);
}

DrawerManager.Instance.AddDrawer("circle", circlesDrawer);


unity debug draw



もうすこし機能を追加して公開したいと思います。

組み合わせの等価性を比較するIEqualityComparerのGetHashCode

C# .NET

例えば以下のようなクラスがあったとして

class Pair
{
    public int Value1 { get; }
    public int Value2 { get; }

    public Pair(int value1, int value2)
    {
        Value1 = value1;
        Value2 = value2;
    }
}


Value1とValue2の組み合わせが等しいかを比較したくて次のようなIEqualityComparerを実装したとします。

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }
}


このとき、GetHashCodeの実装はどうしたらいいのでしょうか。


もちろん、以下のコードはこれは意図した挙動になりません。

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        obj.GetHashCode();
    }
}



Equalsが正しく実装されていれば、以下のようなコードを書いても想定通りに動きます。

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        return 0;
    }
}

ただこれは線形サーチになるのでかなり遅いです。



私はいつも次のような実装をしています。(正しいかどうかは分かりません)

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        var val1 = Math.Min(obj.Value1, obj.Value2);
        var val2 = Math.Max(obj.Value1, obj.Value2);

        var hash = 17;
        hash = hash * 23 + val1.GetHashCode();
        hash = hash * 23 + val2.GetHashCode();

        return hash;

    }
}

ソートしてからハッシュを計算します。
独自クラスの場合はIComparerを実装してソートします。



一応検証コードを載せときます。

class Pair
{
    public int Value1 { get; }
    public int Value2 { get; }

    public Pair(int value1, int value2)
    {
        Value1 = value1;
        Value2 = value2;
    }
}

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        return obj.GetHashCode();
    }
}

class Program
{
    static void Main(string[] args)
    {
        var pairs = new HashSet<Pair>(new PairEqualityComparer());

        var sw = new Stopwatch();
        sw.Start();

        var count = 0;
        while (count < 100000)
        {
            pairs.Add(new Pair(count, 100000 - count));
            count++;
        }

        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        Console.WriteLine(pairs.Count());
        Console.ReadLine();
    }
}

結果

00:00:00.0231028
100000


class Pair
{
    public int Value1 { get; }
    public int Value2 { get; }

    public Pair(int value1, int value2)
    {
        Value1 = value1;
        Value2 = value2;
    }
}

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        return 0;
    }
}

class Program
{
    static void Main(string[] args)
    {
        var pairs = new HashSet<Pair>(new PairEqualityComparer());

        var sw = new Stopwatch();
        sw.Start();

        var count = 0;
        while (count < 100000)
        {
            pairs.Add(new Pair(count, 100000 - count));
            count++;
        }

        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        Console.WriteLine(pairs.Count());
        Console.ReadLine();
    }
}

結果

00:01:25.4922908
50001


class Pair
{
    public int Value1 { get; }
    public int Value2 { get; }

    public Pair(int value1, int value2)
    {
        Value1 = value1;
        Value2 = value2;
    }
}

class PairEqualityComparer : IEqualityComparer<Pair>
{
    public bool Equals(Pair x, Pair y)
    {
        return
            (x.Value1.Equals(y.Value1) && x.Value2.Equals(y.Value2)) ||
            (x.Value1.Equals(y.Value2) && x.Value2.Equals(y.Value1));
    }

    public int GetHashCode(Pair obj)
    {
        var val1 = Math.Min(obj.Value1, obj.Value2);
        var val2 = Math.Max(obj.Value1, obj.Value2);

        var hash = 17;
        hash = hash * 23 + val1.GetHashCode();
        hash = hash * 23 + val2.GetHashCode();

        return hash;
    }
}

class Program
{
    static void Main(string[] args)
    {
        var pairs = new HashSet<Pair>(new PairEqualityComparer());

        var sw = new Stopwatch();
        sw.Start();

        var count = 0;
        while (count < 100000)
        {
            pairs.Add(new Pair(count, 100000 - count));
            count++;
        }

        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        Console.WriteLine(pairs.Count());
        Console.ReadLine();
    }
}

結果

00:00:00.0221448
50001