Hat Golang drin?

golang hat nicht drin. Golang bietet weder einen ähnlichen Python-Operator noch eine solche Standardbibliotheksfunktion wie andere Sprachen, beispielsweise in_array in PHP. Gründe: 1. Die Implementierung der Funktion in ist sehr einfach und unnötig. 2. In verschiedenen Szenarien müssen wir auch anhand der tatsächlichen Situation analysieren, welche Methode implementiert werden soll, und nicht anhand einer festen Methode.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, GO Version 1.18, Dell G3-Computer.

Ich habe schon einmal eine Frage zu Zhihu gesehen: Warum hat Golang nicht die gleiche Funktion wie in Python? Also habe ich nach dieser Frage gesucht und festgestellt, dass viele Menschen immer noch solche Fragen haben.

Lassen Sie uns heute über dieses Thema sprechen.

in ist eine sehr häufig verwendete Funktion. Sie kann in einigen Sprachen auch als „enthält“ bezeichnet werden. Obwohl die Ausdrücke in verschiedenen Sprachen unterschiedlich sind, sind sie grundsätzlich vorhanden. Aber leider bietet Go weder einen ähnlichen Python-Operator noch eine solche Standardbibliotheksfunktion wie andere Sprachen, wie zum Beispiel in_array in PHP.

Gos Philosophie besteht darin, weniger mehr zu erreichen. Ich denke, das Go-Team ist vielleicht der Meinung, dass dies eine Funktion ist, die nicht praktisch umzusetzen ist.

Warum sagst du unbedeutend? Wenn Sie es selbst umsetzen möchten, wie sollten Sie es tun?

Mir fallen drei Implementierungsmethoden ein: eine ist Traversal, die andere ist die binäre Suche von sort und die dritte ist der Schlüsselindex der Karte.

Traversal

Traversal sollte die einfachste Implementierungsmethode sein, die wir uns leicht vorstellen können.

Das Beispiel lautet wie folgt:

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

    return false
}

Das Obige zeigt, wie man herausfindet, ob das angegebene int in einer Variablen vom Typ []int existiert. Daran können wir auch erkennen, warum ich gesagt habe, dass es trivial ist .

Dieses Beispiel hat einen Fehler, es unterstützt nur einen einzigen Typ. Wenn Sie allgemeine Funktionen wie interpretierte Sprachen unterstützen möchten, müssen Sie Reflection verwenden.

Der Code lautet wie folgt:

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
}

Um die Vielseitigkeit zu erhöhen, sind die Eingabeparameter haystack und Needle der In-Funktion beide vom Typ interface{}.

Lassen Sie uns kurz über die Vorteile sprechen, die es hat, wenn alle Eingabeparameter interface{} sind. Es gibt zwei Hauptpunkte:

• Erstens ist Haystack vom Typ interface{}, sodass die von in unterstützten Typen nicht einfach sind Slices, aber auch Arrays. Wir sehen, dass die Funktion intern eine Typprüfung für Heuhaufen durch Reflexion durchführt und Slices und Arrays unterstützt. Wenn es sich um andere Typen handelt, wird eine Fehlermeldung angezeigt. Das Hinzufügen neuer Typunterstützung, z. B. Karte, ist eigentlich sehr einfach. Diese Methode wird jedoch nicht empfohlen, da der Effekt von in durch die Syntax von _, ok := m[k] erreicht werden kann.

• Zweitens ist Heuhaufen eine Schnittstelle{}, dann erfüllt auch []Schnittstelle{} die Anforderungen und Nadel ist eine Schnittstelle{}. Auf diese Weise können wir den gleichen Effekt erzielen wie eine interpretierte Sprache.

Wie verstehst du? Ein direktes Beispiel lautet wie folgt:

gotin.In([]interface{}{1, "two", 3}, "two")

haystack ist []interface{}{1, „two“, 3} und Needle ist interface{}, und der Wert zu diesem Zeitpunkt ist „two“. Es scheint, dass in einer interpretierten Sprache Elemente beliebiger Art sein können und nicht unbedingt die gleiche Wirkung haben müssen. Auf diese Weise können wir es nutzen, wie es uns gefällt.

Aber es ist zu beachten, dass es in der Implementierung der In-Funktion einen solchen Code gibt:

if sVal.Index(i).Interface() == needle {
    ...
}

Nicht alle Typen in Go können mit == verglichen werden. Wenn das Element ein Slice oder eine Map enthält, tritt ein Fehler auf darf gemeldet werden.

Binäre Suche

Es gibt einen Nachteil beim Durchlaufen, um zu bestätigen, ob ein Element vorhanden ist, dh wenn das Array oder Slice eine große Datenmenge enthält, z. B. 1.000.000 Daten, also eine Million Im schlimmsten Fall dauert die Bestätigung 1.000.000 Mal, und die Zeitkomplexität ist aktiviert.

Gibt es eine Möglichkeit, die Anzahl der Durchquerungen zu reduzieren?

Die natürliche Methode, die mir in den Sinn kommt, ist die binäre Suche, deren zeitliche Komplexität log2(n) beträgt. Dieser Algorithmus hat jedoch eine Voraussetzung und basiert auf einer geordneten Reihenfolge.

Das erste Problem, das wir lösen müssen, besteht darin, die Sequenz zu bestellen. Die Standardbibliothek von Go bietet diese Funktion bereits im Sortierpaket.

Der Beispielcode lautet wie folgt:

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

Für []int verwenden wir die Funktion SortInts. Wenn es sich um andere Arten von Slices handelt, bietet sort beispielsweise auch verwandte Funktionen, die nach SortStrings sortiert werden können.

Nach dem Sortieren können Sie eine binäre Suche durchführen. Glücklicherweise bietet Go auch diese Funktion. Die entsprechende Funktion für den Typ []int ist SearchInts.

Lassen Sie uns diese Funktion kurz vorstellen, schauen wir uns zuerst die Definition an:

func SearchInts(a []int, x int) int

Die Eingabeparameter sind leicht zu verstehen, suchen Sie x aus Slice a. Der entscheidende Punkt besteht darin, über den Rückgabewert zu sprechen, der für uns von entscheidender Bedeutung ist, um später zu bestätigen, ob das Element existiert. Die Bedeutung des Rückgabewerts besteht darin, die Position des Elements im Slice zurückzugeben. Wenn das Element nicht vorhanden ist, wird die Position zurückgegeben, an der das Element eingefügt werden soll, während das Slice in Ordnung bleibt.

Die Reihenfolge lautet beispielsweise wie folgt:

1 2 6 8 9 11

Angenommen, x ist 6 und nach der Suche wird festgestellt, dass seine Position am Index 2 liegt. Wenn x 7 ist, wird festgestellt, dass das Element nicht existiert , und wenn es in die Sequenz eingefügt wird, wird es an 6 und 8 platziert Dazwischen ist die Indexposition 3, also ist der Rückgabewert 3.

Codetest:

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 对 haystack 切片排序，并返回一个可多次使用的函数。

使用案例如下：

in := gotin.InIntSliceSortedFunc(haystack)

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

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

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

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

map key

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

我们常会用到这个方法。

_, 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 中如何使用 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
}

实现起来不难，但和二分查找有着同样的问题，开始要做数据处理，将 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
    }
}

对于相同的数据，它会返回一个可多次使用的 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。

为便于测试，首先定义了一个用于生成 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()
}

输入参数是 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)
    }
}

首先，通过 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

匹配所有以 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.47ns/op，当然，另外两种方式表现也不错，分别是 22.3ns/op 和 17.7ns/op。

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

测试所有函数在数据量在 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 ns/op，与数据量 10 的时候相比基本无变化。再次验证了前文的说法。

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

$ 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 ns，Sort 次之，而 InIntSlice 呈现线性增加的趋势。一般情况下，如果不是对性能要特殊要求，数据量特别大的场景，针对单类型的遍历已经有非常好的性能了。

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

总结

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

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

【相关推荐：Go视频教程、编程教学】

Das obige ist der detaillierte Inhalt vonHat Golang drin?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!