読者です 読者をやめる 読者になる 読者になる

関数から整数(int)を 2 つ返すとき、配列とタプルの速度差を調べる

int の配列を new するのと、タプルを生成するのとで速度に差が出るのか計測してみました。

using System;
using System.Diagnostics;

class Program {
    static int[] CreateArray(int a, int b) {
        return new[] { a, b };
    }

    static Tuple<int, int> CreateTuple(int a, int b) {
        return Tuple.Create(a, b);
    }

    static void Test(int n) {
        Console.WriteLine($"n = {n}");

        var sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < n; i++) {
            CreateArray(1, 2);
        }
        sw.Stop();
        Console.WriteLine($"array: {sw.ElapsedMilliseconds}ms");

        sw.Restart();
        for (int i = 0; i < n; i++) {
            CreateTuple(1, 2);
        }
        sw.Stop();
        Console.WriteLine($"tuple: {sw.ElapsedMilliseconds}ms");
        Console.WriteLine();
    }

    static void Main() {
        for (int i = 1; i < 10; i++) {
            Test((int)Math.Pow(10, i));
        }
    }
}

実行結果です。

n = 10
array: 0ms
tuple: 0ms

n = 100
array: 0ms
tuple: 0ms

n = 1000
array: 0ms
tuple: 0ms

n = 10000
array: 0ms
tuple: 0ms

n = 100000
array: 2ms
tuple: 1ms

n = 1000000
array: 10ms
tuple: 10ms

n = 10000000
array: 115ms
tuple: 109ms

n = 100000000
array: 1099ms
tuple: 1031ms

n = 1000000000
array: 11613ms
tuple: 10352ms

上記のコードで計測する限りでは、速度に大きな差は見られませんでした。

環境

% mono --version
Mono JIT compiler version 4.6.2 (Stable 4.6.2.16/ac9e222 Sat Jan  7 16:00:28 PST 2017)
Copyright (C) 2002-2014 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com

0 と 1 を交互に繰り返したいときは xor を使う

変数に格納されている整数値が、

  • 0 のときは 1 を返す
  • 1 のときは 0 を返す

というように 0 と 1 を交互に繰り返したいときは、1 と xor するとできます。

$ csharp
Mono C# Shell, type "help;" for help

Enter statements below.
csharp> int a = 0;
csharp> a ^ 1
1
csharp> (a ^ 1) ^ 1
0
csharp> ((a ^ 1) ^ 1) ^ 1
1

文字列リテラルにダブルクォートを含める

文字列リテラルにダブルクォートを含めるには、次のようにします。

  • 標準の文字列リテラルなら、バックスラッシュでエスケープします
  • 逐語的文字列リテラルなら、ダブルクォートを 2 つ重ねます
using System;

class Program {
    static void Main() {
        Console.WriteLine("<a href=\"http://www.google.co.jp\">Google</a>");

        // 逐語的文字列リテラル(vervatim string literal)
        Console.WriteLine(@"<a href=""http://www.google.co.jp"">Google</a>");
    }
}

実行結果です。

<a href="http://www.google.co.jp">Google</a>
<a href="http://www.google.co.jp">Google</a>

IEnumerable, IEnumerator

GetEnumerator() を定義すると、foreach でループを回すことができます。

using System;
using System.Collections;
using System.Collections.Generic;

class Program {
    static IEnumerable<int> G() {
        yield return 1;
        yield return 2;
    }

    static IEnumerator<int> T() {
        yield return 3;
        yield return 4;
    }

    static void Main() {
        // コンパイルエラー:
        //     error CS1579: foreach statement cannot operate on variables of type
        //     `System.Collections.Generic.IEnumerator<int>'
        //     because it does not contain a definition for `GetEnumerator'
        //     or is inaccessible
        // foreach (var a in T())
        //     Console.WriteLine(a);

        var g = G().GetEnumerator();
        while (g.MoveNext()) {
            Console.WriteLine(g.Current);
        }

        var t = T();
        while (t.MoveNext()) {
            Console.WriteLine(t.Current);
        }
    }
}

実行結果です。

1
2
3
4

プロパティでコルーチン

プロパティでコルーチンを定義するサンプルです。

using System;
using System.Collections.Generic;
using System.Linq;

class Test {
    public IEnumerable<int> G {
        get {
            int n = 0;
            while (true) {
                yield return n++;
            }
        }
    }
}

class Program {
    static void Main() {
        Console.WriteLine(string.Join(" ", new Test().G.Take(5)));
        //=> 0 1 2 3 4
    }
}

実行結果です。

0 1 2 3 4

速度のために List クラスに Last 拡張メソッドを定義しようとしたけど要らなかった

やろうとしたこと

  • List<T> の最後の要素を取得するメソッドが欲しい
  • Enumerable.Last メソッドがある
    • だけど、シーケンスを辿るので O(N) で遅いのでは?

先に結論から言うと、IList<T> インターフェース を実装しているなら、 Enumerable.Last は O(N) ではなく O(1) になります。後ほど、Enumerable.Last の実装をみます。

List.MyLast 拡張メソッドを定義して、速度を計測してみた

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public static class Extension {
    public static T MyLast<T>(this List<T> list) {
        return list[list.Count - 1];
    }
}

class Program {
    static void TestLast(int n, int m) {
        var xs = Enumerable.Range(0, m).ToList();
        var sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < n; i++) {
            xs.Last();
        }
        sw.Stop();
        Console.WriteLine("Last  : n:{0} time:{1}", n, sw.ElapsedMilliseconds);
    }

    static void TestMyLast(int n, int m) {
        var xs = Enumerable.Range(0, m).ToList();
        var sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < n; i++) {
            xs.MyLast();
        }
        sw.Stop();
        Console.WriteLine("MyLast: n:{0} time:{1}", n, sw.ElapsedMilliseconds);
    }

    static void Main() {
        int size = 1000000;
        foreach (var x in new[] { 1000000, 10000000 }) {
            TestLast(x, size);
            TestMyLast(x, size);
        }
    }
}

実行結果です。

Last  : n:1000000 time:13
MyLast: n:1000000 time:5
Last  : n:10000000 time:117
MyLast: n:10000000 time:45

2 倍程度しか差がありません。

Enumerable.Last の実装をみてみる

Reference Source の Enumerable.Last の実装 をみてみると、as 演算子IList<T> インターフェース を実装しているか確認しています。もし、IList<T> インターフェースを実装しているなら、インデックスによるアクセスで最後の要素を取得しています。

まとめ

タプルを == 演算子で比較、Equals() で比較

using System;

class Program {
    static void Main() {
        var a = Tuple.Create(1, 2);
        var b = Tuple.Create(1, 2);

        Console.WriteLine(a == b);      // False
        Console.WriteLine(a.Equals(b)); // True
    }
}

実行結果です。

False
True

タプルを Dictionary のキーにしてみる

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var a = Tuple.Create(1, 2);
        var b = Tuple.Create(1, 2);

        var dict = new Dictionary<Tuple<int, int>, int>();
        dict[a] = 12;
        Console.WriteLine(dict[a]); // 12
        dict[b] = 30;
        Console.WriteLine(dict[a]); // 30
        Console.WriteLine(dict[b]); // 30
    }
}

実行結果です。

12
30
30

タプルを HashSet に格納

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var a = Tuple.Create(1, 2);
        var b = Tuple.Create(1, 2);

        var hs = new HashSet<Tuple<int, int>>();
        hs.Add(a);
        Console.WriteLine(hs.Contains(b)); // True
    }
}

実行結果です。

True