やっさんの雑記

プログラミングでやってみたこととか

C#の2次元配列とLINQ

今日はC#の2次元配列とLINQの相性がものすごく悪いなあという話です。

途中が無駄に長いので、途中がどうでもよくて対処法だけ知りたいという方はどうしてもLINQのメソッドを使いたいの節まで飛んでください。

きっかけ

1次元配列だと

var a = new int[] { 2, 7, 1, 8, 2, 8 };
var b = new int[] { 3, 1, 4, 1, 5, 9 };
var c = a.Zip(b, (n, m) => n + m).ToArray();

みたいにSystem.Linq.Enumerable.Zip()で各要素ごとに同じ操作をすることができます。

それと同じように2次元配列でも

var a = new int[,] { { 2, 7 }, { 1, 8 }, { 2, 8 } };
var b = new int[,] { { 3, 1 }, { 4, 1 }, { 5, 9 } };
var c = a.Zip(b, (n, m) => n + m).ToArray();

のように書いて要素ごとに操作をしたいなあと思ってコードを書きましたがa.Zまで書いたところでVisualStudioのIntelliSenseに「そんな関数ねぇよw」と言われて、どうやったらこういうのを簡単に書けるんだろうと思って考えました。

「四角形配列」と「ジャグ配列」

C#で多次元配列を使うときには、大きく分けて次の2つの方法があります。

// 四角形配列の例
var ar1 = new int[,] { { 1, 2 },
                       { 3, 4 },
                       { 5, 6 } };

// ジャグ配列の例
var ar2 = new int[][] { new int[] { 1, 2 },
                        new int[] { 3, 4 },
                        new int[] { 5, 6 } };

それぞれ欠点利点がありますが、とりあえず代表的なもの簡単にまとめてみます。

  四角形配列 ジャグ配列
メモリ使用量 少ない 多い
初期化 簡単 面倒
行ごとのサイズ 必ず一定 変えられる
foreachアクセス コード例参照 コード例参照

foreachによるアクセスですが、四角形配列では例えば

using System;

class Program
{
    public static void Main()
    {
        var ar_rect = new int[,] { { 1, 2 },
                                   { 3, 4 },
                                   { 5, 6 } };
        foreach (var n in ar_rect) {
            Console.Write("{0} ", n);
        }
    }
}

とすると、出力は

1 2 3 4 5 6 

となり、1次元配列のようにならされて順番にアクセスすることがわかります。

一方ジャグ配列で同じことをしようとすると、

using System;

class Program
{
    public static void Main()
    {
        var ar_jag = new int[][] { new int[] { 1, 2 },
                                   new int[] { 3, 4 },
                                   new int[] { 5, 6 } };
        foreach (var ar in ar_jag) {
            foreach (var n in ar) {
                Console.Write("{0} ", n);
            }
        }
    }
}

というふうにループを2重に書かないといけませんね。四角形配列は単なるintの配列である一方、ジャグ配列はintの配列の配列だからです。

さて本題

四角形配列とジャグ配列にどんな差があるのか簡単にわかったところで、本題です。

四角形配列も単なる1次元配列もどちらもSystem.Arrayクラスのインスタンスのはずなのになぜ前者はZipが使えなくて後者は使えるのでしょうか。

使えないメソッドはZipだけではありません。SumやAverageなど、LINQの関数全般が使えません、というよりLINQのクエリ式自体使えません。

using System;

class Program
{
    public static void Main()
    {
        var ar = new int[,] { { 1, 2 }, { 3, 4 }, { 5, 6 } };

        var sum  = ar.Sum();                               // コンパイルエラー
        var odds = from n in ar where n % 2 == 0 select n; // コンパイルエラー
    }
}

ここでMSDNのヘルプを見ると、ZipやSumはSystem.Linq.Enumerableクラスに定義されている拡張メソッドであることがわかります。

例えばSumの例で見ると、たくさんのオーバーロードがありますが、基本となるのは

public static int Sum(this IEnumerable<int> source)

です。

要するに、Sum関数を使うには対象のオブジェクトがSystem.Collections.Generic.IEnumerable<>を実装したクラスのインスタンスである必要があります。

そこで四角形配列とジャグ配列がどんなクラスのインスタンスなのかを含め、いろいろ調べてみます。

using System;

class Program
{
    public static void Main()
    {
        var ar_rect = new int[,] { { 1, 2 }, { 3, 4 } };
        var ar_jag = new int[][] { new int[] { 1, 2 }, new int[] { 3, 4 } };

        var re_t = ar_rect.GetType();
        var ja_t = ar_jag.GetType();

        Console.WriteLine("ar_rect is Array: {0}", ar_rect is Array);
        Console.WriteLine("ar_jag  is Array: {0}", ar_jag is Array);
        Console.WriteLine();

        Console.WriteLine("ar_rect.GetType() = {0}", re_t);
        Console.WriteLine("ar_jag .GetType() = {0}", ja_t);
        Console.WriteLine();

        Console.WriteLine("ar_rect.GetType().BaseType = {0}", re_t.BaseType);
        Console.WriteLine("ar_jag .GetType().BaseType = {0}", ja_t.BaseType);
        Console.WriteLine();

        Console.WriteLine("ar_rect.GetType() == typeof(Array) ? {0}", re_t == typeof(Array));
        Console.WriteLine("ar_jag .GetType() == typeof(Array) ? {0}", ja_t == typeof(Array));
        Console.WriteLine();

        Console.WriteLine("type of ar_rect is a implementation of: ");
        foreach (var t in re_t.GetInterfaces()) {
            Console.WriteLine(t);
        }
        Console.WriteLine();
        Console.WriteLine("type of ar_jag  is a implementation of: ");
        foreach (var t in ja_t.GetInterfaces()) {
            Console.WriteLine(t);
        }
        Console.WriteLine();
    }
}

すると、こんな結果が得られるはずです。

ar_rect is Array: True
ar_jag  is Array: True

ar_rect.GetType() = System.Int32[,]
ar_jag .GetType() = System.Int32[][]

ar_rect.GetType().BaseType = System.Array
ar_jag .GetType().BaseType = System.Array

ar_rect.GetType() == typeof(Array) ? False
ar_jag .GetType() == typeof(Array) ? False

type of ar_rect is a implementation of:
System.ICloneable
System.Collections.IList
System.Collections.ICollection
System.Collections.IEnumerable
System.Collections.IStructuralComparable
System.Collections.IStructuralEquatable

type of ar_jag  is a implementation of:
System.ICloneable
System.Collections.IList
System.Collections.ICollection
System.Collections.IEnumerable
System.Collections.IStructuralComparable
System.Collections.IStructuralEquatable
System.Collections.Generic.IList`1[System.Int32[]]
System.Collections.Generic.ICollection`1[System.Int32[]]
System.Collections.Generic.IEnumerable`1[System.Int32[]]
System.Collections.Generic.IReadOnlyList`1[System.Int32[]]
System.Collections.Generic.IReadOnlyCollection`1[System.Int32[]]

ということで、ar_rectもar_jagもBaseTypeがSystem.Arrayになっているので、上ではar_rectもar_jagもArrayクラスのインスタンスと書きましたが、実際にはその派生クラスのインスタンスのようです。

ここで、再びMSDNでArrayクラスの定義を見てみると、

[SerializableAttribute]
[ComVisibleAttribute(true)]
public abstract class Array : ICloneable, 
	IList, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable

ということで、Arrayクラスは抽象クラスなのでインスタンス化できず、C#の配列の実体はArrayクラスの派生クラスのインスタンスです。これは僕の勘違いというか不勉強なだけですね。

LINQのメソッドを使うにはSystem.Collections.Generic.IEnumerable<>を実装している必要があるので、やっぱり2次元配列にはLINQのメソッドは(そのままでは)使えません。

なぜ使わせてくれないのか

CLIの2014/02/01現在の最新の仕様書ECMA-335)の§I.8.9.1を見ると、

(前略)


Additionally, a created vector with element type T, implements the interface System.Collections.Generic.IList<U>, where U := T. (§I.8.7)


(中略)


Array types form a hierarchy, with all array types inheriting from the type System.Array. This is an abstract class (see §I.8.9.6.2) that represents all arrays regardless of the type of their elements, their rank, or their upper and lower bounds. The VES creates one array type for each distinguishable array type. In general, array types are only distinguished by the type of their elements and their rank. However, the VES treats single dimensional, zero-based arrays (also known as vectors) specially. Vectors are also distinguished by the type of their elements, but a vector is distinct from a single-dimensional array of the same element type that has a non-zero lower bound. Zero-dimensional arrays are not supported.


(後略)

http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-335.pdf

とか書かれていて、簡単に訳しますと

(前略)


加えて、要素の型をTとして生成されたベクトルは U:=T として System.Collections.Generic.IList<U> インタフェースを実装します。


(中略)


配列型は階層構造をなし、すべての配列型は System.Array 型を継承します。これは配列要素の型、次元、上限下限を無視したすべての配列をあらわす抽象クラスです。VESは各区別可能な配列の型に対して1つの配列型を作ります。一般的に、配列の型はその要素の型と次元数によってのみ区別されます。しかしながら、VESは1次元で下限が0の配列(要するにベクトル)を特別扱いします。ベクトルもまたその要素の型によって区別されますが、要素が同じ型で下限が0でない1次元配列とは全く異なります。0次元の配列はサポートされません。


(後略)

ということで*1、次のことがわかります。

  • 配列については1次元配列でしかも添字が0から始まるもの(いわゆる普通の配列。配列が入れ子になったものとかもこれ)だけが特別扱い
  • 普通の配列だけがSystem.Collections.Generic.IList<>を実装している

普通の配列だけが特別扱いされるというのは僕としては非常に納得しています。というのも、全種類の配列を同一視して命令セットを作る場合、多次元だったりインデックスが0から始まらなかったりして、実際のメモリ上のアドレスを計算するのにとても時間がかかってしまいそうで非効率的です。一方普通の配列の場合は、C言語とかを触った人なら当然わかると思いますが、実際のアドレスを計算するのに先頭アドレスに(要素データのバイト数)×(インデックスの値)を足すだけでいいので、アクセスがとても早くて効率的だからです*2

一方2つ目が今回の問題の本質ですが、結局よくわかりません。System.Collections.IListは実装しているんだから、System.Collections.Generic.IList<>も実装してくれたっていいじゃんとか思うわけです。

LINQのメソッドの中にはTakeWhile<>()とかもあって、これは多次元配列でどんな動作すりゃええねんという感じで、確かに実装されちゃ困るようなメソッドもあるわけですが、たぶんLINQ登場以前からSystem.Collections.Generic.IList<>を実装していないということは変わらないわけで…

どうしてもLINQのメソッドを使いたい

標準でサポートしてくれていなくても、やっぱり多次元配列の要素の中の最大値とかは簡単に計算したいし、クエリ式を書いて簡単に要素抽出とかしたいわけです。

じゃあどうすればいいかというと、いくつか方法が考えられるので、順に紹介してみたいと思います。

多次元配列を使わない

ちょっと乱暴ですが、(インスタンス生成がめんどくさいという話はおいといて)多次元配列は1次元配列の配列の配列の…の配列という形で記述できるので、すべてそれに移行してしまうという方法です*3

記法が全体的に複雑になってわかりにくくなるという欠点もありますが、非常に明快単純な解決法です。

キャストする

ちょっと使うだけならたぶんこれが一番簡単です。

System.Collections.IEnumerableにはCast<>拡張メソッドがあります。これはSystem.Collections.IEnumerableをSystem.Collections.Generic.IEnumerable<>に変換するものです。素晴らしいですね。さっそく使ってみましょう。

using System;
using System.Linq;

class Program
{
    public static void Main()
    {
        var data = new int[,] { { 2, 3, 5 },
                                { 7, 9, 8 },
                                { 6, 4, 1 } };
        var max  = data.Cast<int>().Max();
        Console.WriteLine("max = {0}", max);

        var even = from n in data.Cast<int>()
                   where n % 2 == 0
                   select n;
        foreach (vat n in even) {
            Console.WriteLine(n);
        }
    }
}

非常に簡単です。このメソッドがSystem.Linq.Enumerableに定義されているというのはつまり、LINQ使いたいときはこれ使えとMSが言ってるのだと思います。

自分で拡張メソッドを定義する

System.Linq.Enumerable.Cast<>を使うとLINQの操作ができるようになることがわかりましたが、これを使うと、得られる結果が1次元的なものになってしまうという弊害があります。Zipしたら配列の形が変わってしまったとかいうのは意味がわからないですよね。1次元配列に対しては得られる結果も1次元的なもので変わらないので、別に大丈夫なわけですが。

このように柔軟な操作を必要とする場合は、自分で適当なクラスに拡張メソッドを定義する必要があります。ただし、C#ではyield-returnを使うことでLINQ式の遅延実行を行っていますが、yield-returnを使う場合は原理的に多次元的に結果を返すことができないので、遅延実行を諦めざるを得ないという面があります。

まとめ

多次元配列はクソ。ジャグ配列使え。どうしても嫌ならCast<>でIEnumerable<>に変換して汚物を消毒。

長々と読んでいただきありがとうございました。

*1:文中で上限下限いってるのがわかりにくそうですが、そういえばC#ではArray.CreateInstanceメソッドを使えば0-indexedではない配列も作れたりするのでした。つまり、「その配列のインデックスとして指定できる値の上限下限」ということですね

*2:x86アセンブラとかだと要素データの大きさによっては1命令でできたりもします

*3:多次元配列はジャグ配列と比べて四角形状配列になることが文法的に保証されるという安心感がなくなるデメリットはありますね