Repository: go
Issue: proposal: slices: add a reusable slices.Contains()
Labels: Proposal

### Proposal Details


Since the introduction of the slices package into the standard library, slices.Contains() has become one of its most frequently used functions. However, this function is merely a simple wrapper around slices.Index(), which iterates through the slice to find the result, leading to a time complexity of O(n).

While slices.Index() provides more information (the position of the element within the slice), slices.Contains() only needs to know whether the element is present in the slice. Therefore, there are more efficient ways than wrapping slices.Index(), especially since the exact position of the element is redundant information for slices.Contains(). This is particularly true when dealing with a vast number of elements and multiple loops, as seen in:

(I have also looked into bytes/strings.Contains(), which are wrappers around bytes/strings.Index() too, but unlike slices.Index(), strings.Index() does not simply iterate through but adjusts its approach based on the size of the parameters.)

```go
func bar() {
    var slice []int

    rand.Seed(time.Now().UnixNano())

    for i := 0; i < 100_000_000; i++ {
        slice = append(slice, rand.Intn(100_000_000))
    }

    var existSli []int

    for i := 0; i < 100_000; i++ {
        for j := 0; j < 100_000; j++ {

            exist := slices.Contains(slice, j)
            if exist {
                existSli = append(existSli, j)
            }
        }
    }
}
```

There are two approaches:

1. If the slice is ordered, then use binary search with a time complexity of O(logn). However,  sorting incurs additional overhead.

(For more details, refer to [sort: add Find #50340](https://github.com/golang/go/issues/50340).   Although not highly relevant, it can provide some ideas)

2. Use a hash map, turning slice elements into map keys, which can reduce the time complexity to O(1). However, it's important to note that creating and maintaining a map incurs higher overhead than using a slice. Therefore, for smaller n values and only use once case, using a map might not be more efficient. 

My initial attempt to optimize slices.Contains() involved using either binary search or a map. However, the issue is that slices.Contains() is only used once, lacking **memorability**, and a single use is far from offsetting the sorting overhead of binary search and the high cost of creating and maintaining a map.

For this common scenario, I suggest adding a new function, slices.ContainsUseManyTimes(), which takes a slice as an input and returns a function, similar to `func ContainsUseManyTimes(sli []int64) func(int64) bool` (though the function name could be more elegant).

This way, for the initial scenario mentioned, we can:

```go
func bar() {
	var slice []int

	rand.Seed(time.Now().UnixNano())

	for i := 0; i < 100_000_000; i++ {
		slice = append(slice, rand.Intn(100_000_000))
	}

	f := ContainsUseManyTimes(slice)

	var existSli []int

	for i := 0; i < 100_000; i++ {
		for j := 0; j < 100_000; j++ {

			if f(j) {
				existSli = append(existSli, j)
			}
		}
	}

}

func ContainsUseManyTimes(sli []int64) func(int64) bool {

	var sortSli []int64
	copy(sortSli, sli)

	sort.Slice(sortSli, func(i, j int) bool { return sortSli[i] < sortSli[j] })

	return func(target int64) bool {
		low := 0
		high := len(sortSli) - 1

		for low <= high {
			mid := low + (high-low)/2
			midVal := sortSli[mid]

			if midVal < target {
				low = mid + 1
			} else if midVal > target {
				high = mid - 1
			} else {
				return true
		}
		return false
	}
}
```

### Regarding performance:

ContainsUseManyTimes could use either binary search or a map, but performance tests show that using a map leads to a sudden performance drop with 9 million elements (the reason is still under consideration), while binary search remains efficient and stable.

Here is a simplified performance test:

contains.go:

```go
func ContainsFuncByMap(sli []int64) func(int64) bool {

	m := make(map[int64]struct{})
	for _, v := range sli {
		m[v] = struct{}{}
	}

	return func(target int64) bool {
		if _, ok := m[target]; ok {
			return true
		} else {
			return false
		}
	}
}


func ContainsFuncBinarySearch(sli []int64) func(int64) bool {

	sortSli := make([]int64, len(sli))
	copy(sortSli, sli)

	sort.Slice(sortSli, func(i, j int) bool { return sortSli[i] < sortSli[j] })

	return func(target int64) bool {
		low := 0
		high := len(sortSli) - 1

		for low <= high {
			mid := low + (high-low)/2
			midVal := sortSli[mid]

			if midVal < target {
				low = mid + 1
			} else if midVal > target {
				high = mid - 1
			} else {
				return true
			}
		}
		return false
	}
}

```

contains_test.go:

```go
func BenchmarkContains(b *testing.B) {
	for i := 0; i < b.N; i++ {
		slices.Contains(sli, target)
	}
}

func BenchmarkContainsFuncByMap(b *testing.B) {
	f := ContainsFuncByMap(sli)
	for i := 0; i < b.N; i++ {
		f(target)
	}
}

func BenchmarkContainsFuncBinarySearch(b *testing.B) {
	f := ContainsFuncBinarySearch(sli)
	for i := 0; i < b.N; i++ {
		f(target)
	}
}
```

```output
➜  map-vs-slice git:(main) ✗ go test -test.bench=".*" -benchmem    (N is the length of slice, N=100)
goos: darwin
goarch: arm64
pkg: mapvsslice
BenchmarkContains-8                     35311144                33.32 ns/op            0 B/op          0 allocs/op
BenchmarkContainsFuncByMap-8            173432636                6.919 ns/op           0 B/op          0 allocs/op
BenchmarkContainsFuncBinarySearch-8     524108920                2.262 ns/op           0 B/op          0 allocs/op
PASS
ok      mapvsslice      5.750s
➜  map-vs-slice git:(main) ✗ go test -test.bench=".*" -benchmem     (N=10000)
goos: darwin
goarch: arm64
pkg: mapvsslice
BenchmarkContains-8                       373540              3171 ns/op               0 B/op          0 allocs/op
BenchmarkContainsFuncByMap-8            172989003                6.936 ns/op           0 B/op          0 allocs/op
BenchmarkContainsFuncBinarySearch-8     535104032                2.329 ns/op           0 B/op          0 allocs/op
PASS
ok      mapvsslice      5.650s
➜  map-vs-slice git:(main) ✗ go test -test.bench=".*" -benchmem  (N=1000000)
goos: darwin
goarch: arm64
pkg: mapvsslice
BenchmarkContains-8                         3715            322815 ns/op               0 B/op          0 allocs/op
BenchmarkContainsFuncByMap-8            160653786                7.422 ns/op           0 B/op          0 allocs/op
BenchmarkContainsFuncBinarySearch-8     505987872                2.249 ns/op           0 B/op          0 allocs/op
PASS
ok      mapvsslice      6.672s
➜  map-vs-slice git:(main) ✗ go test -test.bench=".*" -benchmem   (N=100000000)
goos: darwin
goarch: arm64
pkg: mapvsslice
BenchmarkContains-8                           92          12866297 ns/op               0 B/op          0 allocs/op
BenchmarkContainsFuncByMap-8                   1        12020805167 ns/op       3088798200 B/op  1518423 allocs/op
BenchmarkContainsFuncBinarySearch-8     529186568                2.314 ns/op           0 B/op          0 allocs/op
PASS
ok      mapvsslice      18.064s
```

Note: The above benchmark does not cover slice sorting or the cost of creating a map. The essence of this optimization is when it is necessary to determine whether M elements are in a slice of N elements multiple times (M and N are very large), the one-time overhead of slice sorting and map creation and maintenance is shared through the number of times. Therefore, depending on the size of N, M, and element type, there is a turning point. Only when this point is met, the effect of using this method Only then will it be absolutely improved


Final code, similar to the CL https://go-review.googlesource.com/c/go/+/568095

Suggestions and comments are welcome.