정수 슬라이스를 사용하여 Go에서 하위 집합 관계를 효율적으로 결정하려면 어떻게 해야 합니까?

Go에서 정수 슬라이스로 하위 집합 관계를 효율적으로 확인

한 슬라이스가 다른 슬라이스의 하위 집합인지 확인하는 것은 일반적인 계산 작업입니다. Go에는 이를 달성하기 위한 다양한 접근 방식이 있으며 다양한 수준의 효율성을 제공합니다.

한 가지 간단한 방법은 두 슬라이스의 요소를 반복하여 작은 슬라이스의 각 요소를 더 큰 슬라이스의 요소와 비교하는 것입니다. . 그러나 이 접근 방식은 검사의 반복 특성으로 인해 대형 슬라이스의 경우 계산 비용이 많이 들 수 있습니다.

더 높은 효율성을 달성하기 위해 맵 데이터 구조를 활용하는 대체 접근 방식이 있습니다. 이 접근 방식은 작은 슬라이스의 요소를 큰 슬라이스에서 빼서 요소가 남아 있는지 확인하는 차집합 속성을 활용합니다.

Go에서 이 접근 방식을 구현하는 방법은 다음과 같습니다.

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

이 구현에서는 더 큰 슬라이스의 요소와 해당 개수를 저장하는 데 맵이 사용됩니다. 더 작은 조각의 요소에 대한 반복에는 맵의 개수에 액세스하고 이를 감소시키는 작업이 포함됩니다. 더 작은 슬라이스에서 누락된 요소가 발견되거나(맵에서 찾을 수 없음) 개수가 0 아래로 떨어지면(더 작은 슬라이스보다 큰 슬라이스에 더 적은 요소가 있음을 나타냄) 함수는 false를 반환하여 더 작은 슬라이스가 없음을 나타냅니다. 하위 집합. 이 접근 방식의 시간 복잡도는 반복 접근 방식보다 훨씬 낮기 때문에 대규모 조각에 더 효율적입니다.

위 내용은 정수 슬라이스를 사용하여 Go에서 하위 집합 관계를 효율적으로 결정하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!