Programming in D - スライスとその他の配列機能

スライスとその他の配列機能

配列の章では、要素が配列としてグループ化される仕組みについて説明した。その章は意図的に簡潔にまとめ、配列のほとんどの機能はこの章で説明する。

先に進む前に、意味が近いいくつかの用語の簡単な定義をいくつか紹介する。

配列: 要素が横一列に並べられ、インデックスでアクセスされる要素の集合の一般的な概念。
固定長配列 (静的配列): 要素の数が固定されている配列。このタイプの配列は、その要素を所有している。
動的配列: 要素を追加したり削除したりできる配列。このタイプの配列は、D実行環境によって所有されている要素へのアクセスを提供する。
スライス: 動的配列の別名

sliceと書く場合は、特にスライスを指す。配列と書く場合は、スライスまたは固定長配列のどちらかを指し、区別しない。

スライス

スライスは動的配列と同じ機能である。配列のように使用されるため動的配列と呼ばれ、他の配列の一部へのアクセスを提供するためスライスと呼ばれる。これらの部分は、独立した配列として使用できる。

スライスは、範囲の開始と終了を指定するインデックスに対応する数値範囲構文で定義される:

  開始インデックス .. 最後のインデックスの次のもの

数値範囲構文では、開始インデックスは範囲の一部だが、終了インデックスは範囲外である:

/* ... */ = monthDays[0 .. 3];  // 0、1、2は含まれるが; 3は含まれない

注釈:数値範囲はPhobosの範囲とは異なる。Phobosの範囲は、構造体およびクラスのインターフェースに関するものだ。これらの機能については、後の章で説明する。

例として、monthDays配列をスライスして、その一部を4つの小さな配列として使用できるようにする。

int[12] monthDays =
    [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ];

int[] firstQuarter  = monthDays[0 .. 3];
int[] secondQuarter = monthDays[3 .. 6];
int[] thirdQuarter  = monthDays[6 .. 9];
int[] fourthQuarter = monthDays[9 .. 12];

上記のコードの4つの変数はスライスであり、既存の配列の4つの部分にアクセスすることができる。ここで強調すべき重要な点は、これらのスライスには独自の要素がないことだ。これらは、実際の配列の要素へのアクセスを提供するだけである。スライスの要素を変更すると、実際の配列の要素も変更される。これを確認するために、各スライスの最初の要素を変更してから、実際の配列を出力しよう。

firstQuarter[0]  = 1;
secondQuarter[0] = 2;
thirdQuarter[0]  = 3;
fourthQuarter[0] = 4;

writeln(monthDays);

出力:

[1, 28, 31, 2, 31, 30, 3, 31, 30, 4, 30, 31]

各スライスは最初の要素を変更し、実際の配列の対応する要素も変更される。

これまで、有効な配列インデックスは0から配列の長さより1少ない値までであることを説明してきた。例えば、3要素の配列の有効なインデックスは0、1、2 だ。同様に、スライス構文の終了インデックスは、スライスがアクセスする最後の要素の1つ先を指定する。そのため、配列の最後の要素をスライスに含める必要がある場合は、配列の長さを終了インデックスとして指定する必要がある。例えば、3要素の配列のすべての要素のスライスは、array[0..3]となる。

明らかな制限として、開始インデックスは終了インデックスより大きいことはできない:

int[3] array = [ 0, 1, 2 ];
int[] slice = array[2 .. 1];  // ← 実行時エラー

開始インデックスと終了インデックスが等しいことは合法である。その場合、スライスは空になる。indexが有効であると仮定すると:

int[] slice = anArray[index .. index];
writeln("The length of the slice: ", slice.length);

出力:

スライスの長さ	0

`$`を使用する場合、代わりに`array.length`

インデックス付け時に、$は配列の長さの省略形である:

writeln(array[array.length - 1]);  // 最後の要素
writeln(array[$ - 1]);             // 同じもの

`.dup`を使用してコピーする場合:

"複製"の略である.dupプロパティは、既存の配列の要素のコピーから新しい配列を作成する。

double[] array = [ 1.25, 3.75 ];
double[] theCopy = array.dup;

例として、閏年の各月の日数を格納する配列を定義しよう。1つの方法は、閏年以外の年の配列のコピーを取り、2月に相当する要素を加算することだ。

import std.stdio;

void main() {
    int[12] monthDays =
        [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ];

    int[] leapYear = monthDays.dup;

    ++leapYear[1];   // 2月の日数を増やす

    writeln("Non-leap year: ", monthDays);
    writeln("Leap year    : ", leapYear);
}

出力:

閏年でない年	[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
閏年	[31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

代入

これまで、代入演算子は変数の値を変更することを見てきた。固定長配列でも同じだ。

int[3] a = [ 1, 1, 1 ];
int[3] b = [ 2, 2, 2 ];

a = b;        // 'a'の要素が2つになる
writeln(a);

出力:

[2, 2, 2]

スライスに対する代入操作は、完全に異なる意味を持つ:スライスが新しい要素へのアクセスを開始するようになる:

int[] odds = [ 1, 3, 5, 7, 9, 11 ];
int[] evens = [ 2, 4, 6, 8, 10 ];

int[] slice;   // まだどの要素にもアクセスできない

slice = odds[2 .. $ - 2];
writeln(slice);

slice = evens[1 .. $ - 1];
writeln(slice);

上記では、sliceは定義された時点ではどの要素にもアクセスできない。その後、oddsのいくつかの要素にアクセスするために使用され、さらにevensのいくつかの要素にアクセスするために使用される:

[5, 7]
[4, 6, 8]

スライスを長くすると共有が終了する可能性がある

固定長配列の長さは変更できないため、共有の終了という概念はスライスにのみ適用される。

複数のスライスによって同じ要素にアクセスすることは可能だ。例えば、以下の8つの要素のうち最初の2つは、3つのスライスを通じてアクセスされている。

import std.stdio;

void main() {
    int[] slice = [ 1, 3, 5, 7, 9, 11, 13, 15 ];
    int[] half = slice[0 .. $ / 2];
    int[] quarter = slice[0 .. $ / 4];

    quarter[1] = 0;     // 1つのスライスで変更する

    writeln(quarter);
    writeln(half);
    writeln(slice);
}

quarterの2番目の要素の変更は、すべてのスライスを通じて反映される:

[1, 0]
[1, 0, 5, 7]
[1, 0, 5, 7, 9, 11, 13, 15]

この観点から、スライスは要素への共有アクセスを提供する。この共有は、スライスの1つに新しい要素を追加した場合に何が起こるかという問題を引き起こす。複数のスライスが同じ要素へのアクセスを提供するため、他の要素を上書きせずにスライスに要素を追加するスペースがない可能性がある。

Dは要素の上書きを禁止し、新しい要素を追加するスペースがない場合、共有関係を終了することでこの問題を解決する: 拡張できないスライスは共有から離脱する。この場合、そのスライスの既存のすべての要素は自動的に新しい場所にコピーされ、スライスはこれらの新しい要素へのアクセスを開始する。

この動作を確認するため、quarterに要素を追加してから、その2番目の要素を修正しよう:

quarter ~= 42;    // このスライスが共有から外れるのは、
                  // 新しい要素を格納するスペースがないためである

quarter[1] = 0;   // その理由により、この変更は
                  // 他のスライスには影響しない

プログラムの出力は、quarterスライスへの変更が他のスライスに影響を与えないことを示している:

[1, 0, 42]
[1, 3, 5, 7]
[1, 3, 5, 7, 9, 11, 13, 15]

スライスの長さを明示的に増やすと、共有も解除される:

++quarter.length;       // 共有を終了する

または

quarter.length += 5;    // 共有を終了する

一方、スライスの長さを短くしても共有には影響しない。スライスの長さを短くするとは、単にスライスがアクセス可能な要素の数を減らすことを意味する:

int[] a = [ 1, 11, 111 ];
int[] d = a;

d = d[1 .. $];  // beginningから短縮
d[0] = 42;      // スライスを通じて要素を変更

writeln(a);     // 他のスライスを表示

出力からわかるように、d経由の修正はa経由でも反映され、共有は依然として有効だ:

[1, 42, 111]

異なる方法で長さを短縮しても、共有は終了しない:

d = d[0 .. $ - 1];         // 末尾を短縮
--d.length;                // 同じこと
d.length = d.length - 1;   // 同じこと

要素の共有は依然として有効だ。

`capacity`を使用して共有が終了するかどうかを判断する

要素がスライスの1つに追加されても、スライスが要素の共有を継続する場合がある。これは、要素が最長のスライスに追加され、その末尾に空きがある場合に発生する:

import std.stdio;

void main() {
    int[] slice = [ 1, 3, 5, 7, 9, 11, 13, 15 ];
    int[] half = slice[0 .. $ / 2];
    int[] quarter = slice[0 .. $ / 4];

    slice ~= 42;      // 最長のスライスに追加...
    slice[1] = 0;     // ... そして要素を変更する

    writeln(quarter);
    writeln(half);
    writeln(slice);
}

出力からわかるように、追加された要素がスライスの長さを増やしても、共有は終了せず、変更はすべてのスライスに反映される:

[1, 0]
[1, 0, 5, 7]
[1, 0, 5, 7, 9, 11, 13, 15, 42]

スライスのcapacityプロパティは、特定のスライスに要素が追加された場合に共有を終了するかどうかを決定する。(capacityは実際には関数だが、この説明ではその区別は重要ではない。)

capacityの値は、次の意味を持つ。

値が0の場合、これは最長の元のスライスではないことを意味する。この場合、新しい要素を追加すると、スライスの要素は確実に再配置され、共有は終了する。
値が0以外の場合、これは最長の元のスライスであることを意味する。この場合、capacityは、このスライスがコピーされることなく保持できる要素の総数を表す。追加できる新しい要素の数は、スライスの実際の長さを容量値から差し引いて計算できる。スライスの長さがその容量と等しい場合、要素が1つ追加されると、スライスは新しい場所にコピーされる。

したがって、共有が終了するかどうかを判断する必要があるプログラムでは、以下の論理に類似した処理を使用すべきだ。

if (slice.capacity == 0) {
    /* このスライスに要素が1つ追加されると、
     * その要素は再配置される。 */

    // ...

} else {
    /* このスライスは、再配置が必要になる前に
     * 新しい要素を追加できる余地があるかもしれない。
     * その数を計算しよう: */
    auto howManyNewElements = slice.capacity - slice.length;

    // ...
}

興味深い特殊ケースは、すべての要素が複数のスライスに分割されている場合だ。この場合、すべてのスライスは容量を次のように報告する:

import std.stdio;

void main() {
    // すべての要素に3つのスライス
    int[] s0 = [ 1, 2, 3, 4 ];
    int[] s1 = s0;
    int[] s2 = s0;

    writeln(s0.capacity);
    writeln(s1.capacity);
    writeln(s2.capacity);
}

すべてが容量あり:

7
7
7

しかし、いずれかのスライスに要素が追加されると、他のスライスの容量は0に減少する:

s1 ~= 42;    // ← s1が最長になる

writeln(s0.capacity);
writeln(s1.capacity);
writeln(s2.capacity);

追加された要素を含むスライスが最も長くなったため、容量があるのはそのスライスだけになる:

0
7        ← 現在、S1のみが容量を有している
0

要素のための容量の確保

要素のコピーや容量を増やすための新しいメモリの割り当てには、一定のコストがかかる。そのため、要素の追加は高コストな操作になる可能性がある。追加する要素の数が事前に分かっている場合、要素のための容量を事前に確保することができる:

import std.stdio;

void main() {
    int[] slice;

    slice.reserve(20);
    writeln(slice.capacity);

    foreach (element; 0 .. 17) {
        slice ~= element;  // ← これらの要素は移動されない
    }
}

31        ← 20個以上の要素を収容可能

sliceの要素は、要素数が31を超えた後にのみ移動される。

すべての要素に対する操作

この機能は、固定長配列とスライスの両方に適用される。

配列名の後に書かれた[]は、すべての要素を意味する。この機能は、配列のすべての要素に特定の操作を適用する必要がある場合にプログラムを簡素化する。

import std.stdio;

void main() {
    double[3] a = [ 10, 20, 30 ];
    double[3] b = [  2,  3,  4 ];

    double[3] result = a[] + b[];

    writeln(result);
}

出力:

[12, 23, 34]

そのプログラムの加算操作は、両方の配列の対応する要素に対して順に適用される。まず最初の要素が加算され、次に2番目の要素が加算される、というように続く。自然な要件として、2つの配列の長さは等しい必要がある。

演算子は、算術演算子+、-、*、/、%、^^、二項演算子^、&、|、および配列の前に入力される単項演算子-、~のいずれかである。これらの演算子のいくつかは、後の章で説明する。

これらの演算子の代入バージョンも使用できる:=、+=、-=、*=、/=、%=、^^=、^=、&=、および|=。

この機能は、2つの配列だけでなく、配列と互換性のある式でも使用できる。例えば、次の操作は、配列のすべての要素を4で割る。

double[3] a = [ 10, 20, 30 ];
a[] /= 4;

writeln(a);

出力:

[2.5, 5, 7.5]

すべての要素に特定の値を割り当てるには、次のようにする。

a[] = 42;
writeln(a);

出力:

[42, 42, 42]

この機能は、スライスと併用する場合、細心の注意が必要である。要素の値には明らかな違いはないが、次の2つの式はまったく異なる意味になる。

slice2 = slice1;      // ← slice2は、
                      //   slice1がアクセスできる
                      //   同じ要素へのアクセスを提供し始める

slice3[] = slice1;    // ← slice3の要素の値が
                      //   変更される

slice2を代入すると、slice1と同じ要素が共有される。一方、slice3[]はslice3のすべての要素を意味するため、その要素の値はslice1の要素の値と同じになる。[]文字の有無の影響は無視できない。

この違いの例を次のプログラムで見てみよう。

import std.stdio;

void main() {
    double[] slice1 = [ 1, 1, 1 ];
    double[] slice2 = [ 2, 2, 2 ];
    double[] slice3 = [ 3, 3, 3 ];

    slice2 = slice1;      // ← slice2は、
                          //  slice1がアクセスできる
                          //  同じ要素へのアクセスを提供し始める

    slice3[] = slice1;    // ← slice3の要素の値が
                          //  変更される

    writeln("slice1 before: ", slice1);
    writeln("slice2 before: ", slice2);
    writeln("slice3 before: ", slice3);

    slice2[0] = 42;       // ← slice1と共有する要素の値が
                          //  変更される

    slice3[0] = 43;       // ← それだけがアクセスできる要素の値が
                          //  変更される
                          //

    writeln("slice1 after : ", slice1);
    writeln("slice2 after : ", slice2);
    writeln("slice3 after : ", slice3);
}

slice2による変更は、slice1にも影響する:

slice1の前	[1, 1, 1]
slice2の前	[1, 1, 1]
slice3の前	[1, 1, 1]
slice1の後	[42, 1, 1]
slice2の後	[42, 1, 1]
slice3の後	[43, 1, 1]

ここでの危険は、共有要素の値が変更されるまで、潜在的なバグに気付かない可能性があることである。

多次元配列

これまで、intやdoubleなどの基本的な型のみを持つ配列を使用してきた。実際には、要素の型は他の配列を含む、他の任意の型にすることができる。これにより、プログラマは、配列の配列などの複雑なコンテナを定義することができる。配列の配列は、多次元配列と呼ばれる。

これまで定義したすべての配列の要素は、ソースコード内で左から右に記述されてきた。2次元配列の概念を理解するために、今回は上から下に向かって配列を定義しよう:

int[] array = [
                10,
                20,
                30,
                40
              ];

覚えておいてほしいのは、ソースコード内のほとんどのスペースは読みやすさを向上させるためのもので、コードの意味は変わらないことだ。上記の配列は1行で定義しても同じ意味になる。

次に、その配列のすべての要素を別の配列で置き換えてみよう:

  /* ... */ array = [
                      [ 10, 11, 12 ],
                      [ 20, 21, 22 ],
                      [ 30, 31, 32 ],
                      [ 40, 41, 42 ]
                    ];

int型の要素をint[]型の要素に置き換えた。コードを配列の定義構文に適合させるには、要素の型をintではなくint[]と指定する必要がある。

int[][] array = [
                  [ 10, 11, 12 ],
                  [ 20, 21, 22 ],
                  [ 30, 31, 32 ],
                  [ 40, 41, 42 ]
                ];

このような配列は、行と列を持つように見えるため、2次元配列と呼ばれる。

2次元配列は、各要素がそれ自体配列であり、配列操作で使用されることを覚えておけば、他の配列と同じように使用できる:

array ~= [ 50, 51 ]; // 新しい要素(つまりスライス)を追加する
array[0] ~= 13;      // 最初の要素に追加する

配列の新しい状態:

[[10, 11, 12, 13], [20, 21, 22], [30, 31, 32], [40, 41, 42], [50, 51]]

配列と要素は固定長にすることもできる。以下の例は、すべての次元が固定長の3次元配列だ:

int[2][3][4] array;  // 2列、3行、4ページ

上記の定義は、3行2列の整数の4ページと見なすことができる。例えば、このような配列は、各階が2x3=6部屋で構成される4階建ての建物をアドベンチャーゲームで表現するために使用することができる。

例えば、2階目の1番目の部屋のアイテムの数を次のように増やすことができる。

// 2階のインデックスは1で、その階の最初の部屋は
// [0][0]でアクセスする
++itemCounts[1][0][0];

上記の構文に加えて、new式を使用して、スライスのスライスを作成することもできる。次の例では、2次元のみを使用している。

import std.stdio;

void main() {
    int[][] s = new int[][](2, 3);
    writeln(s);
}

上記のnew式は、それぞれ3つの要素を含む2つのスライスを作成し、それらのスライスおよび要素へのアクセスを提供するスライスを返す。出力:

[[0, 0, 0], [0, 0, 0]]

要約

固定長配列は要素を所有する。スライスは、それらに排他的に属さない要素へのアクセスを提供する。
[]演算子内では、$は array_name.lengthと等価である。
.dupは、既存の配列の要素のコピーからなる新しい配列を作成する。
固定長配列では、代入操作によって要素の値が変更されるが、スライスの場合、スライスが他の要素へのアクセスを開始するようになる。
スライスが長くなる場合、要素の共有が停止し、新しくコピーされた要素へのアクセスが開始されることがある。capacityがこの動作を決定する。
array[]は配列のすべての要素を意味し、適用される操作は各要素に個別に適用される。
配列の配列は多次元配列と呼ばれる。

演習

doubleの配列の要素を繰り返し、10より大きいものを半分にする。例えば、次の配列がある。

double[] array = [ 1, 20, 2, 30, 7, 11 ];

次のように変更しよう:

[1, 10, 2, 15, 7, 5.5]

この問題には多くの解決策があるが、スライスの機能のみを使用して解決してみてよう。まず、すべての要素にアクセスできるスライスを作成する。その後、スライスの先頭から短縮し、常に最初の要素を使用するようにする。

次の式は、スライスの先頭から短縮している。

slice = slice[1 .. $];

... 解答