Rumah > pembangunan bahagian belakang > Golang > Adakah golang ada dalam

Adakah golang ada dalam

青灯夜游
Lepaskan: 2023-01-18 15:01:16
asal
1625 orang telah melayarinya

golang tiada masuk. Golang tidak menyediakan pengendali Python yang serupa, dan juga tidak menyediakan fungsi perpustakaan standard seperti bahasa lain, seperti in_array dalam PHP. Sebab: 1. Pelaksanaan fungsi dalam adalah sangat mudah dan tidak perlu 2. Dalam senario yang berbeza, kita juga perlu menganalisis kaedah yang hendak dilaksanakan berdasarkan situasi sebenar, dan bukannya kaedah tetap.

Adakah golang ada dalam

Persekitaran pengendalian tutorial ini: sistem Windows 7, GO versi 1.18, komputer Dell G3.

Saya melihat soalan tentang Zhihu sebelum ini: Mengapa Golang tidak mempunyai fungsi yang sama seperti dalam Python? Jadi, saya mencari soalan ini dan mendapati ramai orang masih mempunyai soalan sedemikian.

Mari kita bercakap tentang topik ini hari ini.

in ialah fungsi yang sangat biasa digunakan. Ia juga boleh dipanggil mengandungi dalam beberapa bahasa Walaupun ungkapan dalam bahasa berbeza, ia pada dasarnya ada. Tetapi malangnya, Go tidak menyediakan operator Python yang serupa, dan tidak menyediakan fungsi perpustakaan standard seperti bahasa lain, seperti in_array dalam PHP.

Falsafah Go ialah kurang adalah lebih. Saya fikir mungkin pasukan Go merasakan ini adalah ciri yang tidak praktikal untuk dilaksanakan.

Kenapa anda kata ia tidak penting? Jika anda ingin melaksanakannya sendiri, bagaimanakah anda harus melakukannya?

Terdapat tiga kaedah pelaksanaan yang boleh saya fikirkan, satu ialah traversal, satu lagi ialah carian binari isihan, dan yang ketiga ialah indeks kunci peta.

Traversal

Traversal sepatutnya menjadi pelaksanaan paling mudah yang mudah kita fikirkan.

Contohnya adalah seperti berikut:

func InIntSlice(haystack []int, needle int) bool {
    for _, e := range haystack {
        if e == needle {
            return true
        }
    }

    return false
}
Salin selepas log masuk

Di atas menunjukkan cara mencari contoh sama ada int tertentu wujud dalam pembolehubah jenis []int. Bukankah ia sangat mudah? Dari sini juga kita boleh rasa Kenapa saya kata remeh untuk dilaksanakan.

Contoh ini mempunyai kecacatan, ia hanya menyokong satu jenis. Jika anda ingin menyokong umum dalam fungsi seperti bahasa yang ditafsirkan, anda perlu menggunakan refleksi.

Kod adalah seperti berikut:

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
}
Salin selepas log masuk

Untuk menjadi lebih serba boleh, parameter input timbunan jerami dan jarum fungsi In adalah kedua-dua jenis antara muka{}.

Mari kita bincangkan secara ringkas tentang faedah semua parameter input sebagai antara muka{}. Terdapat dua perkara utama, seperti berikut:

  • Pertama, timbunan jerami ialah antara muka{} jenis, jadi Jenis yang disokong oleh dalam tidak terhad kepada hirisan, tetapi juga termasuk tatasusunan. Kami melihat bahawa fungsi secara dalaman melakukan pemeriksaan jenis pada timbunan jerami melalui refleksi, dan menyokong kepingan dan tatasusunan. Jika ia adalah jenis lain, ralat akan digesa Menambah sokongan jenis baharu, seperti peta, sebenarnya sangat mudah. Tetapi kaedah ini tidak disyorkan, kerana kesan in boleh dicapai melalui sintaks _, ok := m[k].

  • Kedua, timbunan jerami ialah antara muka{}, kemudian []antara muka{} juga memenuhi keperluan, dan jarum ialah antara muka{}. Dengan cara ini, kita boleh mencapai kesan yang sama seperti bahasa yang ditafsirkan.

Bagaimana untuk memahami? Contoh langsung adalah seperti berikut:

gotin.In([]interface{}{1, "two", 3}, "two")
Salin selepas log masuk

timbunan jerami ialah []antara muka{}{1, "dua", 3}, dan jarum ialah antara muka{}, dan nilai pada masa ini ialah "dua" . Nampaknya dalam bahasa yang ditafsirkan, unsur-unsur boleh menjadi apa-apa jenis dan tidak perlu mempunyai kesan yang sama. Dengan cara ini, kita boleh menggunakannya sesuka hati.

Tetapi satu perkara yang perlu diperhatikan ialah terdapat sekeping kod ini dalam pelaksanaan fungsi In:

if sVal.Index(i).Interface() == needle {
    ...
}
Salin selepas log masuk

Tidak semua jenis dalam Go boleh dibandingkan menggunakan ==, jika elemen mengandungi kepingan atau peta, ralat mungkin dilaporkan.

Carian binari

Terdapat kelemahan dalam merentasi untuk mengesahkan sama ada unsur wujud, iaitu jika tatasusunan atau kepingan mengandungi satu jumlah data, seperti 1,000,000 keping data, iaitu satu juta Senario kes terburuk ialah kita perlu merentasi 1,000,000 kali untuk mengesahkan, dan kerumitan masa adalah Hidup.

Adakah terdapat cara untuk mengurangkan bilangan traversals?

Kaedah yang secara semula jadi terlintas di fikiran ialah carian binari, yang kerumitan masanya ialah log2(n). Tetapi algoritma ini mempunyai prasyarat dan bergantung pada urutan yang diperintahkan.

Jadi, masalah pertama yang perlu kami selesaikan ialah memesan urutan perpustakaan standard Go sudah menyediakan fungsi ini di bawah pakej isihan.

Kod sampel adalah seperti berikut:

fmt.Println(sort.SortInts([]int{4, 2, 5, 1, 6}))
Salin selepas log masuk

Untuk []int, fungsi yang kami gunakan ialah SortInts Jika ia jenis hirisan lain, isihan juga menyediakan fungsi yang berkaitan, seperti []rentetan Isih mengikut SortStrings.

Selepas mengisih, anda boleh melakukan carian binari Mujurlah, Go juga menyediakan fungsi yang sepadan bagi jenis []int ialah SearchInts.

Pengenalan ringkas kepada fungsi ini, mari lihat definisi dahulu:

func SearchInts(a []int, x int) int
Salin selepas log masuk

Parameter input mudah difahami, cari x dari kepingan a. Perkara utama ialah bercakap tentang nilai pulangan, yang penting untuk kami mengesahkan sama ada elemen itu wujud kemudian. Maksud nilai pulangan adalah untuk mengembalikan kedudukan elemen dalam kepingan Jika elemen itu tidak wujud, ia akan mengembalikan kedudukan di mana elemen harus dimasukkan sambil memastikan kepingan itu teratur.

Sebagai contoh, urutannya adalah seperti berikut:

1 2 6 8 9 11
Salin selepas log masuk

Andaikan, x ialah 6, dan selepas mencari, ia akan mendapati kedudukannya berada pada indeks 2 jika x ialah 7 , didapati bahawa elemen tidak wujud, jika Urutan yang dimasukkan akan diletakkan di antara 6 dan 8, dan kedudukan indeks ialah 3, jadi nilai pulangan ialah 3.

Ujian kod:

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
Salin selepas log masuk

如果判断元素是否在序列中,只要判断返回位置上的值是否和查找的值相同即可。

但还有另外一种情况,如果插入元素位于序列最后,例如元素值为 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
}
Salin selepas log masuk

但这还有个问题,对于无序的场景,如果每次查询都要经过一次排序并不划算。最好能实现一次排序,稍微修改下代码。

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
    }
}
Salin selepas log masuk

上面的实现,我们通过调用 InIntSliceSortedFunc 对 haystack 切片排序,并返回一个可多次使用的函数。

使用案例如下:

in := gotin.InIntSliceSortedFunc(haystack)

for i := 0; i<maxNeedle; i++ {
    if in(i) {
        fmt.Printf("%d is in %v", i, haystack)
    }
}
Salin selepas log masuk

二分查找的方式有什么不足呢?

我想到的重要一点,要实现二分查找,元素必须是可排序的,如 int,string,float 类型。而对于结构体、切片、数组、映射等类型,使用起来就不是那么方便,当然,如果要用,也是可以的,不过需要我们进行一些适当扩展,按指定标准排序,比如结构的某个成员。

到此,二分查找的 in 实现就介绍完毕了。

map key

本节介绍 map key 方式。它的算法复杂度是 O1,无论数据量多大,查询性能始终不变。它主要依赖的是 Go 中的 map 数据类型,通过 hash map 直接检查 key 是否存在,算法大家应该都比较熟悉,通过 key 可直接映射到索引位置。

我们常会用到这个方法。

_, ok := m[k]
if ok {
    fmt.Println("Found")
}
Salin selepas log masuk

那么它和 in 如何结合呢?一个案例就说明白了这个问题。

假设,我们有一个 []int 类型变量,如下:

s := []int{1, 2, 3}
Salin selepas log masuk

为了使用 map 的能力检查某个元素是否存在,可以将 s 转化 map[int]struct{}。

m := map[interface{}]struct{}{
    1: struct{}{},
    2: struct{}{},
    3: struct{}{},
    4: struct{}{},
}
Salin selepas log masuk

如果检查某个元素是否存在,只需要通过如下写法即可确定:

k := 4
if _, ok := m[k]; ok {
    fmt.Printf("%d is found\n", k)
}
Salin selepas log masuk

是不是非常简单?

补充一点,关于这里为什么使用 struct{},可以阅读我之前写的一篇关于 Go 中如何使用 set 的文章。

按照这个思路,实现函数如下:

func MapKeyInIntSlice(haystack []int, needle int) bool {
    set := make(map[int]struct{})
    
    for _ , e := range haystack {
        set[e] = struct{}{}
    }
    
    _, ok := set[needle]
    return ok
}
Salin selepas log masuk

实现起来不难,但和二分查找有着同样的问题,开始要做数据处理,将 slice 转化为 map。如果是每次数据相同,稍微修改下它的实现。

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
    }
}
Salin selepas log masuk

对于相同的数据,它会返回一个可多次使用的 in 函数,一个使用案例如下:

in := gotin.InIntSliceMapKeyFunc(haystack)

for i := 0; i<maxNeedle; i++ {
    if in(i) {
        fmt.Printf("%d is in %v", i, haystack)
    }
}
Salin selepas log masuk

对比前两种算法,这种方式的处理效率最高,非常适合于大数据的处理。接下来的性能测试,我们将会看到效果。

性能

介绍完所有方式,我们来实际对比下每种算法的性能。测试源码位于 gotin_test.go 文件中。

基准测试主要是从数据量大小考察不同算法的性能,本文中选择了三个量级的测试样本数据,分别是 10、1000、1000000。

为便于测试,首先定义了一个用于生成 haystack 和 needle 样本数据的函数。

代码如下:

func randomHaystackAndNeedle(size int) ([]int, int){
    haystack := make([]int, size)

    for i := 0; i<size ; i++{
        haystack[i] = rand.Int()
    }

    return haystack, rand.Int()
}
Salin selepas log masuk

输入参数是 size,通过 http://rand.Int() 随机生成切片大小为 size 的 haystack 和 1 个 needle。在基准测试用例中,引入这个随机函数生成数据即可。

举个例子,如下:

func BenchmarkIn_10(b *testing.B) {
    haystack, needle := randomHaystackAndNeedle(10)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _, _ = gotin.In(haystack, needle)
    }
}
Salin selepas log masuk

首先,通过 randomHaystackAndNeedle 随机生成了一个含有 10 个元素的切片。因为生成样本数据的时间不应该计入到基准测试中,我们使用 b.ResetTimer() 重置了时间。

其次,压测函数是按照 Test+函数名+样本数据量 规则编写,如案例中 BenchmarkIn_10,表示测试 In 函数,样本数据量为 10。如果我们要用 1000 数据量测试 InIntSlice,压测函数名为 BenchmarkInIntSlice_1000。

测试开始吧!简单说下我的笔记本配置,Mac Pro 15 版,16G 内存,512 SSD,4 核 8 线程的 CPU。

测试所有函数在数据量在 10 的情况下的表现。

$ go test -run=none -bench=10$ -benchmem
Salin selepas log masuk

匹配所有以 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
Salin selepas log masuk

表现最好的并非 SortedFunc 和 MapKeyFunc,而是最简单的针对单类型的遍历查询,平均耗时 7.47ns/op,当然,另外两种方式表现也不错,分别是 22.3ns/op 和 17.7ns/op。

表现最差的是 In、SortIn(每次重复排序) 和 MapKeyIn(每次重复创建 map)两种方式,平均耗时分别为 501ns/op 和 513ns/op。

测试所有函数在数据量在 1000 的情况下的表现。

$ go test -run=none -bench=1000$ -benchmem
Salin selepas log masuk

测试结果:

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
Salin selepas log masuk

表现前三依然是 InIntSlice、InIntSliceSortedFunc 和 InIntSliceMapKeyFunc,但这次顺序发生了变化,MapKeyFunc 表现最好,17.6 ns/op,与数据量 10 的时候相比基本无变化。再次验证了前文的说法。

同样的,数据量 1000000 的时候。

$ go test -run=none -bench=1000000$ -benchmem
Salin selepas log masuk

测试结果如下:

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
Salin selepas log masuk

MapKeyFunc 依然表现最好,每次操作用时 17.2 ns,Sort 次之,而 InIntSlice 呈现线性增加的趋势。一般情况下,如果不是对性能要特殊要求,数据量特别大的场景,针对单类型的遍历已经有非常好的性能了。

从测试结果可以看出,反射实现的通用 In 函数每次执行需要进行大量的内存分配,方便的同时,也是以牺牲性能为代价的。

总结

本文通过一个问题引出主题,为什么 Go 中没有类似 Python 的 In 方法。我认为,一方面是实现非常简单,没有必要。除此以外,另一方面,在不同场景下,我们还需要根据实际情况分析用哪种方式实现,而不是一种固定的方式。

接着,我们介绍了 In 实现的三种方式,并分析了各自的优劣。通过性能分析测试,我们能得出大致的结论,什么方式适合什么场景,但总体还是不能说足够细致,有兴趣的朋友可以继续研究下。

【相关推荐:Go视频教程编程教学

Atas ialah kandungan terperinci Adakah golang ada dalam. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan