[翻訳]配列、スライス(および文字列):「挿入」メカニズム

エントリー



手続き型プログラミング言語の最も一般的な機能の1つは、配列の概念です。 配列は単純に見えるかもしれませんが、一方で、言語に追加する前に、次のようないくつかの問題を解決する必要があります。



これらの質問に対する答えは、配列を言語の単純な機能として、またはその設計の主要部分として定義します。



Goの初期の頃、これらの質問に対する答えを見つけるには、概念が適切と思われるようになるまでに何年もの議論が必要でした。 重要なステップは、柔軟で拡張可能なデータ構造を作成するために、固定サイズの配列に基づくスライスの概念を作成することでした。 ただし、Goの新参者の多くは、おそらく他の言語での経験がその足跡を残したために、スライスの原則につまずきます。



この出版物では、これらすべての誤解を払拭しようとします。 これは、 append関数がどのように機能するのか、それがなぜそのように機能するのか、それ以外には何も機能しないのかを説明する部分で実現します。



配列



配列はGo言語の重要な部分ですが、建物の基礎のように、より目に見える部分の下に隠されています。 より興味深く、強力で、注目に値するスライシング機能に進む前に、最新の状態にする必要があります。



Goのプログラムでは、配列の種類にサイズが含まれるため、使用が制限されるため、配列はあまり見られません。



たとえば、広告:

var buffer [256]byte
      
      





256バイトを含むバッファー変数を作成します。 バッファー変数タイプにはサイズが含まれ、 [256] byteのようになります 。 512バイトの配列は、タイプ[512] byteになります



配列に関連付けられているデータは、単なる要素の配列です。 概略的に、メモリ内のバッファは次のようになります。

 buffer: byte byte byte ... 256 times ... byte byte byte
      
      





つまり、変数には256バイトのデータだけが含まれます。 通常のインデックス構文バッファ[0]バッファ[1]などを使用してバッファ[255]に要素にアクセスできます( 0〜255のインデックスは256要素をカバーします)。 この範囲を超えようとすると、プログラムがクラッシュします。



組み込みのlen関数があり、配列、スライス、その他の型の要素数を返します。 明らかに、配列に対してlenを正確に返すもの。 この場合、 len(バッファ)は256を返します。



アレイの場合、アプリケーションの場所を見つけることができます。 たとえば、マトリックスの変換には適していますが、Goでの最も一般的な用途はスライスの保存です。



スライス:スライスヘッダー



面白いことが起こるスライスですが、使用を開始する前に、その必要性と何をしているのかを理解する必要があります。



スライスは、配列の複数のパーティションを記述するデータ構造であり、変数とは別に保存されます。 スライスは配列ではありません 。 スライスは、配列の一部を表します。



前のセクションのバッファー配列を使用する場合、配列をスライスすることにより、100から150(正確には100から149まで)の要素を記述するスライスを作成できます。

 var slice []byte = buffer[100:150]
      
      





このコードでは、正確には、完全な変数宣言を使用しました。 スライス変数のタイプは[] byteで 、「バイトのスライス」として読み取られ、要素100(包括的)から150(排他的)にスライスすることによりバッファ配列から作成されます。 より「標準的な」構文では、初期化プロセス中に定義される型を省略します。

 var slice = buffer[100:150]
      
      





そして、関数内では、短い形式の宣言を使用します。

 slice := buffer[100:150]
      
      





スライスとは何ですか? これは完全な説明ではありませんが、今後はスライスを、長さと配列要素へのポインタという2つの要素で構成される小さな構造と考えてください。 これを舞台裏で次のようなものと考えてください。

 type sliceHeader struct { Length int ZerothElement *byte } slice := sliceHeader{ Length: 50, ZerothElement: &buffer[100], }
      
      





もちろん、これは単なる例です。 これにもかかわらず、この例からは、 sliceHeader構造体プログラマーにアクセスできず、ポインターのタイプは要素のタイプに依存しますが、スライスの仕組みの基本的な考え方を理解することができます。



これまで、配列をスライスする操作を使用しましたが、スライスをスライスすることもできます。

 slice2 := slice[5:10]
      
      







前と同じ方法で、この操作は新しいスライスを作成しますが、この場合は元のスライスに関連する要素5〜9(両端を含む)から作成されます。 slice2変数の基本的なsliceHeader構造は次のようになります。

 slice2 := sliceHeader{ Length: 5, ZerothElement: &buffer[105], }
      
      





ヘッダーは、 バッファ変数にある基になる配列を指すことに注意してください。



再度カットすることもできます。これは、スライスをカットし、カットされたスライスの構造に結果を保存することを意味します。 つまり 後:

 slice = slice[5:10]
      
      





スライス変数のsliceHeader構造は、 slice2変数の場合と同じように見えます。 たとえば、スライスをカットするなど、オーバーシュートが頻繁に発生します。 この例では、スライスの最初と最後の要素が省略されます。

 slice = slice[1:len(slice)-1]
      
      





多くの場合、経験豊富なGoプログラマーから「スライスヘッダー」について聞くことができます。 これは、スライス変数に格納されるものです。 たとえば、 bytes.IndexRuneなど、スライスを引数として取る関数を呼び出すと、ヘッダーが関数に渡されます。 この例では:

 slashPos := bytes.IndexRune(slice, '/')
      
      





スライス引数はIndexRune関数に渡されます。実際、これは単なる「スライスヘッダー」です。



「スライスヘッダー」には、以下で説明する別のデータ要素がありますが、最初に、スライサーを使用するプログラムを作成するときの「スライスヘッダー」の意味を見てみましょう。



スライスを関数に渡す



スライスにポインターが含まれていても、それ自体が値であることを理解することが非常に重要です。 内部では、これはポインターと長さを含む構造です。 これは構造体へポインタではありません



これは重要です。



前の例でIndexRuneを呼び出すと、 「ヘッダーの上部」のコピーが 取得されます。 この動作は重要な結果をもたらします。



簡単な関数を考えてみましょう:

 func AddOneToEachElement(slice []byte) { for i := range slice { slice[i]++ } }
      
      





彼女はタイトルに書かれていることを正確に行います。 ( for rangeループを使用し )すべてのスライス要素をトラバースし、要素を増やします。



試してください:

 func main() { slice := buffer[10:20] for i := 0; i < len(slice); i++ { slice[i] = byte(i) } fmt.Println("before", slice) AddOneToEachElement(slice) fmt.Println("after", slice) }
      
      





スライスヘッダー 」は関数に渡されますが、配列の要素へのポインターが含まれているため、元のスライスヘッダーとそのコピーは同じ配列を表します。 その結果、関数が終了すると、変更された要素を元のスライスから見ることができます。



関数への引数は実際にはコピーであり、この例はこれを示しています。

 func SubtractOneFromLength(slice []byte) []byte { slice = slice[0 : len(slice)-1] return slice } func main() { fmt.Println("Before: len(slice) =", len(slice)) newSlice := SubtractOneFromLength(slice) fmt.Println("After: len(slice) =", len(slice)) fmt.Println("After: len(newSlice) =", len(newSlice)) }
      
      





ここでは、関数では引数の内容を変更できますが、 タイトルでは変更できないことがわかります。 長さはスライス変数に格納され、関数を呼び出しても変更されません。これは、スライスヘッダーのコピーが元のものではなく関数に渡されるためです。 したがって、タイトルを変更する関数を作成する場合は、例で行ったように、それを返す必要があります。 スライス変数は変更されませんが、戻り値には新しい長さがあり、これはnewSliceに格納されます



スライサーポインター:生産方法



スライスヘッダーを変更する関数を記述する別の方法があります。これは、スライスへのポインターを関数に渡すことです。 この機能を示すための例のバリエーションを次に示します。

 func PtrSubtractOneFromLength(slicePtr *[]byte) { slice := *slicePtr *slicePtr = slice[0 : len(slice)-1] } func main() { fmt.Println("Before: len(slice) =", len(slice)) PtrSubtractOneFromLength(&slice) fmt.Println("After: len(slice) =", len(slice)) }
      
      





抽象化のレベル(一時変数)が余分であるため、例は少し厄介に思えるかもしれませんが、スライスへのポインターを使用する場合が1つあります。 スライスを変更するメソッドを記述するとき、レシーバーとしてポインターを使用するのが慣例です。



最後のスラッシュを削除する方法が必要だとしましょう。 次のように記述できます。

 type path []byte func (p *path) TruncateAtFinalSlash() { i := bytes.LastIndex(*p, []byte("/")) if i >= 0 { *p = (*p)[0:i] } } func main() { pathName := path("/usr/bin/tso") //     path pathName.TruncateAtFinalSlash() fmt.Printf("%s\n", pathName) }
      
      





この例を実行すると、必要なことが起こることがわかります。つまり、メソッドがスライスを変更します。



一方、ASCII文字の大文字を設定するパスのメソッドを作成する場合(英語の文字で動作が定義されていない場合)、レシーバーの値は必要な配列を指すため、メソッドはポインターではなく値を操作できます。

 type path []byte func (p path) ToUpper() { for i, b := range p { if 'a' <= b && b <= 'z' { p[i] = b + 'A' - 'a' } } } func main() { pathName := path("/usr/bin/tso") pathName.ToUpper() fmt.Printf("%s\n", pathName) }
      
      





ここで、 ToUpperメソッドは、要素のインデックスを使用するためにfor範囲で2つの変数を使用し、スライス要素自体を直接使用します。 これにより、 p [i]への再書き込みが回避されます。



収容人数



次の関数を考えてください。これは、 intのスライスを1要素だけ増やします

 func Extend(slice []int, element int) []int { n := len(slice) slice = slice[0 : n+1] slice[n] = element return slice }
      
      





次に実行します:

 func main() { var iBuffer [10]int slice := iBuffer[0:0] for i := 0; i < 20; i++ { slice = Extend(slice, i) fmt.Println(slice) } }
      
      





...スライスが成長するまで、どのように成長するかを見てみましょう。



スライスヘッダーの3番目のコンポーネントである容量について説明します。 配列へのポインターとその長さに加えて、スライスヘッダーにはその容量が含まれます。

 type sliceHeader struct { Length int Capacity int ZerothElement *byte }
      
      





[ Capacity]フィールドには、アレイが実際に占有するスペースのレコードが含まれます-これは、 Lengthが到達できる最大値です。 容量を超えてカットを増やすと、アレイが流出し、緊急プログラムが終了します。



この例では、スライスを作成します

 slice := iBuffer[0:0]
      
      





そのタイトルは次のようになります。

 slice := sliceHeader{ Length: 0, Capacity: 10, ZerothElement: &iBuffer[0], }
      
      





[ 容量]フィールドは、元の配列の長さから配列要素のインデックスを引いたものに相当します。これは、最初のスライス要素(この場合はゼロ)です。 スライスの容量を知りたい場合は、 cap関数を使用します。

 if cap(slice) == len(slice) { fmt.Println("slice is full!") }
      
      







作る



容量よりもカットを増やしたい場合はどうすればよいですか? できません! 定義では、容量が成長の限界です。 しかし、新しい配列を作成し、データをコピーし、新しい配列を記述するスライスを変更することで同じ結果を得ることができます。



強調表示から始めましょう。 新しい関数を使用してより大きな配列を割り当て、より大きなスライスを作成できますが、 make関数を使用する方が簡単です。 新しい配列を選択し、スライスヘッダーを作成します。 make関数には3つの引数があります。スライスタイプ、初期長、およびその容量です。ここで、配列の長さは、 makeがスライスデータに割り当てるものです。 その結果、この関数呼び出しは長さ10のスライスを作成し、5(15-10)で拡張する可能性があります。これを実行すると確認できます。

  slice := make([]int, 10, 15) fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))
      
      





このスニペットは、 intスライスの容量を2倍にしますが、同じ長さを残します。

  slice := make([]int, 10, 15) fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice)) newSlice := make([]int, len(slice), 2*cap(slice)) for i := range slice { newSlice[i] = slice[i] } slice = newSlice fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))
      
      





その後、スライスには、別の再配布が必要になる前に、成長する余地がはるかに大きくなります。



スライスを作成するとき、長さと容量がまったく同じになることがよくあります。 make関数には短縮バージョンがあります。 デフォルトの長さが容量になるため、単一の値で指定できます。 後

 gophers := make([]Gopher, 10)
      
      





gophersスライスでは、長さと容量は10になります。



コピー



前のセクションでスライスの容量を2倍にした後、ループを書き換えて古いデータを新しいスライスにコピーしました。 Goには、このタスクを簡素化する組み込みのコピー機能があります。 彼女の引数は2つのスライスで、彼女はデータを右から左のスライスにコピーします。 copyを使用するように書き直した例を次に示します

  newSlice := make([]int, len(slice), 2*cap(slice)) copy(newSlice, slice)
      
      





コピー機能はスマートです。 両方の引数の長さに注意して、できることだけをコピーします。 つまり、コピーされる要素の数は、両方のスライスの長さの最小値に等しくなります。 これは少しの「官僚主義」を救うことができます。 さらに、 copyは整数値(コピーされた要素の数)を返しますが、これは常に確認する価値があるとは限りません。



コピー機能は、ソースとレシーバーが交差する場合も考慮します(約Trans。これはCのmemmove()に似ています)。つまり、この機能を使用して1つのスライス内の要素を移動できます。 以下は、 コピー機能を使用してスライスの中央に値を貼り付ける方法の例です。

 //        , //      . //        . func Insert(slice []int, index, value int) []int { //      slice = slice[0 : len(slice)+1] //  copy           copy(slice[index+1:], slice[index:]) //   . slice[index] = value //  . return slice }
      
      





この機能には、いくつかの注意点があります。 まず、明らかなことですが、長さが変更されているため、スライスを返す必要があります。 第二に、便利な収縮が使用されます。 表現

 slice[i:]
      
      





と同じことを意味します

 slice[i:len(slice)]
      
      





さらに、別のトリックを使用しませんでした。式の最初の要素を空のままにすることもできます。 デフォルトではゼロになります。 このように

 slice[:]
      
      





それは単にそれ自体をスライスすることを意味し、配列をスライスするときに便利です。 この式は最短です:「配列のすべての要素を記述するスライス」:

 array[:]
      
      





しかし、それはケースとケースの間にありました。 挿入関数を試してみましょう。

  slice := make([]int, 10, 20) // ,  capacity > length:     . for i := range slice { slice[i] = i } fmt.Println(slice) slice = Insert(slice, 5, 99) fmt.Println(slice)
      
      







挿入:例



数セクション前に、1つの要素でスライスを拡張するExtend関数を作成しました。 スライスの容量が小さすぎる場合にのみ機能が失敗する可能性があるという理由だけで、間違っていました(この例では、 挿入機能にも同じ問題が発生します)。 これで修正方法がわかったので、整数スライス用のExtend関数の信頼できる実装を作成しましょう。

 func Extend(slice []int, element int) []int { n := len(slice) if n == cap(slice) { //  ;  . //       1,     ,      newSlice := make([]int, len(slice), 2*len(slice)+1) copy(newSlice, slice) slice = newSlice } slice = slice[0 : n+1] slice[n] = element return slice }
      
      





この場合、スライスを返すことが特に重要です。なぜなら、スライスを再配布すると、取得したスライスがまったく異なる配列を記述するからです。 スライスがいっぱいになった場合に何が起こるかを示すための小さなスライスを次に示します。

  slice := make([]int, 0, 5) for i := 0; i < 10; i++ { slice = Extend(slice, i) fmt.Printf("len=%d cap=%d slice=%v\n", len(slice), cap(slice), slice) fmt.Println("address of 0th element:", &slice[0]) }
      
      





サイズ5の初期配列がいっぱいになったときの再配布に注意してください。 新しい配列が割り当てられると、nullアイテムの容量とアドレスが変わります。



堅牢なExtend関数をベースとして使用すると、スライスを複数の要素で拡張できるさらに優れた関数を作成できます。 これを行うには、引数のリストを配列に変換するGoの機能を利用します。 つまり、可変数の関数引数を使用するGoの機能を使用します。



関数appendを呼び出しましょう。 最初のバージョンでは、関数の引数がなくなるまでExtendを呼び出すことができます。 Append関数のプロトタイプは次のようになります。

 func Append(slice []int, items ...int) []int
      
      





これは、 Appendが1つの引数(スライス)を取り、それがint型の引数のゼロから無限まで続くことを示しています。 ご覧のように、これらの要素は将来のスライススライスです。

 // Append    . //  :    Extend. func Append(slice []int, items ...int) []int { for _, item := range items { slice = Extend(slice, item) } return slice }
      
      





forレンジループは、 [] int型のitems引数の各要素に対して実行されることに注意してください。 また、空の識別子_を使用していることに注意してください。これはインデックスを破棄します。これはループでは必要ないためです。



これを試してください:

  slice := []int{0, 1, 2, 3, 4} fmt.Println(slice) slice = Append(slice, 5, 6, 7, 8) fmt.Println(slice)
      
      





この例のもう1つの新しいトリックは、スライスの初期化が、中括弧で囲まれた型とスライス要素で構成される複合リテラルで行われることです。

  slice := []int{0, 1, 2, 3, 4}
      
      





追加も別の理由で興味深いです。 要素を追加するだけでなく、...を使用してスライスを引数として関数に渡すことができます。

  slice1 := []int{0, 1, 2, 3, 4} slice2 := []int{55, 66, 77} fmt.Println(slice1) slice1 = Append(slice1, slice2...) // '...' ! fmt.Println(slice1)
      
      





もちろん、 Extendに基づいた単一選択により、 Appendをより効率的にすることができます。

 // Append    . //  . func Append(slice []int, elements ...int) []int { n := len(slice) total := len(slice) + len(elements) if total > cap(slice) { // .    1.5 ,     . newSize := total*3/2 + 1 newSlice := make([]int, total, newSize) copy(newSlice, slice) slice = newSlice } slice = slice[:total] copy(slice[n:], elements) return slice }
      
      





ここでは、 コピーを 2回使用してデータスライスを新しいメモリに移動し、追加したアイテムを古いデータの最後にコピーします。



試してみてください、動作は以前と同じです:

  slice1 := []int{0, 1, 2, 3, 4} slice2 := []int{55, 66, 77} fmt.Println(slice1) slice1 = Append(slice1, slice2...) // '...' ! fmt.Println(slice1)
      
      







追加:組み込み関数



そのため、Goでは組み込み関数appendを追加する必要があるという結論に達しました。 例のAppend関数と同じことを同じ効率で行いますが、どのタイプのスライサーでも機能します。



Goの弱点は、「ジェネリック型」で定義された操作を実行時に提供する必要があることです。 いつかこれは変わるかもしれませんが、スライサーでの作業を簡素化するために、Goは組み込みの一般関数appendを提供します 。 整数バージョンと同じように機能しますが、 どのタイプのスライスでも機能します。



appendを呼び出すたびにスライスヘッダーが更新されるため、呼び出し後に結果のスライスを保存する必要があることに注意してください。 実際、コンパイラーは、結果を保存せずにappendを呼び出すことを許可しません。



単一行の出力を次に示します。 それらを試して、変更して探索してください:

  //    . slice := []int{1, 2, 3} slice2 := []int{55, 66, 77} fmt.Println("Start slice: ", slice) fmt.Println("Start slice2:", slice2) //    . slice = append(slice, 4) fmt.Println("Add one item:", slice) //     . slice = append(slice, slice2...) fmt.Println("Add one slice:", slice) //    (int). slice3 := append([]int(nil), slice...) fmt.Println("Copy a slice:", slice3) //      . fmt.Println("Before append to self:", slice) slice = append(slice, slice...) fmt.Println("After append to self:", slice)
      
      







停止して例の最後の行について考え、スライスの設計によってこのような単純な呼び出しを正しく行うことができる方法を理解する必要があります。



Slice Tricks wiki(コミュニティ作成)には、 appendcopy、その他のスライスの使用方法を使用した多くの例があります



なし



さらに、新しく獲得した知識を使用して、「ゼロ」カットとは何かを理解できます。 当然、これはスライスヘッダーのnull値です。

 sliceHeader{ Length: 0, Capacity: 0, ZerothElement: nil, }
      
      





または単に

 sliceHeader{}
      
      





重要なのは、ポインターもnilであるということです。 このスライス

 array[0:0]
      
      





長さはゼロですが(容量がゼロの場合もあります)、そのポインターはnilではないため、まだゼロスライスではありません。



明らかに、空のスライスは成長できます(容量がゼロでないと仮定します)が、「nil」( nil )スライスには、少なくとも1つの要素が含まれていても、値を入れて成長できない配列は含まれません。



何も示さない場合でも、「nil」スライスは長さがゼロのスライスと本質的に同等であることに注意してください。長さはゼロで、選択して何かを追加できます。一例として、スライスが「ゼロ»(追加することによって、コピーされる上記の数行、見ゼロ)スライス。





次に、スライスのコンテキストでのGoの行について簡単に説明します。



実際、文字列は非常に単純です。これらは読み取り専用のバイトスライスであり、言語から少し余分な構文サポートがあります。



読み取り専用であるため、容量はありません(増やすことはできません)が、ほとんどの場合、バイトのスライスとして扱うことができます。



まず、インデックスを使用して個々のバイトにアクセスできます。

 slash := "/usr/ken"[0] //   '/'
      
      





文字列をスライスしてサブストリングを作成できます。

 usr := "/usr/ken"[0:4] //   "/usr"
      
      





糸を切るときにカーテンの後ろで何が起こるかは明らかです。



したがって、単純な変換によって、通常のバイトスライスを取得し、そこから文字列を作成できます。

 str := string(slice)
      
      





また、文字列からバイトのスライスを作成します。

 slice := []byte(usr)
      
      





文字列の基礎となる配列はビューから隠されています。文字列を介してアクセスする方法はありません。これは、これらの変換を行うときに、配列のコピーを作成する必要があることを意味します。 Goが仕事を引き受けるので、心配する必要はありません。このような変換の後、基礎となるバイトスライスの配列を変更しても、対応する行には影響しません。



文字列のスライスと同様の動作の重要な結果は、部分文字列の作成が非常に効率的であることです。必要なのは、行の2つの上部を作成することだけです。文字列は読み取り専用なので、元の文字列とスライスの結果として取得された文字列は、同じ配列を安全に共有できます。



歴史的なメモ:初期の文字列実装は常に個別に際立っていましたが、それ以降、言語にスライスが登場し、文字列をより効率的に処理できるようになりました。一部のベンチマークでは、速度が大幅に向上し始めました。



もちろん、行について話すことはもっとたくさんありますが、このトピックは別の出版物のためのものです。



おわりに



スライスの原理を理解することは、それらがどのように作られるかを理解するのに役立ちます。小さなデータ構造、スライスタイプ変数に関連付けられたスライスヘッダーがあり、このヘッダーは個別に割り当てられた配列の一部を示します。スライスを作成すると、ヘッダーがコピーされますが、配列は常に分割されます。



作業を評価した後、スライスは使いやすくなるだけでなく、特に組み込みのコピーおよび追加機能により、強力で表現力豊かになります




オリジナルの出版物-blog.golang.org/slices



All Articles