Index型とRange型で快適に配列を扱う

# はじめに
こちらの記事は[Unity Advent Calendar 2022](https://qiita.com/advent-calendar/2022/unity) 22日目の記事です。

現在Unityの最新版LTS(2021.3.16)で使えるC#バージョンは C#9で、さまざまな新しい言語機能を使うことができます。(2022年12月21日現在)
この記事ではC#8で登場した `Index/Range` について解説します。

この機能自体はC#8からの機能ですが、C#8が使える`Unity2020.2 ~ 2021.1` では**使うことができません**。
使えるのは `2021.2` からなのでご注意を

# Range

Range は端的に言えば 配列を`スライス`することができる機能です。
配列の一部分を取得するのにとても便利です。

```csharp
var array = new [] { 1, 2, 3, 4, 5 };

var array2 = array[1..3];            // [2, 3]
var array3 = array[0..3];            // [1, 2, 3]
var array4 = array[..3];             // [1, 2, 3]
var array5 = array[..array.Length];  // [1, 2, 3, 4, 5]
var array6 = array[..];              // [1, 2, 3, 4, 5]
```

- `[i..j]` は 配列の `i番目からj番目` の範囲を取得 (0始まり)
- `i` を省略すると `0` になる
- `j` を省略すると `array.Length` になる
- `i == j` だと空配列になる
- 配列外参照 や `i > j` の場合は例外がスローされる

# Index

Index はその名の通り配列のインデックスを意味するものです。
**後ろからn番目** を指定することができる便利機能がメインです。Rangeと組み合わせることもできます。

```csharp
var array = new [] { 1, 2, 3, 4, 5 };

var third = array[2];              // 3(普通のやつ)
var last = array[^1];              // 5
var first = array[^array.Length];  // 1
var array2 = array[1..^1];         // [2, 3, 4]
var error = array[^0];             // 必ずエラー
var range = array[2..^0];          // [3, 4, 5]
var range2 = array[^2..];          // [4, 5]
```

- `^j` は `array.Length - j` を返す
- Rangeと組み合わせて使うこともできる
- int型からの暗黙的な型変換がある
- Index単体の `^0` は必ず配列外参照になる
- Rangeと組み合わせるときの `^0` は一番後ろを指す

# もうちょっと詳しく

簡単な説明は以上です。シンプルでとても便利な機能だということがわかっていただけましたでしょうか。
ここからはもう少し詳細な話をします。

先ほどまでは Index/Range には スライスの機能がある！とか解説しましたが、あれは**嘘です**。

`^i` や `i..j` といったものはコンパイラによって`Index型` `Range型`にそれぞれ展開されます。

```csharp
// Index型のインスタンスが生成される
Index lastIndex = ^1;
Index lastIndex2 = new Index(1, true); // trueは「後ろから」を意味する

// Range型のインスタンスが生成される
Range range = 1..^2;
Range range2 = new Range(1,^2);
Range range3 = new Range(new Index(1, false), new Index(2, true));
Range all = ..;
Range all2 = Range.All;
```

こいつらは、インデックスや範囲を表すだけのただの構造体です。
スライスなどは Index/Range を使う側(配列とかのコレクション)がインデクサーや、ヘルパー的なメソッドを定義しなければいけません。
配列ではどうなっているのか、デコンパイルして結果を見てみましょう。

### Indexのデコンパイル
変数を経由せず直接 Index を入れたときはコンパイラの黒魔術により `array.Length - i` と解釈されています。パフォーマンスも良さそう。

```csharp
// Index型
int last = array[^1];

Index index = ^1;
int last2 = array[index];

// ↓デコンパイル結果↓ (一部改変)
int last = array[array.Length - 1];

Index index = new Index(1, true);
int last2 = array[index.GetOffset(array.Length)];
```

### Rangeのデコンパイル
Rangeを配列に渡すと `RuntimeHelpers.GetSubArray<T>`メソッド が呼ばれるようになっています。
ちなみにこの内部では `配列 → Span<T> → 配列` とか `配列 → 配列 → Span<T> → 配列` といった変換をしてるためコピーが発生します

```csharp
// Range型
int[] array2 = array[1..^1];

// ↓デコンパイル結果↓ (一部改変)
int[] array2 = RuntimeHelpers.GetSubArray<int>(array, new Range(Index.op_Implicit(1), new Index(1, true)));
```

現状、`List<T>` では Rangeのインデクサーが定義されていないので使うことができません。

```csharp
List<int> list = new();
var last = list[^1]; // Indexには対応してるからOK

_ = list[1..^3]; // コンパイルエラー。Rangeに対応してない
_ = list.GetRange(1, ^3);  // これもコンパイルエラー。intへの変換は行われない
```

`List<T>`のような言語機能の型はコンパイラによって Index から int への変換が行われているため使うことができます。(実装を見ようとすると`this[int]`に飛ばされた)

# Rangeインデクサを定義してみる

ということで例としてRangeが使えるように拡張したオレオレ`List<T>`を作ってみましょう

```csharp
public class MyList<T> : List<T>
{
    public MyList<T> this[Range range] => GetRange(range);

    public MyList<T> GetRange(Range range)
    {
        MyList<T> list = new();
        var (start, length) = range.GetOffsetAndLength(Count);

        for(var i = start; i < length + start; i++)
        {
            list.Add(base[i]);
        }
        return list;
    }
}
```

めちゃめちゃシンプルです。
`range.GetOffsetAndLength(Count)` は Indexの `fromEnd`フラグ を考慮した開始位置と長さを返してくれます。

### デフォルトでRangeに対応してる型
- `Array`
- `ArraySegment<T>`
- `string`
- `Span<T>`
- `ReadOnlySpan<T>`
- `Memory<T>`
- `ReadOnlyMemory<T>`

(他にもまだありそう...?)

# パフォーマンス比較

ここからは Index/Range を使ったパフォーマンスの比較をしていきます。計測はBenchmarkDotNetを使います


## Span[Range] と Array[Range]
`Span<T>`のRangeスライスは特別な最適化が施されていて高速に動くようなので確認してみます。

```Csharp: ベンチマーク
int count = 10000;

[Benchmark]
public void Array()
{
    for(var i = 0; i < count; i++)
    {
        _ = array[i..];
    }
}

[Benchmark]
public void Span()
{
    var span = memory.Span;
    for(var i = 0; i < count; i++)
    {
        _ = span[i..];
    }
}
```
[(計測コードの全文はこちら)](https://github.com/euglenach/IndexRangeBenchmark/blob/main/IndexRangeBenchmark/IndexRangeBenchmark/IndexRangeBenchmark/RangeAccess.cs)

配列とSpanで 各10000回アクセスした結果が以下の通りです。

| Method |          Mean |       Error |      StdDev |       Gen0 |   Allocated |
|------- |--------------:|------------:|------------:|-----------:|------------:|
|  Array | 17,952.276 us | 155.4486 us | 121.3640 us | 30468.7500 | 400280016 B |
|   Span |      4.066 us |   0.0707 us |   0.0661 us |          - |           - |

Rangeでアクセスすると `Span<T>.Slice`メソッドが呼ばれるようになっています。
配列と比べるとコピーが発生しないのでめちゃめちゃハイパフォーマンスでゼロアロケーションです。

<details><summary>デコンパイル結果</summary><div>

```csharp
// 配列のアクセス部分 のデコンパイル結果
RuntimeHelpers.GetSubArray<long>(this.array, Range.StartAt(Index.op_Implicit(index)));

// Spanのアクセス部分 のデコンパイル結果
System.Span<long> span2 = span1;
int length1 = span2.Length;
int start = index;
int num = start;
int length2 = length1 - num;
span2.Slice(start, length2);
```

</div></details>

## Stringのスライス

string も rangeのスライスに対応しているので計測してみました。
stringを`.AsSpan`すると、返り値は `ReadOnlySpan<char>` になり、そのままでは string として使えないので `Span → ReadOnlySpan<char> → String` と変換したものも併せて計測します。

```csharp: ベンチマーク
int count = 10000;

[Benchmark]
public void String(){
    for(var i = 0; i < count; i++){
        _ = str[range];
    }
}
[Benchmark]
public void Span(){
    var span = str.AsSpan();

    for(var i = 0; i < count; i++){
        _ = span[range];
    }
}
[Benchmark]
public void SpanToString(){
    var span = str.AsSpan();

    for(var i = 0; i < count; i++){
        _ = span[range].ToString();
    }
}
```


[(計測コードの全文はこちら)](https://github.com/euglenach/IndexRangeBenchmark/blob/main/IndexRangeBenchmark/IndexRangeBenchmark/IndexRangeBenchmark/StringSplit.cs)

同じく10000回ずつ回しています。

|       Method |      Mean |     Error |    StdDev |    Gen0 | Allocated |
|------------- |----------:|----------:|----------:|--------:|----------:|
|       String | 44.998 us | 0.4304 us | 0.4026 us | 30.5786 |  400000 B |
|         Span |  4.881 us | 0.0247 us | 0.0219 us |       - |         - |
| SpanToString | 47.518 us | 0.6632 us | 0.6204 us | 30.5786 |  400000 B |

やはり Span のスライスはとても高速です。

stringは`.Substring` が呼ばれていて`ReadOnlySpan<char>.ToString()`とほぼ同じ結果になりました。

<details><summary>stringスライスのデコンパイル結果</summary><div>

```C#:
// stringのスライス部分 のデコンパイル結果
string str = this.str;
int length1 = str.Length;
Range range = this.range;
int offset = range.Start.GetOffset(length1);
int length2 = range.End.GetOffset(length1) - offset;
str.Substring(offset, length2);

// Spanのスライス部分 のデコンパイル結果
ReadOnlySpan<char> readOnlySpan2 = readOnlySpan1;
int length1 = readOnlySpan2.Length;
Range range = this.range;
Index index2 = range.Start;
int offset = index2.GetOffset(length1);
index2 = range.End;
int length2 = index2.GetOffset(length1) - offset;
readOnlySpan2.Slice(offset, length2);

// Span→スライス→String部分 のデコンパイル結果
ReadOnlySpan<char> readOnlySpan2 = readOnlySpan1;
int length1 = readOnlySpan2.Length;
Range range = this.range;
Index index2 = range.Start;
int offset = index2.GetOffset(length1);
index2 = range.End;
int length2 = index2.GetOffset(length1) - offset;
readOnlySpan2.Slice(offset, length2).ToString();
```

</div></details>

# まとめ

- Range は 範囲を表す構造体
    - `[i..j]`でスライスできる
    - 末尾は `array.Length`
- Index は インデックスを表す構造体
    - `^j` で後ろからj番目を指定できる
    - 末尾は `^1`
- RangeとIndexを組み合わせることもできる
    - `[i..^j] `で iから末尾j番目の範囲を取れる
    - 末尾は `^0`

# 参考
https://ufcpp.net/study/csharp/data/dataranges/#range

https://learn.microsoft.com/ja-jp/dotnet/csharp/language-reference/proposals/csharp-8.0/ranges