IEnumerable<T> のランダムな要素を選択する
上の記事で紹介されている「要素全体をメモリに保持せずに、ランダムな要素を選択する」アルゴリズムが面白いです。
C# で書いてみました。
public static class Extensions { // source が空だったり、配列やリストの場合の対応は後述 public static T RandomChoice<T>(this IEnumerable<T> source, Random random) { T selected = default(T); int n = 1; foreach (var e in source) { if (random.Next(n) == 0) selected = e; n++; } return selected; } }
お試しコード。
class Program { static void Main() { var xs = Enumerable.Range(0, 10).ToArray(); var random = new Random(); var freq = new int[xs.Length]; for (int i = 0; i < 1000000; i++) { int x = xs.RandomChoice(random); freq[x]++; } for (int i = 0; i < freq.Length; i++) Console.WriteLine("{0} : {1}", i, freq[i]); } }
実行結果です。
0 : 100246 1 : 99682 2 : 100206 3 : 100504 4 : 99295 5 : 100318 6 : 99000 7 : 100538 8 : 100414 9 : 99797
配列やリストへの対応
IEnumerable<T>
の元が配列やリストの場合は、そもそも要素をループする必要がありません。Enumerable.Last が行っているように、IList<T>
を実装しているなら、ループを回さないようにします。
要素が空かどうかのチェックも入れておきます。
public static class Extensions { public static T RandomChoice<T>(this IEnumerable<T> source, Random random) { if (source == null) throw new ArgumentNullException(nameof(source)); var list = source as IList<T>; if (list != null) { if (list.Count > 0) return list[random.Next(list.Count)]; } else { using (var e = source.GetEnumerator()) { if (e.MoveNext()) { int n = 1; T selected = default(T); do { if (random.Next(n) == 0) selected = e.Current; n++; } while (e.MoveNext()); return selected; } } } throw new InvalidOperationException("source is empty"); } }
インターフェース型の変数への代入と 3 項演算子を組み合わせるとコンパイルエラーになる
クラス A と、クラス B が IDisposable
を実装しているとします。
そのときに、3 項演算子を用いて、以下のように書くことはできないようです。
class A : IDisposable { ... } class B : IDisposable { ... } // コンパイルエラーになる: There is no implicit conversion between 'A' and 'B' IDisposable c = true ? new A() : new B();
IDisposable
でキャストすれば問題なくコンパイルできます。
// OK IDisposable c = true ? (IDisposable)new A() : (IDisposable)new B();
あるいは、いったん IDisposable
型の変数に格納しておいてから、3 項演算子を使う方法もあります。
IDisposable a = new A(); IDisposable b = new B(); var c = true ? a : b; // OK
背景
あるオブジェクトの配列があり、それをいくつかの異なる方法でソートする必要がでてきました。
そのため、それぞれの比較方法に応じた IComparer
を実装するクラスを用意して、
それを Sort
メソッドに渡してソート方法を切り替えようと考えました。
Sort
メソッドに IComparer
を渡すときに 3 項演算子を使おうとしたのですが、
コンパイルエラーになりましたので、かわりに IComparer
を返すメソッドを作成するようにしました。
おおよそ以下のようなコードを書きました。
using System; using System.Collections.Generic; class Foo {} // Foo をある方法 A で比較 class ComparerA : IComparer<Foo> { public int Compare(Foo x, Foo y) { throw new NotImplementedException(); } } // Foo をある方法 B で比較 class ComparerB : IComparer<Foo> { public int Compare(Foo x, Foo y) { throw new NotImplementedException(); } } class Program { static void Main() { var foos = new[] { new Foo() }; Array.Sort(foos, new ComparerA()); // 方法 A でソート Array.Sort(foos, new ComparerB()); // 方法 B でソート // フラグでソート方法を切り替える。 // 本当はこう書きたかったがコンパイルエラー: // There is no implicit conversion between 'ComparerA' and 'ComparerB' // Array.Sort(foos, true ? new ComparerA() : new ComparerB()); // 3 項演算子が使えないので、IComarer を返すメソッドを用意した Array.Sort(foos, CreateComparer(true)); } static IComparer<Foo> CreateComparer(bool flag) { if (flag) return new ComparerA(); return new ComparerB(); } }
構造体を定義すると Equals が自動的に実装されるが、IEquatable<T> を実装した方がよい
方法: 型の値の等価性を定義する (C# プログラミング ガイド) | Microsoft Docs より:
構造体を定義すると、System.Object.Equals(Object) メソッドの System.ValueType オーバーライドから継承された値の等価性が既定で実装されます。 この実装では、リフレクションを使用して、型のフィールドとプロパティをすべて調べます。 この実装によって正しい結果が生成されますが、その型専用に記述したカスタム実装と比較すると、処理にかなり時間がかかります。
自作の Point 構造体を定義して、配列、HashSet, Dictionary から値を検索できるか確認してみます。値の等価性の確認です。
using System; using System.Collections.Generic; class Program { struct Point { public int X { get; } public int Y { get; } public Point(int x, int y) { X = x; Y = y; } } static void Main() { void p<T>(T o) => Console.WriteLine(o); var a = new Point(1, 2); var b = new Point(1, 2); // a を格納した配列から b を見つける p(Array.IndexOf(new[] { a }, b)); // 0 // a を格納した HashSet から b を見つける var hs = new HashSet<Point>() { a }; p(hs.Contains(b)); // True // a を格納した Dictionary から b を見つける var d = new Dictionary<Point, bool>() { [a] = true }; p(d.ContainsKey(b)); // True } }
実行結果です。
0 True True
構造体のメンバーごとの比較が行われており、配列、HashSet、Dictionary に格納した場合でも値を見つけることができていることが確認できました。
次に、IEquatable<T>
を実装した場合と、速度比較をしてみます。
using System; using System.Collections.Generic; class Program { struct Point { public int X { get; } public int Y { get; } public Point(int x, int y) { X = x; Y = y; } } // IEquatable<T> を実装した Point 構造体 struct PointImplementsIEquatable : IEquatable<PointImplementsIEquatable> { public int X { get; } public int Y { get; } public PointImplementsIEquatable(int x, int y) { X = x; Y = y; } public bool Equals(PointImplementsIEquatable other) { return X == other.X && Y == other.Y; } public override bool Equals(object other) { if (other is PointImplementsIEquatable) return Equals((PointImplementsIEquatable)other); return false; } public override int GetHashCode() { return X ^ Y; } } static void Benchmark(int n) { var sw = new System.Diagnostics.Stopwatch(); sw.Start(); var xs = new[] { new Point(1, 2), }; for (int i = 0; i < n; i++) { Array.IndexOf(xs, xs[0]); } sw.Stop(); Console.WriteLine($"Point = {sw.ElapsedMilliseconds}ms"); sw.Restart(); var ys = new[] { new PointImplementsIEquatable(1, 2), }; for (int i = 0; i < n; i++) { Array.IndexOf(ys, ys[0]); } sw.Stop(); Console.WriteLine($"Point(IEquatable) = {sw.ElapsedMilliseconds}ms"); } static void Main() { Benchmark(10_000_000); } }
実行結果です。
Point = 895ms Point(IEquatable) = 281ms
IEquatable<T>
を実装したほうが速いようです。Equals() 呼び出し時のボックス化も重いんですかね。
速度のことを考えると、常に IEquatable<T>
を実装したほうが良さそうです。
参考
Mono 5.0 と C# 7 の Local Functions, Tuples で遊ぶ
Mono 5.0 と C# 7 で遊びます。
まずは、mono のアップグレード。
$ brew upgrade mono
mono のバージョンの確認。
$ mono --version Mono JIT compiler version 5.0.1.1 (2017-02/5077205 Wed May 31 14:47:54 BST 2017) Copyright (C) 2002-2014 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com
csc
コマンドでコンパイルして実行します。
$ cat a.cs using System; class Program { static void Main() { Console.WriteLine("Hello C# 7"); } } $ csc a.cs Microsoft (R) Visual C# Compiler version 2.0.0.61404 Copyright (C) Microsoft Corporation. All rights reserved. $ mono a.exe Hello C# 7
C# 7 で遊ぶ準備が整いました。
Local Functions
メソッド名と同じ名前のローカル関数を定義できるようです。 以下では、メソッド名と同じ Add, Sub という名前のローカル関数を定義しています。
using System; class Program { static int Add(int a, int b) { int Add(int x, int y) { return x + y; } return Add(a, b); } static int Sub(int a, int b) { int Sub(int x, int y) => x - y; return Sub(a, b); } static void Main() { Console.WriteLine(Add(10, 23)); // 33 Console.WriteLine(Sub(100, 88)); // 12 } }
ローカル関数の引数には、外側のメソッドと同じ引き数名は付けられないようです。
using System; class Program { static int Add1(int n) { // コンパイルエラー: 引数名 n は外側のメソッドで使われている int Add1(int n) => n + 1; return Add1(n); } static void Main() { } }
$ csc a.cs a.cs(6,22): error CS0136: A local or parameter named 'n' cannot be declared in this scope because that name is used in an enclosing local scope to define a local or parameter
Tuples
using System; class Program { static void Main() { var t = ("Bob", 10); Console.WriteLine($"{t.Item1} {t.Item2}"); // Bob 10 var t2 = (Name: "Bob", Age: 10); Console.WriteLine($"{t2.Name} {t2.Age}"); // Bob 10 (string name, int age) = ("Bob", 10); Console.WriteLine($"{name} {age}"); // Bob 10 (string Name, int Age) bob = ("Bob", 10); Console.WriteLine($"{bob.Name} {bob.Age}"); // Bob 10 var (name2, age2) = ("Bob", 10); Console.WriteLine($"{name2} {age2}"); // Bob 10 } }
メソッドの戻り値にも使えますので、複数の値を返すときにわざわざ新しい型を作る必要がなくなります。
using System; class Program { // a を b で割ったときの商と余りを返す static (int Quotient, int Remainder) DivMod(int a, int b) { return (a / b, a % b); } static void Main() { (int q, int r) = DivMod(10, 3); Console.WriteLine($"{q} {r}"); // 3 1 var x = DivMod(11, 3); Console.WriteLine($"{x.Quotient} {x.Remainder}"); // 3 2 var (q2, r2) = DivMod(12, 3); Console.WriteLine($"{q2} {r2}"); // 4 0 } }
参考
算術シフト、論理シフト
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