アルゴリズム ビジュアル大辞典のアルゴリズムをPython, Goで実装する [線形探索、二分探索]

こちらの続きです。

mattsun-plapla.hatenablog.com

やること

こちらの書籍に記載されるアルゴリズムをPython, Goで実装してみます。
(Goはまだまだホントに初学者です)

アルゴリズム ビジュアル大事典

線形探索

キーの値が見つかるまで配列の最初から順に見ていく。最悪の場合は配列内の最後の要素まで見ていく。
計算量＝O(N)となり、配列内の要素分だけ計算量も増える。

二分探索

配列の中央に分割するステップを繰り返しながらキーの値を見つける。
最初の中央値よりキーの値が大きければ、中央値以上、そうでなければ中央値以下の範囲を見ていく。
計算量=O(logN)となり、線形探索と比べ劇的に計算量が減る。
計算ステップはlog2Nだが定数は無視する。

実装例

Pythonでは簡単に連番となる配列を作ることができるけど、Goでは正直楽な作り方がわからなかったので、適当な配列としています(涙)。(ループで追加していけばできるんだろうけど面倒でした)
したがって、Pythonでは1000〜1億個もの配列を用意して線形探索・二分探索のそれぞれの計算速度の違いも計測しました。
Goではしていません笑。

import time

def LinearSearch(array, key):
    for i in range(len(array)):
        if array[i] == key:
            return i, array[i]
    return None, None


def BinarySearch(array, key):
    left = 0
    right = len(array)
    while left < right:
        mid = round((left + right) / 2)
        if array[mid] == key:
            return mid, array[mid]
        elif array[mid] < key:
            left = mid + 1
        else:
            right = mid
    return None, None


if __name__ == '__main__':

    for i in [1000, 10000, 100000, 1000000, 10000000, 100000000]:
        r = list(range(1, i, 1))
        print(f"array len: {i}")
        start = time.perf_counter()
        idx, val = LinearSearch(r, 671)
        print("index:{0} value: {1}".format(idx2, val2))
        print("Linear Seach")
        end = time.perf_counter()
        print(start - end, "\n")

        start2 = time.perf_counter()
        idx2, val2 = BinarySearch(r, 671)
        print("Binary Seach")
        print("index:{0} value: {1}".format(idx2, val2))
        end2 = time.perf_counter()
        print(start2 - end2, "\n")

"""
array len: 1000
index:670 value: 671
Linear Seach
-6.370099999999934e-05 

Binary Seach
index:670 value: 671
-3.961000000000242e-05 

array len: 10000
index:670 value: 671
Linear Seach
-5.716499999999791e-05 

Binary Seach
index:670 value: 671
-1.4183000000000945e-05 

array len: 100000
index:670 value: 671
Linear Seach
-6.525899999999807e-05 

Binary Seach
index:670 value: 671
-1.769600000000454e-05 

array len: 1000000
index:670 value: 671
Linear Seach
-6.603499999999207e-05 

Binary Seach
index:670 value: 671
-2.3250000000002435e-05 

array len: 10000000
index:670 value: 671
Linear Seach
-5.8237000000016526e-05 

Binary Seach
index:670 value: 671
-2.2823999999976863e-05 

array len: 100000000
index:670 value: 671
Linear Seach
-5.810900000025043e-05 

Binary Seach
index:670 value: 671
-2.6684000000276598e-05
"""

package main

import (
	"fmt"
)

func LinearSearch(array []int, key int) (int, int) {
	for i := 0; i < len(array); i++ {
		if array[i] == key {
			return i, array[i]
		}
	}
	return 0, 0
}

func BinarySearch(array []int, key int) (int, int) {
	left := 0
	right := len(array)
	for left < right {
		mid := (left + right) / 2
		if array[mid] == key {
			return mid, array[mid]
		} else if array[mid] < key {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return 0, 0
}

func main() {
	A := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println(LinearSearch(A, 6))
	fmt.Println(BinarySearch(A, 6))
}

参考

Binary Search in Go (Golang) - golangprograms.com