Golang中如何尽可能高效地搜索切片中的字符串？

Golang中如何尽可能高效地搜索切片中的字符串？

foo := []string{"foo","bar","FoO","baR"}
sayIfExists("baR") //func(string)bool

有没有人能实现一个效率最高的 sayIfExists() 函数？

for _,v := range foo {
    if givenStr == v {
       return true
    }
}

这个例子效率不高。因为如果我搜索最后一个值，它需要遍历整个切片。

对于非常大的数据集来说这太糟糕了。

有没有更好的想法？

7 回复

是的，当数据是动态的时候，前缀树比哈希更好

更多关于Golang中如何尽可能高效地搜索切片中的字符串？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


NobbZ:

取决于要搜索的单词长度。不过它的内存开销可能比 Go 原生映射更大…

是的，这是个很棒的解决方案，但这里存在权衡： CPU 与内存的取舍。 @AnikHasibul

但是必须计算哈希值。最高效的版本，特别是对于动态集合而言，前缀树可能是最有效的解决方案，至少在运行效率上是如此。

其运行时间取决于待搜索词的长度。不过它的内存开销可能会比 Go 原生映射更大……

如果切片没有顺序，那么你只能使用线性搜索，其时间复杂度为 O(n)。如果切片已排序，你可以使用二分搜索在 O(log(n)) 时间内完成。这是假设你对数据结构和其填充方式没有控制权的情况。

使用 sort 包

package main

import sort

func main() {
    foo := []string{"foo","bar","FoO","baR"}
    sort.String(foo)
    query := "baR"
    match := sort.SearchStrings(foo, "baR")
    if foo[match] < len(foo) && foo[match] == query {
         // 匹配
    } else {
        // 不匹配
    }
}

最佳方式是使用 map，Go 的 map 通过哈希表实现，具有 O(1) 的时间复杂度

foo = map[string]struct{}{"foo":struct{}{}, "bar":struct{}{}, "FoO": struct{}{}, "baR": struct{}{}}

_, ok:= foo["baR"]
// 处理

Go 映射不是 O(1) 的。

reddit

Go Maps Don’t Appear to be O(1) • r/golang

缩略图

目前在 reddit 上获得 23 个赞和 40 条评论

对于需要高效搜索字符串切片的需求，有几种优化方案可以实现。以下是几种效率较高的实现方法：

方案1：使用map进行O(1)查找

package main

import (
    "fmt"
    "strings"
)

type StringSearcher struct {
    data map[string]bool
}

func NewStringSearcher(slice []string) *StringSearcher {
    searcher := &StringSearcher{
        data: make(map[string]bool, len(slice)),
    }
    for _, v := range slice {
        searcher.data[v] = true
    }
    return searcher
}

func (s *StringSearcher) SayIfExists(str string) bool {
    return s.data[str]
}

// 使用示例
func main() {
    foo := []string{"foo", "bar", "FoO", "baR"}
    searcher := NewStringSearcher(foo)
    
    fmt.Println(searcher.SayIfExists("baR")) // true
    fmt.Println(searcher.SayIfExists("nonexistent")) // false
}

方案2：预排序 + 二分查找

package main

import (
    "fmt"
    "sort"
)

type SortedStringSearcher struct {
    data []string
}

func NewSortedStringSearcher(slice []string) *SortedStringSearcher {
    // 复制切片避免修改原数据
    data := make([]string, len(slice))
    copy(data, slice)
    sort.Strings(data)
    
    return &SortedStringSearcher{data: data}
}

func (s *SortedStringSearcher) SayIfExists(str string) bool {
    i := sort.SearchStrings(s.data, str)
    return i < len(s.data) && s.data[i] == str
}

// 使用示例
func main() {
    foo := []string{"foo", "bar", "FoO", "baR"}
    searcher := NewSortedStringSearcher(foo)
    
    fmt.Println(searcher.SayIfExists("bar")) // true
    fmt.Println(searcher.SayIfExists("nonexistent")) // false
}

方案3：考虑大小写不敏感的搜索

package main

import (
    "fmt"
    "strings"
)

type CaseInsensitiveSearcher struct {
    data map[string]string // 小写形式 -> 原始形式
}

func NewCaseInsensitiveSearcher(slice []string) *CaseInsensitiveSearcher {
    searcher := &CaseInsensitiveSearcher{
        data: make(map[string]string, len(slice)),
    }
    for _, v := range slice {
        lower := strings.ToLower(v)
        searcher.data[lower] = v
    }
    return searcher
}

func (s *CaseInsensitiveSearcher) SayIfExists(str string) bool {
    _, exists := s.data[strings.ToLower(str)]
    return exists
}

// 使用示例
func main() {
    foo := []string{"foo", "bar", "FoO", "baR"}
    searcher := NewCaseInsensitiveSearcher(foo)
    
    fmt.Println(searcher.SayIfExists("BAR")) // true
    fmt.Println(searcher.SayIfExists("foo")) // true
}

性能分析

  • map方案：O(1)查找时间，但需要O(n)额外空间和O(n)初始化时间
  • 排序+二分查找：O(log n)查找时间，需要O(n log n)排序时间
  • 线性搜索：O(n)查找时间，无额外开销

对于频繁搜索的场景，推荐使用map方案，因为它提供了最优的查找性能。如果内存受限且搜索频率不高，可以考虑排序+二分查找的方案。

回到顶部