이진 검색 문제가 있는 Golang의 동시성

문제

Go로 문제를 해결하는 것은 정말 재미있고 보람 있는 경험이 될 수 있습니다. 이번 포스팅에서는 "중간"리트코드 챌린지 "Find First and Last Position of Element in Sorted Array"에 대해 알아보겠습니다.

문제는 매우 간단합니다. 정렬된 배열이므로 이진 검색을 사용할 수 있습니다. 그러나 배열은 감소하지 않습니다. 즉, 요소가 반복될 수 있습니다. 대상 요소가 배열에 있는 위치의 시작 및 끝 인덱스가 있는 크기 2 배열을 반환하는 작업이 주어졌습니다.

프롬프트는 다음과 같습니다.

솔루션 단계

더 이상 읽기 전에 자신을 위한 정신적 해결책을 생각해 보십시오.

사소한 선형 솔루션을 무시하고 이진 검색 솔루션에 초점을 맞출 것입니다. 단계를 생각해 봅시다.

target에 대한 이진 검색

어레이를 "하위"및 "상위"로 분할

둘 다에 대한 이진 검색, 별도로

두 분할이 더 이상 대상을 찾지 못할 때까지 반복합니다

.

매우 간단합니다. 저는 Go로 문제를 해결하는 데 많은 재미를 느꼈습니다. 대부분의 구문은 다른 언어와 유사합니다. Go의 가장 중요한 기능 중 하나는 동시성 및 멀티스레딩을 얼마나 간단하게 만드는가입니다. 스레드 간에 데이터를 동기화하기 위해 네이티브Channels와 함께 Goroutine이라는 데이터 유형을 사용합니다. 다른 언어에서는 async / await로 생각하십시오.

암호

런타임이 O(log n)인 간단한 이진 검색 방법을 만들 것입니다.

// BinarySearch method
func findTarget(nums []int, target int) int {
    low, high := 0, len(nums) - 1

    for low <= high {
        mid := (high + low) / 2

        if nums[mid] == target {
            return mid
        }

        if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return -1
}

우리는 이 메서드를 몇 번 호출할 것이지만 배열의 계속 감소하는 슬라이스에서는 동일한 메모리 공간으로 두 번 호출하지 않을 것입니다.

이제 초기 대상을 쉽게 찾을 수 있습니다.

func searchRange(nums []int, target int) []int {
    // Initial Search
    high := findTarget(nums, target)

    // Didn't find it, return early
    if high == -1 {
        return []int{-1, -1}
    }
    // TODO: finish function
}

여기서 우리는 target가 전혀 존재하지 않는 초기 반환을 가지고 있습니다. 하지만 이제 우리가 그것을 찾으면 어떻게 될까요? 배열을 위아래로 검색해야 합니다. 물론 이 작업을 선형적으로 수행할 수 있지만 최악의 경우를 생각해 보십시오. 1,000만 개의 요소 배열이 있다면 모두target 입니다. 센터에서 시작했다면 이제 어레이 위아래로 5백만 개의 요소를 선형적으로 크롤링해야 합니다. 별로!

그 때문에 우리는 이진 검색을 고수할 것입니다. Golang을 사용하면 slice 데이터 유형을 잘라낼 수 있습니다. 동시성을 사용하지 않고 나머지 방법은 다음과 같습니다.

func searchRange(nums []int, target int) []int {
// ...

// Found target, lets search left and right
    low := high

    // Search lower half of array
    for {
        temp := findTarget(nums[:low], target)
        if temp == -1 {
            break
        }
        low = temp
    }

    // Search upper half of array
    for {        
        temp := findTarget(nums[high + 1:], target)
        if temp == -1 {
            break
        }
        // temp is reindexed at 0 - account for that
        high += temp + 1
    }

    return []int{low, high}
}

매우 간단합니다. 각 슬라이스에서 요소를 더 이상 찾을 수 없을 때까지 이진 검색입니다. 엄청난! 이것은 Leetcode에 전달되며 우리는 할 수 있습니다. 하지만 이것을 어떻게 조금 더 좋게 만들 수 있을까요? 이 코드의 주요 병목 현상은 "하위"검색이 완료될 때까지 "상위"검색이 완전히 차단된다는 사실입니다.

여기에 기회가 있습니다. 두 개의 for 루프는 완전히 분리된 메모리 주소에서 작동합니다. Goroutines 및 a Channel 로 무엇을 할 수 있는지 봅시다. 여기에 동시성이 추가된 완성된 전체 함수가 있습니다.

func searchRange(nums []int, target int) []int {
    // Initial Search
    high := findTarget(nums, target)

    // Didn't find it, return early
    if high == -1 {
        return []int{-1, -1}
    }

    // Hold our data from the threads
    bounds := make(chan int, 2)

    // Search lower half of array, in its own thread (goroutine)
    go func(low int) {
        for {
            temp := findTarget(nums[:low], target)
            if temp == -1 {
                break
            }
            low = temp
        } 
        // Shovel the lower-bound into the Channel
        bounds<-low
    }(high)

    // Search upper half of array, in its own thread (goroutine)
    go func(high int) {
        for {
            temp := findTarget(nums[high + 1:], target)
            if temp == -1 {
                break
            }
            high += temp + 1
        }
        // Shovel the upper-bound into the Channel
        bounds<-high
    }(high)

    newLow := <-bounds
    newHigh := <-bounds

    // No garauntee which one finishes first, so order them
    if newLow > newHigh {
        newLow, newHigh = newHigh, newLow
    }

    return []int{newLow, newHigh}
}

이제 익명 함수를 만들고 즉시 호출하지만 go 키워드를 사용하여 고루틴을 실행합니다. bounds 채널의 범위를 사용하여 데이터를 안팎으로 삽질할 수 있습니다. 채널에서 데이터를 가져올 때( <-bounds ) Go는 실제로 데이터가 있을 때까지 차단합니다.

이는 "하위"및 "상위"슬라이스가 동시에 처리됨을 의미합니다! 축하합니다. 스레드로부터 안전한 동시성💪🧵을 사용하여 Leetcode 챌린지를 해결했습니다!

여기 후속 조치

또한 "lower"및 "upper"에 대한 함수를 자체 메소드로 끌어와서 이 코드를 약간 정리할 수 있습니다. 이렇게 하면 기본searchRange 메서드가 좀 더 깔끔해집니다. 그러나 단순함을 위해 나는 그것들을 그대로 두었습니다.