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> インターフェースを実装しているなら、インデックスによるアクセスで最後の要素を取得しています。
まとめ
- IList<T> インターフェース を実装しているなら、Enumerable.Last は O(1) で速い
タプルを == 演算子で比較、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
2 つの Dictionary をひとつにまとめる
両方の Dictionary に同じキーが含まれる場合は、Sum() で足し合わせます。
using System; using System.Collections.Generic; using System.Linq; class Program { static Dictionary<int, int> Add(Dictionary<int, int> a, Dictionary<int, int> b) { return a.Concat(b).GroupBy(e => e.Key, e => e.Value).ToDictionary(e => e.Key, e => e.Sum()); } static void Main() { var a = new Dictionary<int, int> { { 1, 2 }, { 2, 3 }, }; var b = new Dictionary<int, int> { { 0, 1 }, { 1, 1 }, { 2, 2 }, { 5, 0 }, }; var c = Add(a, b); foreach (var k in c.Keys.OrderBy(e => e)) { Console.WriteLine("key:{0} val:{1}", k, c[k]); } } }
実行結果です。
key:0 val:1 key:1 val:3 key:2 val:5 key:5 val:0
0,1,0,1,0,1... を繰り返すシーケンス
using System; using System.Collections.Generic; using System.Linq; class Program { static IEnumerable<int> ZeroOne() { int n = 0; while (true) { yield return n; n ^= 1; } } static void Main() { Console.WriteLine(string.Join(",", ZeroOne().Take(10))); // => 0,1,0,1,0,1,0,1,0,1 } }
実行結果です。
0,1,0,1,0,1,0,1,0,1
Pairs 関数
Python の
>>> [(i, j) for i in range(3) for j in range(3)] [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
のような各ペアを求める Pairs 関数を作成してみました。
using System; using System.Collections.Generic; using System.Linq; public static class Iter { static IEnumerable<T[]> Product_1<T>(int p, T[] buf, List<List<T>> pools) { if (p == buf.Length) { yield return buf; } else { foreach (var e in pools[p]) { buf[p] = e; foreach (var ret in Product_1(p+1, buf, pools)) { yield return ret; } } } } public static IEnumerable<T[]> Product<T>(IEnumerable<T> xs, int repeat = 1) { var pools = new List<List<T>>(Enumerable.Repeat(xs.ToList(), repeat)); return Product_1(0, new T[pools.Count], pools); } public static IEnumerable<T[]> Product<T>(IEnumerable<T> xs, IEnumerable<T> ys, int repeat = 1) { var ls = new List<List<T>> { xs.ToList(), ys.ToList() }; var pools = new List<List<T>>(Enumerable.Repeat(ls, repeat).SelectMany(e => e)); return Product_1(0, new T[pools.Count], pools); } public static IEnumerable<U> Pairs<T, U>(IEnumerable<T> xs, IEnumerable<T> ys, Func<T, T, U> fn) { foreach (var e in Product(xs, ys)) { var cs = e.ToArray(); yield return fn(cs[0], cs[1]); } } } class Program { static void Main() { var xs = new[] { 0, 1, 2 }; var ys = Iter.Pairs(xs, xs, (a, b) => Tuple.Create(a, b)); Console.WriteLine(string.Join(" ", ys)); // => (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2) } }
Product を経由せずに、foreach で 2 重ループを回すほうが簡単ですが、Product の応用を考えていて Pairs を作れることが分かったので作ってみました。
