forked from dlang/dlang.org
-
Notifications
You must be signed in to change notification settings - Fork 4
/
d-array-article.dd
254 lines (178 loc) · 26 KB
/
d-array-article.dd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
Ddoc
$(D_S $(TITLE),
$(P $(I by Steven Schveighoffer))
$(P D言語で最も嬉しい機能の一つが、スライスの実装です。D以外のプログラミング言語を使うといつでも、自分がDのスライス構文なしではいられなくなっていることに気づきます。スライスは簡潔で効率的なだけではなく、スライスを使っていると全てが思った通りに"ただ動作する"のです。
)
$(P この記事では、Dのスライスと配列の内部実装と背景について眺めていきます。読み終わった後には、Dのスライスの適切な使い方についての明確な理解と、それがただの配列とどう根本的に！違っているかが把握できることと思います。
)
$(H2 オーバーフローの問題)
$(P ほとんどの言語では、配列は中で自分のデータを管理する組み込みデータ型で、参照で持ち回る形で使われます。そのデータの塊全体が "配列" と呼ばれ、配列に関す連するすべての処理 (値の設定、動的配列へのデータの追記、長さの取得、等々) がその型に対して関連づけられています。
)
$(P しかしながら、C 言語の系譜に連なる D では、配列というのは単に連続領域に並んだデータの連なりです。C では、配列や配列の一部への参照は単なるポインタ（明示的な参照）と同じものでした。Cの配列は、要素を指すデータ型、つまりポインタ、のみを通して個別に扱われます。提供される唯一の操作は、ポインタからのオフセットで指定したデータの読み書きのみです。
)
$(P Cに慣れていない方のために、いくつかCでの配列操作の例を紹介します（これは D でもそのまま動きます）:
)
------
arr[0] = 4; /* 配列 'arr' の先頭要素を 4 にする */
x = arr[1]; /* 配列 'arr' の第二要素を x に取り出す */
------
$(P そのほかのすべて (長さ取得, 要素追加, 割り当て, 破棄) はライブラリ関数と仮定/ドキュメントに任されています。さて、これの何が問題なのでしょう？ 最大の問題の一つは、C の配列はポインタを通して、どんなデータにもアクセスできてしまうことです、配列に属さないデータに対してさえも。負の添え字ですら使えてしまいます！配列が、単一の値を指すポインタと完全に同じ型を使っていることに触れるまでもないでしょう。関数の引数としてポインタが渡されたとき、それは配列かもしれないし、単に一つの値へのポインタなのかもしれません。バッファオーバーフロー攻撃の出番です。これについてもっと詳しくは、Walter Bright の記事 $(LINK2 http://drdobbs.com/blogs/cpp/228701625, "C's biggest mistake") をどうぞ。
)
$(H2 スライスの導入)
$(P では、Dではこれをどう改善したのでしょう？ 多くの側面で、Dの配列はCの配列によく似ています。 実際、DはCのポインタを通じた配列の構文をサポートしています。 しかし、D は C の配列構文の上に、スライスと呼ばれる新しい型を導入しました。 スライスは（動的・静的に限らず）配列の一部分を表していて、ポインタ$(I と)その部分の長さを両方とも保持します。 データの長さを持つことによる保護と、裏でメモリを管理するガベージコレクタを合わせると、スライスは非常に協力でダイナミックな、しかもメモリ破壊からは守られた機能となっています。 加えて、D のスライスは、スライスを第一引数にとる関数で機能を拡張することができます。 これによって、どんな機能でも組み込みのプロパティやメソッドのように追加することが可能です。 D のスライスによって、他の言語ならぎこちなく遅くなっていたかもしれないコードを、高性能でエレガントで簡潔な構文で書くことができます。
)
$(P D のスライスの様子を簡単に見てみましょう:)
------
import std.stdio;
void main()
{
int[] a; // a はスライス
a = new int[5]; // 最低 5 要素を持つ、int の動的配列を確保。
// 最初の 5 個へのスライスを手に入れます。
// D のデータはすべて必ずデフォルトで初期化されています。
// int は 0 に初期化されるので、この配列は 5 個の 0 が入っています。
int[] b = a[0..2]; // 'スライス' 演算です。b は a の最初の二つの要素を指します。
// D は区間の終端は開いた形で指定します。
// つまりここでは、a[2] は b には含まれません。
int[] c = a[$-2..$]; // c は a の最後の二つの要素を指します。
// ($ はスライスや添え字式の中で使うと配列の長さを意味します。)
c[0] = 4; // a[3] にも値が代入される
c[1] = 5; // a[4] にも値が代入される
b[] = c[]; // a[] の最初の二つの要素に、
// 最後の二つの要素 (4, 5) を代入
writeln(a); // "[4, 5, 0, 4, 5]" を表示
int[5] d; // d は固定サイズの配列で、スタックに割り当てられます。
b = d[0..2]; // スライスは固定サイズの配列を指すこともできます！
}
------
$(P 配列割り当ての説明がちょっと複雑だな、と思われたことでしょう: "最低 5 要素を持つ、int の動的配列を確保。最初の 5 個へのスライスを手に入れます。" とは？ 単に "5 要素の動的配列を確保" では駄目なのでしょうか。 熟練した D 言語コーダーであっても、ときどき D の配列の概念に混乱することがあって、それには理由があります。 D のスライスは厳密な意味では動的配列型 $(I ではない) のです。たとえそう見えるとしても、少なくとも、動的配列として実態が完全に覆い隠されているとは言えません。 スライスが提供するのは、様々な型（動的, それ以外）の配列への安全で簡単な $(I インターフェイス) です。 以下では、おそらく D のスライスについてもっとも広く見られる誤解について議論します。
)
$(H2 責任者は誰だ？)
$(P D のスライスは、ほとんどの面で、動的配列のように見えます。装飾なしで渡された場合、参照されるデータは参照渡しされ、動的配列型がサポートしていそうなすべてのプロパティと関数はサポートしています。 しかし、一つ、重要な違いがあります。 スライスは配列を $(I 所有) しません。 配列を $(I 参照) しているのです。 つまり、スライスはデータの割り当てや解放に責任を持ちません。動的配列のメモリ管理に責任を持つ主体は、D のランタイムです。
)
$(P では、本物の動的配列は D のどこにあるのでしょう？ それはランタイムによって秘匿されています。 実は、動的配列を表すフォーマルな型は存在しません。 スライスさえあれば十分で、また見ていくとわかるように、データに対してやりたいことを全て理解してくれるように、ランタイムは賢く作られています。 動的配列という型が完全には存在しないことに、あなたはほぼ全ての瞬間気づくことはないでしょう。実際の所、ほとんどの D コーダーはスライス $(I こそが) 動的配列型であると思っています -- 仕様書にすら動的配列型として並んでいます！ 所有権のなさは非常に微かで、気づきにくい特質です。
)
$(P この事実のもう一つの帰結は、長さは配列のプロパティではなく、スライスのプロパティだということです。 つまり、length フィールドは配列の長さではなく、スライスの長さを意味しています。 これは言語に新しく触れる人にとって混乱しやすいところでもあります。 例えば。次のコードには大きな間違いがあります:
)
------
import std.stdio;
void shrinkTo2(int[] arr)
{
if(arr.length > 2)
arr.length = 2;
}
void main()
{
int[] arr = new int[5];
arr.shrinkTo2(); // shrinkTo2 をメソッド風に呼び出せます
writeln(arr.length); // 5 を出力
}
------
$(P これは渡された $(D arr) の長さを 2 に変えたように見えるかもしれません。しかし実際には何の効果も発生していません ($(D writeln) の出力を見るとわかります)。これは、データは参照として渡されていても、実際のポインタと長さは値で渡されているのが理由です。 多くの言語には、すべてのプロパティが参照で渡される配列型があります。 特に、C# と Java の配列は実際には完全に参照としてある Object です。 C++ の vector はデータとプロパティを両方参照渡しするか、両方値渡しするかのいずれかです。)
$(P この問題を修正するには、次の二つの方法が選べます。スライスを $(D ref) キーワードを明示することで参照渡しするか、結果のスライスを関数から返して再代入するか、です。例えば、参照渡しする場合の関数の型はこうなります:)
------
void shrinkTo2(ref int[] arr)
------
$(P この変更を加えたとすると、第二要素より後ろの要素はどうなるのでしょう？ D では、スライスはデータを所有しません。後ろの要素は依然としてそこにあり、霧の向こうにある動的配列型によって管理されています。その理由は根本的なもので、他のスライスがまだそのデータを参照しているかもしれないからです！ どんな $(I 単一の) スライスもデータを所有しないという事実は、どのスライスも配列のデータに対する他からの参照がないという仮定をできないことを意味しています。)
$(P データを参照するスライスが一個もなくなったらどうなるのでしょう？ D のガベージコレクタの出番です。 ガベージコレクタはスライスからまったく参照されなくなった動的配列を片付ける責任を負っています。 ガベージコレクタがあることで初めて、D のスライスの使い方が可能になっています。 スライスをとって動的配列として使ってそのまま終わっても、メモリをリークしたり、他のスライスをめちゃめちゃにしたり、とにかく配列の生存期間を心配したりする必要はありません。)
$(H2 伸ばせるスライス)
$(P D のスライスは、スライスの末尾にデータを追加する機能をサポートしています。これは本物の動的配列に非常に近いです。 言語には結合とデータ追加のための特別な演算子、チルダ ($(D ~)) があります。 いくつかの結合と追加の例をどうぞ:)
------
int[] a; // 空スライスは何もデータを指していませんが、追加はできます
a ~= 1; // int をいくつか追加すると、
a ~= 2; // その要素を保持する配列を自動で割り当てます。
a ~= [3, 4]; // 他の配列 (この場合、配列リテラル) を追加
a = a ~ a; // 自分自身と結合して、[1, 2, 3, 4, 1, 2, 3, 4] になる
int[5] b; // スタック上の固定サイズ配列
a = b[1..$]; // a は b のスライス
a ~= 5; // a はスタックを指しているので、
// 追加は再割り当てを行いますが、動きます！
------
$(P パフォーマンスが気になる方は、きっと、4個の要素を足したら何が起こるか気になっていることでしょう。 スライスはデータを所有しないのだから、追加のたびに新しい配列を再割り当てするのは避けられないのでは？ D のスライスに対する主な要求は、効率的であることです。 そうでなければプログラマには使われません。 D はこの問題を、プログラマには実質的に見えないところでこの問題を解決しています。 そしてそれが、スライスが本物の動的配列のように見える理由の一つです。)
$(H2 動作の仕組み)
$(P 前に配列を新しく割り当てるところで、$(I $(B 最低) 5 要素を持つ int の動的配列を確保しスライスを手に入れる) と言ったのを覚えていますか？ ここがランタイムが効率を稼ぐポイントです。 アロケータは、ページサイズ以下の範囲では常に 2 の冪乗サイズのブロックだけを割り当て (32-bit x86 ではページは 4096 バイトです)、それ以上ではページサイズの倍数のブロックを割り当てます。 ですから、配列を割り当てるときには、要求したよりも大きなサイズのブロックが手に入っていることになります。 たとえば、5 個の 32 bit 整数 (20 バイトを消費) を要求すると、32 バイトのブロックが帰ってきます。 これによって整数 3 個分の余裕ができます。)
$(P この余裕があれば再割り当てなしで整数を追加するのは明らかに可能ですが、問題は、有効でまだ使われているデータを "踏みつぶす" のは防がなければいけないということです。 スライスには同じデータを指す他のスライスの情報や、配列のどこ（先頭なのか中間なのか）を指しているのかの情報は持っていない、ということを覚えているでしょうか。 全てを正しく動作させるために、ランタイムはブロック自身に $(I 使用済み) バイト数を持たせています (この方法の小さな欠点は、ブロック内で使用可能なスペースが少しだけ小さくなることです。 今回の例では、例えば、再割り当てが発生するまでに 7 個の整数しか入れることができません。)
)
$(P スライスに要素を追加するようランタイムに要求すると、ランタイムは、ブロックが追加可能である (つまり $(I 使用済み) フィールドが有効) ことと、スライスが有効データの終わりと同じところで $(I 終わって) いることを確認します（スライスの先頭は重要ではありません）。 その後、新しいデータが余っているスペースに収まるかどうかを確認します。これらのチェックを全て通過すると、データは空きスペースに書き込まれ、$(I 使用済み) フィールドが新しいデータを含むように更新されます。 どれか一つでも失敗すると、新しい配列ブロックが割り当てられ、既存のデータと新しいデータで埋められます。 古いブロックには何が起きるのでしょう？ まだそのブロックを指す他のスライスが存在するなら、何も変わらず同じ場所に残ります。 他に参照がなければ、次のガベージコレクションのサイクルが回収します。 この仕組みによって、他のスライスを無効化せずにスライスの再割り当てが安全に実行できます。 これは C/C++ と比べると大きな進化です。C/C++ では、配列の再割り当てや vector の要素追加をすると、そのデータへの既存の参照（ポインタやイテレータ）は無効になっていました。)
$(P 結果として、要素追加は効率的であるだけではなく、普遍的に手軽です。 スライスに要素を足したくなったら、効率や他を壊す心配なく、いつでも足すことができます。 スライスのデータがヒープにあるのかスタックにあるのかROMにあるのか、null であるのかすら心配する必要はありません。 追加処理は（メモリが十分にあるという前提の下では）常に成功し、裏方の面倒はランタイムがすべて見てくれます。)
$(H2 決定性)
$(P 一つだけ、スライスの要素追加で初心者を、あるいは熟練者でさえも、嵌める落とし穴があります。要素追加の、目に見える非決定的な挙動です。)
$(P バッファを渡されて、A をいくつかバッファに書き込んで (必要なら追加して)、埋めたバッファを返す関数を考えましょう:)
------
import std.stdio;
char[] fillAs(char[] buf, size_t num)
{
if(buf.length < num)
buf.length = num; // 必要な分 A が入るようにサイズを拡張
buf[0..num] = 'A'; // A を全体に代入
return buf[0..num]; // 結果を返す。
}
------
$(P $(D fillAs) の何が悪いのでしょうか？ 何も悪くありませんが、しかし、length の増加が常にバッファを再割り当てさせるとしたらどうでしょう。 その場合は、バッファは渡されますが、それが A で埋められることは $(I なく)、再割り当てされたバッファだけが上書きされます。 これは、同じバッファを使い続けようとしていたり、あるいは元のバッファに値が埋められることを期待していた場合、驚くような結果になってしまいます。 最終結果は、$(D buf[]) が要素追加できるかどうかに依存して、呼び出し側のスライスが 'A' で埋められたり埋められなかったりするのです。)
------
// 例の続き...
void main()
{
char[] str = new char[10]; // ブロックの容量は
// 15 要素です。
str[] = 'B';
fillAs(str, 20); // 再割り当て発生 (20 > 15)
writeln(str); // "BBBBBBBBBB"
fillAs(str, 12); // その場でバッファが伸びる (12 <= 15)!
writeln(str); // "AAAAAAAAAA";
}
------
$(P 少し考えてみると、コストのかかる「追加のたびにコピー」セマンティクスを用いない限りはこれは避けられない問題であることに気づきます。 データを参照するすべてのスライスを追跡はできず、どこかにはデータを置かなければならないのです。 しかし、この問題を緩和する方法はいくつかあります:)
$(OL
$(LI 関数の返値をスライスに再代入する。この関数の最重要な結果は返値であり、バッファが使われたか否かではないことに注意して下さい。)
$(LI 渡したバッファを再度使うことはしない。 元々のスライスを二度と使わないのであれば、それに関して問題を感じることもないでしょう。)
)
$(P 関数の作者側としては、この手の問題を回避するためにできることはいくつかあります。 重要なポイントとして、この問題が発生するのは関数が渡されたスライスに要素追加やサイズ増加を行い、$(B そして) スライスの元々の範囲にデータを書き込む場合のみです。 できる限りこのような処理をする状況を避けることで、非決定性が露わになる可能性を減らすことができます。 のちほど、ランタイムがスライスにどう影響するかを予測するためのプロパティについて幾つか議論します。 また、ドキュメントで渡されたスライスがどのように上書きされる/されないかを書き残しておくのは良いアイデアと言えるでしょう。)
$(P 最後の選択肢は $(D ref) を使って確実に渡されたスライスを更新することです。 この手は、スライスはしばしば rvalue (入力専用) であることがあるので、使えないこともあります。 また、この方法では他のところにある同じデータを指すスライスに関する問題は解決していません。)
$(H2 キャッシュ)
$(P スライスへの追加での問題の一つは、この操作は高速ですが十分に高速ではないことです。 追加のたびにブロックのメタデータ (開始アドレス、サイズ、$(I 使用済み) バイト数) を参照する必要があり、これはガベージコレクタのメモリプールに対して O(lg(n)) 時間かかる参照になります (GCに対するグローバルなロックをとることなどを抜きにしても)。 でも、欲しいのは全体でならして考えると定数時間になる要素追加なのです。 この高いゴールを達成するために、キャッシュを使ったテクニックが導入されており、私の知る限りでは、これは D に独特のものです。)
$(P D ではデータがデフォルトでスレッドローカル記憶域に置かれるという特徴があるため、型システムによって、データがスレッドローカル（ほとんどのデータはそうです）なのか、全スレッドで共有されているのかがわかります。 この情報を使うと、スレッドローカルな要素追加にはロックなしでこのメタデータをキャッシュできます。 このキャッシュには最大で $(D N) 回の直近のメタデータ検索の結果を保持し、スライス追加のできる可能性の高速判定を可能にしています。)
$(H2 スライスのメンバと Appender)
$(P このように D のスライスは興味深い挙動をしめすため、時には、要素追加の際にどのような挙動をするか予測したいことがあります。 この目的のために、スライスにはいくつかのプロパティとメソッドが用意されています。)
$(P $(OBJREF reserve, size_t reserve(size_t n)): スライスに n 要素格納できるように領域を予約する。 スライスがその場で要素追加可能で、すでに最低 n 要素以上（n には既存の要素と追加の空き容量の両方を含みます）格納できる余地があれば、何も変化はありません。このメソッドは変更後の容量を返します。)
------
int[] slice;
slice.reserve(50);
foreach(int i; 0..50)
slice ~= i; // 再割り当ては起こらない
------
$(P $(OBJREF capacity, size_t capacity): あと何要素追加できるかを返すプロパティです。 その場で追加ができないスライスであれば、0 を返します。 返す容量は (非ゼロであれば) 現在のスライスの要素数も含むことにご注意下さい。)
------
int[] slice = new int[5];
assert(slice.capacity == 7); // 使用済みの 5 要素も含む
int[] slice2 = slice;
slice.length = 6;
assert(slice.capacity == 7); // 再割り当てなしの要素追加は容量を変えません
assert(slice2.capacity == 0); // slice2 は slice の第6要素を潰さないために、
// その場で伸ばすことはできなくなっています
------
$(P $(OBJREF assumeSafeAppend, assumeSafeAppend()): ランタイムに、スライスへの追加は可能と強制的に教え込みます。 本質的には、これは配列の $(I 使用済み) フィールドを指定のスライスの終端に合わせる操作です。)
------
int[] slice = new int[5];
slice = slice[0..2];
assert(slice.capacity == 0); // 追加は安全ではない。ブロック内の有効なデータを壊すので
slice.assumeSafeAppend();
assert(slice.capacity == 7); // 使用済みは 2 要素だけであると強制
------
$(P D のスライスの要素追加のパフォーマンスがまだどうしても要求するパフォーマンスに届かないときは、さらに別の選択肢があります。 $(FULL_STDREF array, Appender) 型を使うと、ランタイムからのメタデータを参照せずに、配列に最高速でデータを追加できます。 $(STDREF array, Appender) は要素追加操作を使った出力レンジとしても動作します (通常のスライスは自分のデータを上書きする出力レンジとしてしか使うことができません)。)
$(H2 まとめ)
$(P 熟練プログラマにも初心者プログラマにも、Dの配列とスライスの概念は、配列に対して行いたいほとんど全ての操作を可能にする非常に豊富な機能を提供しています。 パフォーマンスと使いやすさの両面に大きく焦点を当てた D のスライス型は、それの無い他の言語を使い始めるまでは、どれほど素晴らしいものであるが気づきにくい機能の一つとなっています。)
$(P $(I David Gileadi, Andrej Mitrovic, Jesse Phillips, Alex Dovhal, Johann !MacDonagh, Jonathan Davis の、この記事に対するレビューと提案に感謝します。))
© 2011-2012 by Steven Schveighoffer <br/>
<a rel="license" href="http://creativecommons.org/licenses/by-nd/3.0/"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-nd/3.0/88x31.png" /></a><br />This <span xmlns:dct="http://purl.org/dc/terms/" href="http://purl.org/dc/dcmitype/Text" rel="dct:type">work</span> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-nd/3.0/">Creative Commons Attribution-NoDerivs 3.0 Unported License</a>.
)
Macros:
D = <font face=Courier><b>$0</b></font>
D = <span class="d_inlinecode">$0</span>
H2=<h2>$0</h2>
H3=<h3>$0</h3>
TITLE=D言語のスライス機能
CATEGORY_ARTICLES=$0
FULL_STDREF = <a href="phobos/std_$1.html#$2">$(D std.$1.$2)</a>
STDREF = <a href="phobos/std_$1.html#$2">$(D $2)</a>
OBJREF = <a href="phobos/object.html#$1">$(D $2)</a>