アルゴリズムとデータ構造 - 配列

アルゴリズムとデータ構造

概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

配列

  • データを1列に並べたもの
  • データへのアクセスは容易だが、追加や削除には時間がかかる
  • 配列のデータはメモリの連続した領域に順番に格納される
    • 固定長のメモリを確保する
      • 宣言時に確保(静的確保)
      • 実行時に確保(動的確保)

計算時間

配列に格納されているデータ数をnとする。

データへのアクセス

  • O(1)
    • メモリアドレスが添字を使って計算することができるため、データに直接アクセスすることができる。(ランダムアクセス)

データの追加

  • O(n)
    • 追加する箇所より後ろのデータをすべて1つずつずらす必要がある。

データの削除

  • データの追加と同様

実装

package main

import (
    "errors"
    "fmt"
)

// A Array is array implemented by slice.
type Array struct {
    data   []string
    length int // Keep a array memory size
}

// Insert is insert a data to array.
func (a *Array) insert(index int, value string) error {
    if a.length == int(cap(a.data)) {
        return errors.New("a array is full")
    }

    if index != a.length && index >= a.length {
        return errors.New("out of index range")
    }

    // shift data
    for i := a.length; i > index; i-- {
        a.data[i] = a.data[i-1]
    }

    // insert a value to target index
    a.data[index] = value

    // update the length
    a.length++

    return nil
}

// delete is delete a target data by index.
func (a *Array) delete(index int) (string, error) {
    if index >= a.length {
        return "", errors.New("out of index range")
    }

    // target value for deleting
    v := a.data[index]

    for i := index; i < a.length-1; i++ {
        a.data[i] = a.data[i+1]
    }

    // unset
    a.data[a.length-1] = ""

    // update the length
    a.length--

    return v, nil
}

// get is get a target data by index.
func (a *Array) get(index int) (string, error) {
    if index >= a.length {
        return "", errors.New("out of index range")
    }

    // random access
    return a.data[index], nil
}

func main() {
    a := &Array{
        data:   make([]string, 10, 10),
        length: 0,
    }

    cases := []struct {
        index int
        value string
    }{
        {
            index: 0,
            value: "foo",
        },
        {
            index: 1,
            value: "bar",
        },
        {
            index: 2,
            value: "foobar",
        },
    }

    for _, c := range cases {
        if err := a.insert(c.index, c.value); err != nil {
            fmt.Printf("index: %v value: %v is error. %v\n", c.index, c.value, err)
        }
    }

    if s, err := a.delete(2); err != nil {
        fmt.Printf("index: 0 is error. %v\n", err)
    } else {
        fmt.Printf("%v is deleted.", s)
    }

    if r, err := a.get(0); err != nil {
        fmt.Printf("index: 0 is error. %v", err)
    } else {
        fmt.Printf("%v", r)
    }
}
  • 構造体Arrayには配列のデータ構造を定義する。
    • golangには配列があるが、ここではスライスを使って配列のデータ構造を実装する。
    • 配列は固定長なので長さ(length)を用意しておく。
  • insert
    • 条件分岐
      • 配列が満杯のとき(=data数がlengthと同じとき)
      • 配列の範囲外のアクセスが発生するとき
    • データをずらす
      • 配列の末尾から任意のindexまでを対象にループでデータをずらす
      • ずらし終わった後に配列にデータを追加し、lengthを更新する
  • delete
    • 考え方としてinsertの逆に近い
    • 条件分岐
      • 配列の範囲外のアクセスだけ考慮すれば良い
      • データをへらすので配列が満杯かどうかは条件外
    • データをずらす
      • indexで指定したデータをunsetする
      • 末尾からではなく、任意のindexから末尾に向かってループでデータをずらす
      • ずらし終わったら後はlengthの更新をする
  • get
    • 配列の範囲外へのアクセスだけ考慮してランダムアクセス(添字でデータを参照)
  • ノート
    Image from iOS

参考

関連


関連書籍