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

算術シフト、論理シフト

using System;

class Program {
    static void Display(int n) {
        Console.WriteLine(" int {0,12} {1,32}", n, Convert.ToString(n, 2));
    }

    static void Display(uint n) {
        Console.WriteLine("uint {0,12} {1,32}", n, Convert.ToString(n, 2));
    }

    static void Main() {
        int si = 1 << 31;
        Display(si);
        Display(si >> 1);
        Display(si >> 4);

        uint ui = 1U << 31;
        Display(ui);
        Display(ui >> 1);
        Display(ui >> 4);
    }
}

実行結果です。

 int  -2147483648 10000000000000000000000000000000
 int  -1073741824 11000000000000000000000000000000
 int   -134217728 11111000000000000000000000000000
uint   2147483648 10000000000000000000000000000000
uint   1073741824  1000000000000000000000000000000
uint    134217728     1000000000000000000000000000

int(符号付き)だと、最上位ビット(符号ビット)が保存されたままになっています。

参考

関数から整数(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> インターフェースを実装しているなら、インデックスによるアクセスで最後の要素を取得しています。

まとめ