Мы все знаем, что бинарный поиск — один из самых быстрых способов поиска цели в отсортированном списке. И есть два способа реализовать это либо с помощью итеративного подхода, либо с помощью рекурсивного подхода. В этой истории мы рассмотрим рекурсивный подход, и одна из проблем использования рекурсивной функции заключается в том, что она требует больше времени ( O (2 ^ N) ), поскольку каждый вызов функции вызывает себя дважды, если только он не был рекурсирован n раз.
Тогда почему мы не можем сделать его немного быстрее, просто разбив операторы return в рекурсивных вызовах > 🤔.
Ну вот…!!
реализация бинарного поиска с использованием подпрограмм go
func implementBinarySearchUsingRoutines(arr []int, target int) {
result := make(chan int)
go binarySearchUsingGoRoutines(arr, target, 0, len(arr)-1, result)
// it will block the code until search function sends some response
index := <-result
if index != -1 {
fmt.Println(target, " target found at", index)
} else {
fmt.Println(target, " target not found")
}
}
func binarySearchUsingGoRoutines(arr []int, target, low, high int, result chan int) {
if low > high {
result <- -1
return
}
mid := (low + high) / 2
if arr[mid] == target {
result <- mid
return
}
if arr[mid] > target {
go binarySearchUsingGoRoutines(arr, target, low, mid-1, result)
} else {
go binarySearchUsingGoRoutines(arr, target, mid+1, high, result)
}
}
вместо того, чтобы возвращать функцию, мы можем запустить ту же функцию в отдельной процедуре go, чтобы повысить ее производительность 🙂.
Теперь мы сравним временную и пространственную сложность рекурсивной и рутинной реализации.
package main
import (
"fmt"
"math/rand"
"runtime"
"time"
)
func main() {
arr, target := generateArrayAndTarget()
// set max usage cores as 1
runtime.GOMAXPROCS(1)
start := time.Now()
fmt.Println("starting implementation of Binary Search recursively ")
implementBinarySearchRecursively(arr, target)
printMemUsage()
fmt.Println("time taken in nano seconds:-",time.Since(start).Nanoseconds())
// run garbage collector to free up unused memory
runtime.GC()
start = time.Now()
fmt.Println("starting implementation of Binary Search Using Routines ")
implementBinarySearchUsingRoutines(arr, target)
printMemUsage()
fmt.Println("time taken in nano seconds:-",time.Since(start).Nanoseconds())
}
func implementBinarySearchRecursively(arr []int, target int) {
index := binarySearch(arr, target, 0, len(arr)-1)
if index != -1 {
fmt.Println(target, " target found at", index)
} else {
fmt.Println(target, " target not found")
}
}
func implementBinarySearchUsingRoutines(arr []int, target int) {
result := make(chan int)
go binarySearchUsingGoRoutines(arr, target, 0, len(arr)-1, result)
// it will block the code until search function sends some response
index := <-result
if index != -1 {
fmt.Println(target, " target found at", index)
} else {
fmt.Println(target, " target not found")
}
}
func binarySearchUsingGoRoutines(arr []int, target, low, high int, result chan int) {
if low > high {
result <- -1
return
}
mid := (low + high) / 2
if arr[mid] == target {
result <- mid
return
}
if arr[mid] > target {
go binarySearchUsingGoRoutines(arr, target, low, mid-1, result)
} else {
go binarySearchUsingGoRoutines(arr, target, mid+1, high, result)
}
}
func binarySearch(arr []int, target, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if arr[mid] == target {
return mid
}
if arr[mid] > target {
return binarySearch(arr, target, low, mid-1)
} else {
return binarySearch(arr, target, mid+1, high)
}
}
func generateArrayAndTarget() ([]int, int) {
arr := make([]int, 999999999)
for i := 1; i < len(arr); i++ {
arr[i-1] = i
}
return arr, arr[rand.Intn(len(arr)-1)]
}
func printMemUsage() {
var stats runtime.MemStats
runtime.ReadMemStats(&stats)
fmt.Printf("Alloc = %v MiB", stats.Alloc/1024/1024)
fmt.Printf("\tTotalAlloc = %v MiB", stats.TotalAlloc/1024/1024)
fmt.Printf("\tSys = %v MiB", stats.Sys/1024/1024)
fmt.Printf("\tNumGC = %v", stats.NumGC)
fmt.Printf("\t no of go routines = %v\n", runtime.NumGoroutine())
}
output:-
iteration-1:-
starting implementation of Binary Search recursively
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 1 no of go routines = 1
time taken in nano seconds:-12889400
starting implementation of Binary Search Using Routines
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 2 no of go routines = 1
time taken in nano seconds:-8522300
--------------------------------
iteration-2:-
starting implementation of Binary Search recursively
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 1 no of go routines = 1
time taken in nano seconds:-7123500
starting implementation of Binary Search Using Routines
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 2 no of go routines = 1
time taken in nano seconds:-1851600
--------------------------------
iteration-3:-
starting implementation of Binary Search recursively
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 1 no of go routines = 1
time taken in nano seconds:-10586800
starting implementation of Binary Search Using Routines
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 2 no of go routines = 1
time taken in nano seconds:-4202600
--------------------------------
iteration-4:-
starting implementation of Binary Search recursively
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 1 no of go routines = 1
time taken in nano seconds:-13572600
starting implementation of Binary Search Using Routines
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 2 no of go routines = 1
time taken in nano seconds:-8423100
--------------------------------
iteration-5:-
starting implementation of Binary Search recursively
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 1 no of go routines = 1
time taken in nano seconds:-11283800
starting implementation of Binary Search Using Routines
298498084 target found at 298498083
Alloc = 7629 MiB TotalAlloc = 7629 MiB Sys = 7886 MiB NumGC = 2 no of go routines = 1
time taken in nano seconds:- 7131700
Из вывода видно, что обе реализации занимают одинаковый объем памяти, но затраченное время отличается. Также очевидно, что использование подпрограмм go может улучшить выполнение рекурсивных функций.
Тестирование BenchMark с временем тестирования 10 секунд
note:- target key is generated randomly may not be the same for both the functions go test -bench=. -benchtime=10s iternation -1:- goos: windows goarch: amd64 pkg: medium/binarysearch/usingroutines cpu: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz BenchmarkBinarySearchUsingGoRoutines/input_size_9-8 8009953 2398 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99-8 1823480 5705 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999-8 842208 14788 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_9999-8 182142 64211 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99999-8 25999 466619 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999999-8 3604 3625492 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_9999999-8 591 19323843 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99999999-8 58 180493174 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999999999-8 1 23644980900 ns/op PASS ok medium/binarysearch/usingroutines 147.730s iternation -2:- goos: windows goarch: amd64 pkg: medium/binarysearch/usingroutines cpu: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz BenchmarkBinarySearchUsingGoRoutines/input_size_9-8 9758373 1786 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99-8 2235060 5464 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999-8 869326 14623 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_9999-8 180708 66059 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99999-8 25923 464167 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999999-8 3112 3486702 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_9999999-8 592 19711070 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_99999999-8 57 184378581 ns/op BenchmarkBinarySearchUsingGoRoutines/input_size_999999999-8 1 23065051500 ns/op PASS ok medium/binarysearch/usingroutines 143.025s ------------------------------------------------- go test -bench=. -benchtime=10s iternation -1:- goos: windows goarch: amd64 pkg: medium/binarysearch/recursive cpu: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz BenchmarkBinarySearch/input_size_9-8 100000000 147.5 ns/op BenchmarkBinarySearch/input_size_99-8 15203101 844.0 ns/op BenchmarkBinarySearch/input_size_999-8 2299185 5452 ns/op BenchmarkBinarySearch/input_size_9999-8 255415 49134 ns/op BenchmarkBinarySearch/input_size_99999-8 29052 406890 ns/op BenchmarkBinarySearch/input_size_999999-8 3422 3558830 ns/op BenchmarkBinarySearch/input_size_9999999-8 652 19478196 ns/op BenchmarkBinarySearch/input_size_99999999-8 66 177987880 ns/op BenchmarkBinarySearch/input_size_999999999-8 1 24534260400 ns/op PASS ok medium/binarysearch/recursive 154.862s iternation -2:- goos: windows goarch: amd64 pkg: medium/binarysearch/recursive cpu: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz BenchmarkBinarySearch/input_size_9-8 112362855 208.8 ns/op BenchmarkBinarySearch/input_size_99-8 13626289 847.0 ns/op BenchmarkBinarySearch/input_size_999-8 2133458 5720 ns/op BenchmarkBinarySearch/input_size_9999-8 245186 48752 ns/op BenchmarkBinarySearch/input_size_99999-8 30397 400923 ns/op BenchmarkBinarySearch/input_size_999999-8 3423 3333734 ns/op BenchmarkBinarySearch/input_size_9999999-8 578 20049595 ns/op BenchmarkBinarySearch/input_size_99999999-8 58 184094891 ns/op BenchmarkBinarySearch/input_size_999999999-8 1 24155393800 ns/op PASS ok medium/binarysearch/recursive 156.357s
