概要
今回のブログポストではGolangで資料構造(Data structure)について調べて、使う方法について説明します。このブログポストで紹介するコードは次のリンクで確認できます。
マップ(Map)の資料構造については次のブログポストで確認できます。
資料構造
資料構造(Data structure)とは資料(値、Value)たちをどんな形で保存して、管理するかを意味します。資料構造は大きく、配列、リスト、キュー、スタックなどがあります。
Big-O表記方
Golangで資料構造を使う方法をみる前にBig-O表記方について説明します。Big-O表記方とはアルゴリズムの時間的、空間的効率性を表現するための表記方の1つで、一番多くつかわてる表記方です。
Big-O表記ほうは一番長くかかった時間、一番スペースを占める表現を表示します。
Big-O表記ほうは次のような順番で効率性を表示することができます。
O(1) < O(N) < O(N*log2N) < O(N2) < O(N3)
List
リスト(List)は最も基本的に使えてる線形資料構造中で1つです。
リストは次のような形を持っています。
type Element struct {
Value interface{}
Next *Element
Prve *Element
}
リストは現在変数に保存された値と以前と次の値にアクセスできるポインター変数を持っています。
Golangではcontainer/listのパッケージを使ってリストを使えます。
import "container/list"
v := list.New()
これを確認するためmain.goファイルを生成して次のように修正します。
package main
import (
"container/list"
"fmt"
)
func main() {
l := list.New()
element4 := l.PushBack(4)
element2 := l.PushFront(1)
l.InsertBefore(3, element4)
l.InsertAfter(2, element2)
fmt.Println("From Front")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
fmt.Println("From Back")
for e := l.Back(); e != nil; e = e.Prev() {
fmt.Print(e.Value, " ")
}
}
これを実行すると次のような結果が表示されます。
# go run main.go
From Front
1 2 3 4
From Back
4 3 2 1
ここで使ってる関数たちは次のような機能をしています。
- 一番最後に値を追加: PushBack
- 一番前に値を追加: PushFront
- 指定した位置の直前に値を追加: InsertBefore
- 指定した位置の直後に値を追加: InsertAfter
データの挿入
配列で一番前にデータを追加する場合、全てのデータを1つずつ移動して、一番前にデータを追加することになります。したがって、配列で一番前にデータを挿入する場合はO(N)アルゴリズムになります。
リストで一番前にデータを追加する場合、1つの要素を作って追加することになります。したがって、リストの一番前にデータを挿入する場合はO(1)アルゴリズムになります。
特定要素にアクセス
特定要素(Random Access)にアクセスする場合、配列はインデックスを使って直接アクセスができるのでO(1)になります。リストは一番最初から当該要素が見つかるまで移動する必要があるのでO(N)になります。
| 行為 | 配列、スライス | リスト |
|---|---|---|
| 要素挿入 | O(N) | O(1) |
| 要素削除 | O(N) | O(1) |
| 要素アクセス | O(1) | O(N) |
したがって、要素挿入や削除が多い場合リストを使うことが有利で特定要素にアクセスを多くする場合は配列を使うことが性能的に有利です。
また、一般的には要素の数が少ない場合、データのローカル性のためリストより配列がもっと早く処理されます。
- データのローカル性: データが隣接しているほどキャッシュの成功率が上がり、パフォーマンスも増加する。
キュー
キュー(Queue)は先入選出(FIFO - First in First Out)の構造を持つ資料構造で、待機列などを実装する時使えます。
Golangでは次のようにリストを使ってキューを実装することができます。
import "container/list"
type Queue struct {
v *list.List
}
func NewQueue() *Queue {
return &Queue{list.New()}
}
func (q *Queue) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Queue) Pop() interface{} {
front := q.v.Front()
if front == nil {
return nil
}
return q.v.Remove(front)
}
これを確認するためmain.goファイルを次のように修正します。
package main
import (
"container/list"
"fmt"
)
type Queue struct {
v *list.List
}
func NewQueue() *Queue {
return &Queue{list.New()}
}
func (q *Queue) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Queue) Pop() interface{} {
front := q.v.Front()
if front == nil {
return nil
}
return q.v.Remove(front)
}
func main() {
queue := NewQueue()
for i := 0; i < 5; i++ {
queue.Push(i)
}
v := queue.Pop()
for v != nil {
fmt.Println(v)
v = queue.Pop()
}
}
これを実行すると次のような結果が表示されます。
# go run main.go
0
1
2
3
4
スタック
スタック(Stack)は先入後出(FILO - First in Last Out)の構造を持つ資料構造で、関数のコールスタックなどでよく使えます。
Golangでは次のようにリストを使ってスタックを実装することができます。
import "container/list"
type Stack struct {
v *list.List
}
func NewStack() *Stack {
return &Stack{list.New()}
}
func (q *Stack) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Stack) Pop() interface{} {
back := q.v.Back()
if back == nil {
return nil
}
return q.v.Remove(back)
}
これを確認するためmain.goファイルを次のように修正します。
package main
import (
"container/list"
"fmt"
)
type Stack struct {
v *list.List
}
func NewStack() *Stack {
return &Stack{list.New()}
}
func (q *Stack) Push(v interface{}) {
q.v.PushBack(v)
}
func (q *Stack) Pop() interface{} {
back := q.v.Back()
if back == nil {
return nil
}
return q.v.Remove(back)
}
func main() {
stack := NewStack()
for i := 0; i < 5; i++ {
stack.Push(i)
}
v := stack.Pop()
for v != nil {
fmt.Println(v)
v = stack.Pop()
}
}
これを実行すると次のような結果が表示されます。
# go run main.go
4
3
2
1
0
リング
リング(Ring)の資料構造は最後の要素が最初の要素を指すリストを言います。リングは最後の要素が最初の要素を指してるので、一般的に要素の数を指定して、一番古い要素を消してもいい資料の場合使えます。
- 元に戻す機能: ドキュメントエディターなどで修正を元に戻す場合
- 固定サイズのバファ機能: データによってバファのサイズが変わらなく、固定のサイズを使う場合
- リプレイ機能: ゲームなどで最近のプレイ10秒をリプレイする場合
リングは次のようにサイズを固定したリストを生成して実装することができます。
import "container/ring"
ring := ring.New(5)
n := ring.Len()
for i := 0; i < n; i++ {
ring.Value = i
ring = ring.Next()
}
これを確認するためmain.goファイルを生成して次のように修正します。
package main
import (
"container/ring"
"fmt"
)
func main() {
ring := ring.New(5)
n := ring.Len()
for i := 0; i < n; i++ {
ring.Value = i
ring = ring.Next()
}
fmt.Println("From Front")
for i := 0; i < n; i++ {
fmt.Print(ring.Value, " ")
ring = ring.Next()
}
fmt.Println("")
fmt.Println("From Back")
for i := 0; i < n; i++ {
fmt.Print(ring.Value, " ")
ring = ring.Prev()
}
}
これを実行すると次のような結果が表示されます。
# go run main.go
From Front
0 1 2 3 4
From Back
0 4 3 2 1
完了
これでGolangで良く使える資料構造であるリスト、キュー、スタック、リンクについて見て見ました。このような資料構造を活用するともっと効率的にデータを管理して見てください。
私のブログが役に立ちましたか？下にコメントを残してください。それは私にとって大きな大きな力になります！
アプリ広報
Dekuが開発したアプリを使ってみてください。Dekuが開発したアプリはFlutterで開発されています。興味がある方はアプリをダウンロードしてアプリを使ってくれると本当に助かります。
