線形探索

# 探索とは
- レコード（`Key`と`Value`の組み合わせ）の中から，与えられた`Key`に対応するレコードを選び出すこと

# 線形探索
- 横に並べられたレコードを一つづつ逐次的に「舐めていく」

## 配列による列を線形探索
- 失敗の場合は（結果として全部舐めきるので）$O(n)$，成功の場合は平均して$O(n/2)$なので，何れにしても$O(n)$

```go
package main

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

const LENGTH = 50

type Element struct {
	Key int
	Value int
}

type Array struct {
	arr [LENGTH]Element
}

func (a *Array) Search(target int) (bool, int) {
	pos := 0
	for pos < len(a.arr) && target != a.arr[pos].Key {
		pos += 1
	}
	found := pos < len(a.arr)
	return found, pos
}

func main() {
	rand.Seed(time.Now().UnixNano())
	keys := make([]int, LENGTH)
	for i := range keys {
		keys[i] = rand.Intn(LENGTH*2)
	}
	values := make([]int, LENGTH)
	for i := range values {
		values[i] = rand.Intn(LENGTH*2)
	}
	array := Array{}
	for i := 0; i < LENGTH; i++ {
		ele := Element{Key: keys[i], Value: values[i]}
		array.arr[i] = ele
	}

	if found, val := array.Search(12); found {
		fmt.Println("Found! = <Key: 12, Value: ", val, ">")
	} else {
		fmt.Println("Not Found!")
	}
}
```

# 番兵
- レコードの列の一番最後に，探索対象の`Key`を持つレコードをあらかじめ配置しておくことで，実行される命令の個数を減らす
- 抜本的な高速化手法というよりかは，シビアに実行速度が求められる状況でよく用いられる手法程度という認識が正しい．

> #### 条件判定の数を削減するために置くダミーのデータ
> ループの終了条件が複数ある場合に、**条件判定の数を削減するために**置くダミーのデータ。この意味での番兵を使った最適化技法を番兵法と呼ぶ。
> 番兵法はループ中の条件判断を削減できるため、実行時間の削減が非常に重要な場合によく検討される。1 回の条件判断にかかる時間は短くても、ループで繰り返す場合には大きな差となる場合がある。しかしソース上で終了条件がわかりにくくなる可能性も高く、現代の高速化したコンピュータにおいては必ずしも歓迎される技法ではない。

```go
package main

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

const LENGTH = 50

type Element struct {
	Key int
	Value int
}

type Array struct {
	arr [LENGTH+1]Element
}

func (a *Array) Search(target int) (bool, int) {
	a.arr[LENGTH].Key = target // Sentinel
	pos := 0
	for /* pos < len(a.arr) && */ target != a.arr[pos].Key {
		pos += 1
	}
	found := pos < len(a.arr)-1
	return found, pos
}

func main() {
	rand.Seed(time.Now().UnixNano())
	keys := make([]int, LENGTH)
	for i := range keys {
		keys[i] = rand.Intn(LENGTH*2)
	}
	values := make([]int, LENGTH)
	for i := range values {
		values[i] = rand.Intn(LENGTH*2)
	}
	array := Array{}
	for i := 0; i < LENGTH; i++ {
		ele := Element{Key: keys[i], Value: values[i]}
		array.arr[i] = ele
	}
	
	if found, pos := array.Search(12); found {
		fmt.Println("Found at", pos, " = <Key: 12, Value: ", array.arr[pos].Value, ">")
	} else {
		fmt.Println("Not Found!")
	}
}
```

## リストによる列を線形探索
- 番兵としてダミーの`Cell`を入れておく

```go
package main

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

const LENGTH = 50

type Cell struct {
	key int
	val int
	next *Cell
}

type LinkedList struct {
	head *Cell
}

func (l *LinkedList) Search(key int) (bool, *Cell) {
	sentinel := &Cell{key: key} // Here!
	last := l.head
	if last == nil {
		fmt.Println("ERROR: no records in list")
		return false, nil
	}
	for last.next != nil {
		last = last.next
	}
	last.next = sentinel
	previous := l.head
	p := l.head.next
	for key != p.key {
		previous = p
		p = p.next
	}

	return p != sentinel, previous
}

func (l *LinkedList) Append(key, val int) {
	cell := NewCell(key, val)
	last := l.head
	if last == nil {
		l.head = cell
		return
	}
	for last.next != nil {
		last = last.next
	}
	last.next = cell
}

func (l *LinkedList) Print() {
	cell := l.head
	for cell != nil {
		fmt.Printf("<Key: %d, Value: %d>\n", cell.key, cell.val)
		cell = cell.next
	}
}

func NewCell(key, val int) *Cell {
	return &Cell{key: key, val: val, next: nil}
}

func NewLinkedList() *LinkedList {
	return &LinkedList{head: nil}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	keys := make([]int, LENGTH)
	for i := range keys {
		keys[i] = rand.Intn(LENGTH*2)
	}
	values := make([]int, LENGTH)
	for i := range values {
		values[i] = rand.Intn(LENGTH*2)
	}
	l := NewLinkedList()
	for i := 0; i < LENGTH; i++ {
		l.Append(keys[i], values[i])
	}
	
	if found, prev := l.Search(12); found {
		fmt.Println("Found: <Key: ", prev.next.key, ", Value: ", prev.next.val, ">")
	} else {
		fmt.Println("Not Found!")
	}

}
```

# 自己再構成リスト
- データアクセスには時間的な局所性（つい最近アクセスしたデータは，近しい将来に再びアクセスする蓋然性が高い）ので，探索されたレコードをレコードの先頭に配置しておくことで再探索の際のコストを削減することができそう．
    - データの位置を変えやすいのは ~~配列ではなく~~ 線形リストの方なので，自己再構成**リスト**

```go
func (l *LinkedList) Search(key int) (bool, *Cell) {
	sentinel := &Cell{key: key}
	last := l.head
	if last == nil {
		fmt.Println("ERROR: no records in list")
		return false, nil
	}
	for last.next != nil {
		last = last.next
	}
	last.next = sentinel
	previous := l.head
	p := l.head.next
	for key != p.key {
		previous = p
		p = p.next
	}
	previous.next = nil
	found := p != sentinel
	if found {
		previous.next = p.next
		p.next = l.head.next
		l.head.next = p
	}
	return found, previous
}
```