Go で整数スライスを使用してサブセットの関係を効率的に判断するにはどうすればよいですか?

Go で整数スライスとのサブセット関係を効率的に確認する

あるスライスが別のスライスのサブセットであるかどうかを判断することは、一般的な計算タスクです。 Go では、これを達成するために、さまざまなレベルの効率を提供するさまざまなアプローチがあります。

簡単な方法の 1 つは、両方のスライスの要素を反復処理し、小さいスライスの各要素を大きいスライスの要素と比較することです。 。ただし、このアプローチは、チェックの反復的な性質により、大きなスライスの計算コストが高くなる可能性があります。

効率を高めるためにマップ データ構造を利用する代替アプローチがあります。このアプローチは、差分セット プロパティを活用し、小さなスライスの要素が大きなスライスから減算され、要素が残っているかどうかを判断します。

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 中国語 Web サイトの他の関連記事を参照してください。