эта статьяНачалось вмой блог, если вы найдете это полезным, ставьте лайк и собирайте.
Я уже видел вопрос в Zhihu: почему в Golang нет той же функции, что и в Python? Итак, я искал этот вопрос и обнаружил, что есть еще много людей, у которых есть такие вопросы.
Давайте сегодня поговорим на эту тему.
in — очень распространенная функция, в некоторых языках она также может называться contains, хотя представления в разных языках разные, в основном они есть. Но, к сожалению, в Go нет ни оператора, подобного Python, ни такой стандартной библиотечной функции, как в других языках, например in_array в PHP.
Философия Go заключается в том, что меньше значит больше. Я думаю, возможно, команда Go считает, что это функция, которую не нужно реализовывать.
Почему банально? Если вы хотите сделать это сами, как вы это делаете?
Есть три метода реализации, о которых я думаю: один — обход, другой — своего рода двоичный поиск, а третий — ключевой индекс карты.
Соответствующий исходный код этой статьи был загружен на мой github,poloxue/gotin.
траверс
Обход должен быть самой простой реализацией, которую мы можем легко придумать.
Пример выглядит следующим образом:
func InIntSlice(haystack []int, needle int) bool {
for _, e := range haystack {
if e == needle {
return true
}
}
return false
}
В приведенном выше примере показано, как найти существование указанного int в переменной типа []int. Это очень просто, поэтому мы также можем понять, почему я говорю, что это тривиально реализовать.
В этом примере есть недостаток, он поддерживает только один тип. Если вы хотите поддерживать общие функции, такие как интерпретируемый язык, вам нужно делать это с отражением.
код показывает, как показано ниже:
func In(haystack interface{}, needle interface{}) (bool, error) {
sVal := reflect.ValueOf(haystack)
kind := sVal.Kind()
if kind == reflect.Slice || kind == reflect.Array {
for i := 0; i < sVal.Len(); i++ {
if sVal.Index(i).Interface() == needle {
return true, nil
}
}
return false, nil
}
return false, ErrUnSupportHaystack
}
Чтобы быть более общим, входные параметры стога сена и иглы функции In имеют тип interface{}.
Проще говоря, входные параметры — это преимущества интерфейса {}. Есть два основных момента:
Во-первых, haystack является типом interface{}, поэтому in поддерживает не только срезы, но и массивы. Мы видим, что функция проверяет тип стога сена через отражение, и поддерживает slice (слайс) и array (массив). Если это другие типы, это вызовет ошибку, а добавить поддержку нового типа, такого как карта, на самом деле очень просто. Но этот метод не рекомендуется, потому что эффекта in можно добиться с помощью синтаксиса _, ok := m[k].
Во-вторых, стог сена — это интерфейс{}, тогда []интерфейс{} также соответствует требованиям, а игла — это интерфейс{}. Таким образом, мы можем добиться того же эффекта, что и интерпретируемый язык.
Как понять? Прямое описание примера, как показано ниже:
gotin.In([]interface{}{1, "two", 3}, "two")
haystack — это []interface{}{1, "two", 3}, а игла — это interface{}, и значение равно "two". Таким образом, понимается, что в интерпретируемом языке элементы могут быть любого типа и не обязательно иметь точно такой же эффект. Таким образом, мы можем использовать его произвольно.
Но одно замечание, в реализации функции In есть такой кусок кода:
if sVal.Index(i).Interface() == needle {
...
}
Не все типы в Go можно сравнивать с помощью == , и может быть выдано сообщение об ошибке, если элемент содержит срез или карту.
бинарный поиск
Недостаток обхода для подтверждения наличия элемента, то есть если массив или срез содержит большое количество данных, например 1 000 000 фрагментов данных, то есть один миллион, в худшем случае нам придется пройдите 1 000 000 раз, чтобы подтвердить, сложность времени включена.
Есть ли способ уменьшить количество обходов?
Естественно, на ум приходит метод бинарного поиска, который имеет временную сложность log2(n). Но у этого алгоритма есть предпосылка, и он должен полагаться на упорядоченную последовательность.
Итак, первая проблема, которую нам нужно решить, — отсортировать последовательность, и стандартная библиотека Go уже предоставляет эту функциональность в пакете sort.
Пример кода выглядит следующим образом:
fmt.Println(sort.SortInts([]int{4, 2, 5, 1, 6}))
Для []int мы используем функцию SortInts. Для других типов срезов sort также предоставляет связанные функции. Например, []string можно отсортировать с помощью SortStrings.
После сортировки можно выполнить бинарный поиск, благо, эта функция тоже есть в Go, соответствующая функция типа []int — SearchInts.
Краткое введение в эту функцию, сначала см. определение:
func SearchInts(a []int, x int) int
Входные параметры легко понять, ищите x из среза a. Ключевым моментом является обсуждение возвращаемого значения, которое имеет решающее значение для нас, чтобы позже подтвердить существование элемента. Смысл возвращаемого значения, возвращает позицию искомого элемента в срезе, если элемент не существует, возвращает позицию, в которую элемент должен быть вставлен, сохраняя порядок среза.
Например, последовательность следующая:
1 2 6 8 9 11
Предположим, что x равно 6, после поиска он найдет свою позицию по индексу 2, если x равно 7, окажется, что элемент не существует, если вставить его в последовательность, он будет помещен между 6 и 8, и позиция индекса равна 3, поэтому return Значение равно 3.
Тест кода:
fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 6)) // 2
fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 7)) // 3
Если вы определяете, находится ли элемент в последовательности, вам нужно только определить, совпадает ли значение в возвращаемой позиции с искомым значением.
Но есть и другой случай, если вставляемый элемент находится в конце последовательности, например, значение элемента равно 12, позиция вставки равна длине последовательности 6. Если вы ищете элемент в позиции 6 напрямую, вы можете выйти за границы. тогда что нам делать? На самом деле достаточно судить, меньше ли возвращаемое значение длины среза, если меньше, значит, элемент находится в последовательности слайсов.
Полный код реализации выглядит следующим образом:
func SortInIntSlice(haystack []int, needle int) bool {
sort.Ints(haystack)
index := sort.SearchInts(haystack, needle)
return index < len(haystack) && haystack[index] == needle
}
Но проблема остается: для неупорядоченных сценариев экономически невыгодно, если каждый запрос нужно сортировать один раз. Лучше всего реализовать сортировку и немного изменить код.
func InIntSliceSortedFunc(haystack []int) func(int) bool {
sort.Ints(haystack)
return func(needle int) bool {
index := sort.SearchInts(haystack, needle)
return index < len(haystack) && haystack[index] == needle
}
}
В приведенной выше реализации мы сортируем срез стога сена, вызывая InIntSliceSortedFunc, и возвращаем функцию, которую можно использовать несколько раз.
Вариант использования следующий:
in := gotin.InIntSliceSortedFunc(haystack)
for i := 0; i<maxNeedle; i++ {
if in(i) {
fmt.Printf("%d is in %v", i, haystack)
}
}
Что не так с бинарным поиском?
Важный момент, который приходит мне на ум, для реализации бинарного поиска элементы должны быть сортируемыми, например, тип int, string, float. Для таких типов как структуры, срезы, массивы и карты использовать не так удобно.Конечно, если вы хотите их использовать, то тоже можно, но нам нужно сделать соответствующие расширения и отсортировать их по заданному критерии, такие как член структуры.
На этом этапе вводится реализация бинарного поиска.
map key
В этом разделе описывается метод ключа карты. Его сложность алгоритма составляет O1, а производительность запроса остается неизменной вне зависимости от объема данных. В основном он зависит от типа данных карты в Go. Хэш-карта используется для прямой проверки существования ключа. Каждый должен быть знаком с алгоритмом. Ключ может быть напрямую сопоставлен с позицией индекса.
Мы часто используем этот метод.
_, ok := m[k]
if ok {
fmt.Println("Found")
}
Так как же это сочетается с in? Случай иллюстрирует проблему.
Предположим, у нас есть переменная типа []int следующего вида:
s := []int{1, 2, 3}
Чтобы использовать возможности map для проверки существования элемента, преобразуйте s в map[int]struct{}.
m := map[interface{}]struct{}{
1: struct{}{},
2: struct{}{},
3: struct{}{},
4: struct{}{},
}
Если вы проверяете, существует ли элемент, вам нужно всего лишь написать его следующим образом:
k := 4
if _, ok := m[k]; ok {
fmt.Printf("%d is found\n", k)
}
Это очень просто?
Чтобы добавить, почему здесь используется struct{}, вы можете прочитать статью, которую я написал ранее оКак использовать наборы в Goстатья.
Согласно этой идее, функция реализации выглядит следующим образом:
func MapKeyInIntSlice(haystack []int, needle int) bool {
set := make(map[int]struct{})
for _ , e := range haystack {
set[e] = struct{}{}
}
_, ok := set[needle]
return ok
}
Это несложно реализовать, но у него та же проблема, что и у бинарного поиска: начать обрабатывать данные и конвертировать срезы в карты. Если данные каждый раз одни и те же, немного измените его реализацию.
func InIntSliceMapKeyFunc(haystack []int) func(int) bool {
set := make(map[int]struct{})
for _ , e := range haystack {
set[e] = struct{}{}
}
return func(needle int) bool {
_, ok := set[needle]
return ok
}
}
Для одних и тех же данных он возвращает функцию in, которую можно использовать несколько раз. Один из вариантов использования выглядит следующим образом:
in := gotin.InIntSliceMapKeyFunc(haystack)
for i := 0; i<maxNeedle; i++ {
if in(i) {
fmt.Printf("%d is in %v", i, haystack)
}
}
По сравнению с первыми двумя алгоритмами этот метод обладает наибольшей эффективностью обработки и очень подходит для обработки больших данных. Следующий тест производительности, мы увидим эффект.
представление
После представления всех методов давайте собственно сравним производительность каждого алгоритма. Исходный код теста находится вgotin_test.goв файле.
Тест производительности в основном проверяет производительность различных алгоритмов по размеру данных.В этой статье выбраны три уровня данных тестовой выборки, а именно 10, 1000 и 1000000.
Чтобы облегчить тестирование, сначала определите функцию для генерации данных выборки стога сена и иглы.
код показывает, как показано ниже:
func randomHaystackAndNeedle(size int) ([]int, int){
haystack := make([]int, size)
for i := 0; i<size ; i++{
haystack[i] = rand.Int()
}
return haystack, rand.Int()
}
Входным параметром является размер, а стог сена размера size и иголка генерируются случайным образом с помощью rand.Int(). В тестовом примере достаточно ввести эту случайную функцию для генерации данных.
Например, следующим образом:
func BenchmarkIn_10(b *testing.B) {
haystack, needle := randomHaystackAndNeedle(10)
b.ResetTimer()
for i := 0; i < b.N; i++ {
_, _ = gotin.In(haystack, needle)
}
}
Во-первых, срез из 10 элементов генерируется случайным образом с помощью randomHaystackAndNeedle. Поскольку время генерации выборочных данных не должно учитываться в бенчмарке, мы сбрасываем время с помощью b.ResetTimer() .
Во-вторых, функция измерения давления основана наTest+函数名+样本数据量Запись правила, например BenchmarkIn_10 в данном случае, представляет функцию теста In, а размер выборки равен 10. Если мы хотим протестировать InIntSlice с объемом данных 1000, функция стресс-теста будет называться BenchmarkInIntSlice_1000.
Да начнется испытание! Кратко о конфигурации моего ноутбука, версия Mac Pro 15, 16G памяти, 512 SSD, 4-ядерный 8-поточный процессор.
Протестируйте производительность всех функций с размером данных 10.
$ go test -run=none -bench=10$ -benchmem
Соответствует всем функциям ударения, оканчивающимся на 10.
Результаты теста:
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_10-8 3000000 501 ns/op 112 B/op 11 allocs/op
BenchmarkInIntSlice_10-8 200000000 7.47 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_10-8 100000000 22.3 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_10-8 10000000 162 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_10-8 100000000 17.7 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_10-8 3000000 513 ns/op 163 B/op 1 allocs/op
PASS
ok github.com/poloxue/gotin 13.162s
Лучшая производительность не у SortedFunc и MapKeyFunc, а у простейшего запроса обхода для одного типа, который занимает в среднем 7,47 нс/операцию.Конечно, два других метода также работают хорошо, что составляет 22,3 нс/оп и 17,7 нс/оп. оп соответственно. .
Наихудшие показатели у In, SortIn (сортировка за повторение) и MapKeyIn (создание карты за повторение) со средним временем 501 нс/операция и 513 нс/операция соответственно.
Протестируйте работу всех функций с объемом данных 1000.
$ go test -run=none -bench=1000$ -benchmem
Результаты теста:
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000-8 30000 45074 ns/op 8032 B/op 1001 allocs/op
BenchmarkInIntSlice_1000-8 5000000 313 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000-8 30000000 44.0 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000-8 20000 65401 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000-8 100000000 17.6 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000-8 20000 82761 ns/op 47798 B/op 65 allocs/op
PASS
ok github.com/poloxue/gotin 11.312s
В тройку лидеров по-прежнему входят InIntSlice, InIntSliceSortedFunc и InIntSliceMapKeyFunc, но на этот раз порядок изменился: MapKeyFunc имеет наилучшую производительность при 17,6 нс/оп, что практически не изменилось по сравнению с объемом данных, равным 10. И снова подтверждается предыдущее утверждение.
Точно так же, когда количество данных равно 1 000 000.
$ go test -run=none -bench=1000000$ -benchmem
Результаты теста следующие:
goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000000-8 30 46099678 ns/op 8000098 B/op 1000001 allocs/op
BenchmarkInIntSlice_1000000-8 3000 424623 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000000-8 20000000 72.8 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000000-8 10 138873420 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000000-8 100000000 16.5 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000000-8 10 156215889 ns/op 49824225 B/op 38313 allocs/op
PASS
ok github.com/poloxue/gotin 15.178s
MapKeyFunc по-прежнему показал лучшие результаты, занимая 17,2 нс на операцию, за ней следует Sort, в то время как InIntSlice показал линейный рост. В обычных условиях, если нет особых требований к производительности и объем данных особенно велик, он уже имеет очень хорошую производительность для однотипного обхода.
Из результатов тестирования видно, что общая функция In, реализованная с помощью отражения, требует выделения большого объема памяти при каждом выполнении, что удобно, но и за счет производительности.
Суммировать
Эта статья ведет к теме с вопросом, почему в Go нет Python-подобного метода In. Думаю, с одной стороны, реализация очень простая и ненужная. Кроме того, с другой стороны, в разных сценариях нам также необходимо проанализировать, какой способ реализовать в соответствии с реальной ситуацией, а не фиксированным способом.
Далее мы вводим три способа реализации In и анализируем их преимущества и недостатки. С помощью теста анализа производительности мы можем сделать общий вывод, какой метод подходит для какой сцены, но в целом все еще недостаточно подробно, и заинтересованные друзья могут продолжить изучение.
Ссылаться на
Есть ли в Go конструкция «if x in», похожая на Python?
Почему в Golang нет такой функции, как в Python?
Добро пожаловать в мой публичный аккаунт WeChat