[GO 마스터하기] 05-Go 자료구조

이진트리

이진트리는 각 노드마다 최대 두개의 자식 노드를 가진다. 루트부터 리프까지의 최대 거리와 최소 거리의 차이가 1 이하이면 균형이 잡혔다고 표현한다. 균형을 잡는 작업은 다소 까다롭고 속도도 느리기 때문에, 노드의 수가 많을수록 균형을 잡은 상태로 만들기 시작하는 것이 좋다.

package main

import (
    "fmt"
    "math/rand"
    "time"
)

type Tree struct {
    Left *Tree
    Value int
    Right *Tree
}

func traverse(t *Tree) {
    if t == nil {
        return
    }
    traverse(t.Left)
    fmt.Print(t.Value, " ")
    traverse(t.Right)
}

func create(n int) *Tree {
    var t *Tree
    rand.Seed(time.Now().Unix())
    for i := 0; i < 2*n; i++ {
        temp := rand.Intn(n * 2)
        t = insert(t, temp)
    }
    return t
}

func insert(t *Tree, v int) *Tree {
    if t == nil {
        return &Tree{nil, v, nil}
    }
    if v == t.Value {
        return t
    }
    if v < t.Value {
        t.Left = insert(t.Left, v)
        return t
    }
    t.Right = insert(t.Right, v)
    return t
}

func main() {
    tree := create(10)
    fmt.Println("Root : ", tree.Value)
    traverse(tree)
    fmt.Println()
    tree = insert(tree, -10)
    tree = insert(tree, -2)
    traverse(tree)
    fmt.Println()
    fmt.Println("Root : ", tree.Value)
}

• traverse() 함수는 이진 트리를 구성하는 모든 노드를 재귀 호출한다.
• create() 함수는 이진 트리를 정수형 난수로 채운다.
• insert() 함수는 이진 트리의 속성 대로 숫자를 트리에 삽입한다.

$ go run foo.go
Root :  10
1 4 9 10 11 12 13 14 15 18 19 
-10 -2 1 4 9 10 11 12 13 14 15 18 19 
Root :  10

이진 트리의 장점

계층형 데이터를 표현하는데 트리만큼 좋은 것은 업다. 프로그래밍 언어의 컴파일러에서 프로그램을 파싱할 때 트리를 굉장히 많이 사용한다.

트리는 기본적으로 순서를 가진다. 다시 말해 정렬하기 위한 작업을 따로 수행할 필요가 없다. 원소를 적절한 위치에 추가하는 과정이 곧 정렬하는 과정이다. 하지만 원소를 삭제하는 것은 트리의 구성 방식에 따라 쉽지 않을 수 있다.

이진 트리의 균형이 잡혀 있다면 모든 연산은 대략 log n이다. 또한 균형 이진 트리의 높이는 대략 log2n이다.

이진 트리의 큰 단점은 트리의 모양이 원소를 추가하는 순서에 따라 달라진다는 것이다.

이진 트리보다 연결 리스트나 배열이 훨씬 빠르지만, 검색 연산에 대한 유연성은 이러한 성능 및 관리의 오버헤드를 상쇄하고도 남는다. 이진 트리에서 특정한 원소를 탐색할 때 그 원소의 값이 현재 노드보다 작은지 검사할 수 있고, 이러한 방법으로 트리를 탐색할 때 방향을 결정할 수 있다.

해시 테이블 만들기

해시 테이블은 한 개 이상의 키와 값을 쌍을 저장하는 자료 구조이다. 해시 함수는 버킷 또는 슬롯 배열에서 원하는 값이 담긴 위치를 계산할 때 사용한다. 이상적인 해시 함수는 각 키마다 고유한 버킷을 가리켜야한다. 단 버킷의 수는 필요한 만큼 있어야한다.

좋은 해시 함수는 고르게 분산된 해시값을 생성한다. 사용하지 않는 버킷이 많거나 버킷 사이의 크기가 심하면 성능이 떨어지기 때문이다.

package main

import "fmt"

const SIZE = 15 

type Node struct {
    Value int 
    Next *Node
}

type HashTable struct {
    Table map[int]*Node 
    Size int
}

func hashFunction(i, size int) int {
    return (i % size) 
}

func insert(hash *HashTable, value int) int {
    index := hashFunction(value, hash.Size) 
    element := Node{Value : value, Next : hash.Table[index]}
    hash.Table[index] = &element
    return index 
}

func traverse(hash *HashTable) {
    for k := range hash.Table {
        if hash.Table[k] != nil {
            t := hash.Table[k]
            for t != nil {
                fmt.Printf("%d -> ", t.Value) 
                t = t.Next
            }
            fmt.Println()
        }
    }
}

func lookup(hash *HashTable, value int) bool {
    index := hashFunction(value, hash.Size) 
    if hash.Table[index] != nil {
        t := hash.Table[index]
        if t != nil {
            if t.Value == value {
                return true 
            }
            t = t.Next
        }
    }
    return false 
}
func main() {
    table := make(map[int]*Node, SIZE) 
    hash := &HashTable{Table: table, Size: SIZE}
    fmt.Println("Num of spaces :", hash.Size) 
    for i := 0; i < 120; i++ {
        insert(hash, i)
    }
    traverse(hash)
}

해시 테이블에 n개의 키와 k개의 버킷이 있다면 n개의 키에 대한 탐색 속도를 O n 에서 O n/k로 높일 수 있다.

$ go run foo.go
Num of spaces : 15
106 -> 91 -> 76 -> 61 -> 46 -> 31 -> 16 -> 1 -> 
109 -> 94 -> 79 -> 64 -> 49 -> 34 -> 19 -> 4 -> 
113 -> 98 -> 83 -> 68 -> 53 -> 38 -> 23 -> 8 -> 
116 -> 101 -> 86 -> 71 -> 56 -> 41 -> 26 -> 11 -> 
105 -> 90 -> 75 -> 60 -> 45 -> 30 -> 15 -> 0 -> 
112 -> 97 -> 82 -> 67 -> 52 -> 37 -> 22 -> 7 -> 
115 -> 100 -> 85 -> 70 -> 55 -> 40 -> 25 -> 10 -> 
117 -> 102 -> 87 -> 72 -> 57 -> 42 -> 27 -> 12 -> 
119 -> 104 -> 89 -> 74 -> 59 -> 44 -> 29 -> 14 -> 
108 -> 93 -> 78 -> 63 -> 48 -> 33 -> 18 -> 3 -> 
114 -> 99 -> 84 -> 69 -> 54 -> 39 -> 24 -> 9 -> 
118 -> 103 -> 88 -> 73 -> 58 -> 43 -> 28 -> 13 -> 
107 -> 92 -> 77 -> 62 -> 47 -> 32 -> 17 -> 2 -> 
110 -> 95 -> 80 -> 65 -> 50 -> 35 -> 20 -> 5 -> 
111 -> 96 -> 81 -> 66 -> 51 -> 36 -> 21 -> 6 ->

연결 리스트 만들기

package main

import "fmt"

type Node struct {
    Value int
    Next *Node
}

var root = new(Node)

func addNode(t *Node, v int) int {
    if root == nil {
        t = &Node{v, nil}
        root = t
        return 0
    }
    if v == t.Value {
        fmt.Println("Node already exists : ", v)
        return -1
    }
    if t.Next == nil {
        t.Next = &Node{v, nil}
        return -2
    }
    return addNode(t.Next, v)
}

func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> Empty list!")
        return
    }
    for t != nil {
        fmt.Printf("%d -> " , t.Value)
        t = t.Next
    }
    fmt.Println()
}

func lookupNode(t *Node, v int) bool {
    if root == nil {
        t = &Node{v, nil}
        root = t
        return false
    }
    if v == t.Value {
        return true
    }
    if t.Next == nil {
        return false
    }
    return lookupNode(t.Next, v)
}

func size(t *Node) int {
    if t == nil {
        fmt.Println("-> Empty list!")
        return 0
    }
    i := 0
    for t != nil {
        i++
        t = t.Next
    }
    return i
}

func main() {
    fmt.Println(root) 
    root = nil 
    traverse(root) 
    addNode(root, 1)
    addNode(root, -1)
    traverse(root)
    addNode(root, 10)
    addNode(root, 5)
    addNode(root, 45)
    addNode(root, 5)
    addNode(root, 5)
    traverse(root)
    addNode(root, 100)
    traverse(root)

    if lookupNode(root, 100) {
        fmt.Println("Node exists!")
    } else {
        fmt.Println("Node does not exists!")
    }

    if lookupNode(root, -100) {
        fmt.Println("Node exists")
    } else {
        fmt.Println("Node does not exists!")
    }
}

$ go run foo.go
&{0 <nil>}
-> Empty list!
1 -> -1 -> 
Node already exists :  5
Node already exists :  5
1 -> -1 -> 10 -> 5 -> 45 -> 
1 -> -1 -> 10 -> 5 -> 45 -> 100 -> 
Node exists!
Node does not exists!

정렬된 연결 리스트를 사용하면 노드를 탐색하거나 추가하는 과정에서 다양한 최적화 기법을 적용할 수 있다. 가장 흔히 사용하는 방법은 정렬된 연결 리스트의 중심 노드에 포인터를 저장하고 있다가 탐색을 수행할 때 그 지점에서 시작한다.

이중 연결 리스트 만들기

package main

import "fmt"

type Node struct {
    Value int
    Previous *Node
    Next *Node
}
var root = new(Node)

func addNode(t *Node, v int) int {
    if root == nil {
        t = &Node{v, nil, nil}
        root = t
        return 0
    }
    if v == t.Value {
        fmt.Println("Node already exists")
        return -1
    }
    if t.Next == nil {
        temp := t
        t.Next = &Node{v, temp, nil}
        return -2
    }
    return addNode(t.Next, v)
}

func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> Empty list")
        return
    }
    for t != nil {
        fmt.Println("-> Empty list")
        return
    }
    fmt.Println()
}

func reverse(t *Node) {
    if t == nil {
        fmt.Println("-> Empty list!")
        return
    }
    temp := t
    for t != nil {
        temp = t
        t = t.Next
    }
    for temp.Previous != nil {
        fmt.Printf("%d -> ", temp.Value)
        temp = temp.Previous
    }
    fmt.Printf("%d -> ", temp.Value)
    fmt.Println()
}

func size(t *Node) int {
    if t == nil {
        fmt.Println("-> Empty list!")
        return 0
    }
    n := 0
    for t != nil {
        n++
        t = t.Next
    }
    return n
}

func lookupNode(t *Node, v int) bool {
    if root == nil {
        return false
    }
    if v == t.Value {
        return true
    }
    if t.Next == nil {
        return false
    }
    return lookupNode(t.Next, v)
}

func main() {
    fmt.Println(root)
    root = nil
    traverse(root)
    addNode(root, 1)
    addNode(root, -1)
    traverse(root)
    addNode(root, 10)
    addNode(root, 5)
    addNode(root, 0)
    addNode(root, 0)
    traverse(root)
    addNode(root, 100)
    fmt.Println("Size :", size(root))
    traverse(root)
    reverse(root)
}

$ go run foo.go
&{0 <nil> <nil>}
-> Empty list
-> Empty list
Node already exists
-> Empty list
Size : 6
-> Empty list
100 -> 0 -> 5 -> 10 -> -1 -> 1 ->

리스트를 탐색할 때 양방향 모두 이동할 수 있고 원소를 더 쉽게 추가하거나 삭제할 수 있다. 헤드에 대한 포이터를 잃어버리더라도 리스트의 헤드 노드를 찾아 낼 수 있다.

큐 만들기

package main

import "fmt"

type Node struct {
    Value int
    Next  *Node
}

var size = 0
var queue = new(Node)

func Push(t *Node, v int) bool {
    if queue == nil {
        queue = &Node{v, nil}
        size++
        return true
    }
    t = &Node{v, nil}
    t.Next = queue
    queue = t

    size++
    return true
}

func Pop(t *Node) (int, bool) {
    if size == 0 {
        return 0, false
    }
    if size == 1 {
        queue = nil
        size--
        return t.Value, true
    }
    temp := t

    for t.Next != nil {
        temp = t
        t = t.Next
    }

    v := temp.Next.Value
    temp.Next = nil

    size--
    return v, true
}

func traverse(t *Node) {
    if size == 0 {
        fmt.Println("Empty Q")
        return
    }
    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }
    fmt.Println()
}

func main() {
    queue = nil
    Push(queue, 10)
    fmt.Println("Size:", size)
    traverse(queue)

    v, b := Pop(queue)
    if b {
        fmt.Println("Pop:", v)
    }
    fmt.Println("Size : ", size)

    for i := 0; i < 5; i++ {
        Push(queue, i)
    }
    traverse(queue)
    fmt.Println("Size :", size)

    v, b = Pop(queue)
    if b {
        fmt.Println("Pop : ", v)
    }
    fmt.Println("Size :", size)
    v, b = Pop(queue)
    if b {
        fmt.Println("Pop : ", v)
    }
    fmt.Println("Size :", size)
    traverse(queue)
}

$ go run foo.go
Size: 1
10 -> 
Pop: 10
Size :  0
4 -> 3 -> 2 -> 1 -> 0 -> 
Size : 5
Pop :  0
Size : 4
Pop :  1
Size : 3
4 -> 3 -> 2 ->

스택 만들기

package main

import "fmt"

type Node struct {
    Value int
    Next *Node
}

var size = 0
var stack = new(Node)

func Push(v int) bool {
    if stack == nil {
        stack = &Node{v, nil}
        size = 1
        return true
    }
    temp := &Node{v, nil}
    temp.Next = stack
    stack = temp
    size++
    return true
}

func Pop(t *Node) (int, bool) {
    if size == 0 {
        return 0, false
    }
    if size == 1 {
        size = 0
        stack = nil
        return t.Value, true
    }
    stack = stack.Next
    size--
    return t.Value, true
}

func traverse(t *Node) {
    if size == 0 {
        fmt.Println("Empty stack")
        return
    }
    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }
    fmt.Println()
}

func main() {
    stack = nil 
    v, b := Pop(stack) 
    if b {
        fmt.Print(v, " ") 
    } else {
        fmt.Println("Pop() failed!")
    }
    Push(100) 
    traverse(stack) 
    Push(200) 
    traverse(stack) 

    for i := 0; i < 10; i++ {
        Push(i) 
    }
    for i := 0; i < 15; i++ {
        v, b := Pop(stack) 
        if b {
            fmt.Print(v, " ")
        } else {
            break
        }
    }
    fmt.Println() 
    traverse(stack) 
}

$ go run foo.go
Pop() failed!
100 -> 
200 -> 100 -> 
9 8 7 6 5 4 3 2 1 0 200 100 
Empty stack

Container 패키지

컨테이너 페키지는 세 가지 자료 구조를 제공한다. (heap, list, ring)

링은 순환 리스트이며, 링의 마지막 원소는 첫번째 원소를 가리킨다.

Container/heap

힙은 일종의 트리로, 각 노드의 값은 그 노드의 아래에 있는 원소들 중에서 가장 작은 값으로 구성한다. 여기서 주목할 부분은, 최소값이라 표현하지 않고 가장 작은 값이라 표현한 점이다. 힙은 숫자가 아닌 다른 종류의 값도 표현한다는 것을 강조하기 위해서다.

container/heap 패키지를 사용하려면 container/heap.Interface를 구현해야한다.

type Interface interface {
    sort.Interface 
    Push(x interface{})
    Pop() interface{}
}

package main

import (
    "container/heap"
    "fmt"
)

type heapFloat32 []float32

func (n *heapFloat32) Pop() interface{} {
    old := *n
    x := old[len(old) - 1]
    new := old[0 : len(old) - 1]
    *n = new
    return x
}

func (n *heapFloat32) Push(x interface{}) {
    *n = append(*n, x.(float32))
}

func (n heapFloat32) Len() int {
    return len(n)
}

func (n heapFloat32) Less(a,b int) bool {
    return n[a] < n[b]
}

func (n heapFloat32) Swap(a, b int) {
    n[a], n[b] = n[b], n[a]
}

func main() {
    myHeap := &heapFloat32{1.2, 2.1, 3.1, -100.1}
    heap.Init(myHeap)
    size := len(*myHeap)
    fmt.Printf("Heap Size : %d\n", size)
    fmt.Printf("%v\n", myHeap)

    myHeap.Push(float32(-100.2))
    myHeap.Push(float32(0.2))
    fmt.Printf("Heap Size : %d\n", size)
    fmt.Printf("%v\n", myHeap)
    heap.Init(myHeap)
    fmt.Printf("%v\n", myHeap)
}

$ go run foo.go
Heap Size : 4
&[-100.1 1.2 3.1 2.1]
Heap Size : 4
&[-100.1 1.2 3.1 2.1 -100.2 0.2]
&[-100.2 -100.1 0.2 2.1 1.2 3.1]

container/list 사용법

package main

import (
    "container/list"
    "fmt"
    "strconv"
)

func printList(l *list.List) {
    for t := l.Back(); t != nil; t = t.Prev() {
        fmt.Print(t.Value, " ")
    }
    fmt.Println()

    for t := l.Front(); t != nil; t = t.Next() {
        fmt.Print(t.Value, " ")
    }

    fmt.Println()
}

func main() {

    values := list.New()

    e1 := values.PushBack("One")
    e2 := values.PushBack("Two")
    values.PushFront("Three")
    values.InsertBefore("Four", e1)
    values.InsertAfter("Five", e2)
    values.Remove(e2)
    values.Remove(e2)
    values.InsertAfter("FiveFive", e2)
    values.PushBackList(values)

    printList(values)

    values.Init()
    fmt.Printf("After Init(): %v\n", values)

    for i := 0; i < 20; i++ {
        values.PushFront(strconv.Itoa(i))
    }

    printList(values)
}

$ go run foo.go
Five One Four Three Five One Four Three 
Three Four One Five Three Four One Five 
After Init(): &{{0xc000056180 0xc000056180 <nil> <nil>} 0}
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

list.PushBack() 함수는 연결 리스트의 마지막에 오브젝트를 추가하는 반면 list.PushFront() 함수는 리스트의 첫 부분에 오브젝트를 추가한다. 두 함수는 리스트에 추가한 값을 리턴한다.

container/ring 사용법

package main

import (
    "container/ring"
    "fmt"
)

var size int = 10 

func main() {
    myRing := ring.New(size + 1) 
    fmt.Println("Empty ring :", *myRing)

    for i := 0; i < myRing.Len()-1; i++ {
        myRing.Value = i 
        myRing = myRing.Next()
    }
    myRing.Value = 2 

    sum := 0 
    myRing.Do(func(x interface{}) {
        t := x.(int) 
        sum += t 
    })
    fmt.Println("Sum:", sum) 

    for i := 0; i < myRing.Len()+2; i++ {
        myRing = myRing.Next()
        fmt.Print(myRing.Value, " ") 
    }
    fmt.Println()
}

ring .Do 함수는 링의 각 원소에 대해 함수를 호출할 때 사용한다. 이 하수가 링을 수정하면 ring.Do()의 동작을 알 수 없게 된다. x.(int)라고 적은 부분을 타입 어써션이라고 부른다.

$ go run foo.go
Empty ring : {0xc0000a6040 0xc0000a6160 <nil>}
Sum: 47
0 1 2 3 4 5 6 7 8 9 2 0 1

난수 생성하기

난수를 생성하는 방법은 실용적일 뿐만 아니라 전산학의 한 연구 분야이다. 난수를 지정하려면 씨드를 지정해야 한다. 씨드란 전반적인 난수 생성 과정을 초기화하는데 사용되는 굉장히 중요한 값이다. 그 이유는 같은 씨드 값으로 시작하면 난수가 생성되는 결과도 같아지기 때문이다. 이렇게 누구나 같은 값들을 생성할 수 있다면 나수라 부를 수 없다.

package main

import (
    "fmt"
    "math/rand"
    "os"
    "strconv"
    "time"
)

func random(min, max int) int {
    return rand.Intn(max-min) + min
}

func main() {
    MIN := 0
    MAX := 100
    TOTAL := 100
    SEED := time.Now().Unix()

    arguments := os.Args
    switch len(arguments) {
    case 2:
        fmt.Println("Usage: ./randomNumbers MIN MAX TOTAL SEED")
        MIN, _ = strconv.Atoi(arguments[1])
        MAX = MIN + 100
    case 3:
        fmt.Println("Usage: ./randomNumbers MIN MAX TOTAL SEED")
        MIN, _ = strconv.Atoi(arguments[1])
        MAX, _ = strconv.Atoi(arguments[2])
    case 4:
        fmt.Println("Usage: ./randomNumbers MIN MAX TOTAL SEED")
        MIN, _ = strconv.Atoi(arguments[1])
        MAX, _ = strconv.Atoi(arguments[2])
        TOTAL, _ = strconv.Atoi(arguments[3])
    case 5:
        MIN, _ = strconv.Atoi(arguments[1])
        MAX, _ = strconv.Atoi(arguments[2])
        TOTAL, _ = strconv.Atoi(arguments[3])
        SEED, _ = strconv.ParseInt(arguments[4], 10, 64)
    default:
        fmt.Println("Using default values!")
    }

    rand.Seed(SEED)
    for i := 0; i < TOTAL; i++ {
        myrand := random(MIN, MAX)
        fmt.Print(myrand)
        fmt.Print(" ")
    }
    fmt.Println()
}

랜덤 스트링 생성하기

package main

import (
    "fmt"
    "math/rand"
    "os"
    "strconv"
    "time"
)

func random(min, max int) int {
    return rand.Intn(max-min) + min
}

func main() {
    MIN := 0
    MAX := 94
    SEED := time.Now().Unix()
    var LENGTH int64 = 8

    arguments := os.Args

    switch len(arguments) {
    case 2:
        LENGTH, _ = strconv.ParseInt(os.Args[1], 10, 64)
    default:
        fmt.Println("Using default values!")
    }
    rand.Seed(SEED)

    startChar := "!"
    var i int64 = 1
    for {
        myRand := random(MIN, MAX)
        newChar := string(startChar[0] + byte(myRand))
        fmt.Print(newChar)
        if i == LENGTH {
            break
        }
        i++
    }
    fmt.Println()
}

startChar 변수는 아스키 문자를 담는다. 이 값은 십진수로 33이다. 94 보다 작은 난수 생성시 가장 큰 아스키 값은 93+33인 126이다.

$ go run foo.go 20
cjFq$;)a:I4"57$0+G$^