about blog github
‹
›

01 May 2016
go从已知列表中查找字符串

最近在开发中遇到一个需求，需要查找某个给定的字符串是否属于有效字符串。例如以下字符串都是有效字符串：

"key1" "key2" "key3" "key4" "key5" "key6"

若查找的字符串是key1，存在key1，所以key1是有效字符串，若查找的字符串是key0，不存在key0，所以key0是无效字符串。

我通过4种方式实现，分别如下：

方式一：使用map

将有效的字符串定义成map的key，value都是true，如下：

var validKeyMap = map[string]bool{
    "key1": true,
    "key2": true,
    "key3": true,
    "key4": true,
    "key5": true,
    "key6": true,
}

使用map的特性查找某个键是的值，如下：

key := "key1"
if validKeyMap[key] {
    fmt.Println("found via map")
} else {
    fmt.Println("not found via map")
}

方式二：遍历列表

将有效字符串定义成一个切片，如下：

var validKeyList = []string{
    "key1",
    "key2",
    "key3",
    "key4",
    "key5",
    "key6",
}

通过遍历切片查找特定字符串，如下：

var found bool
key := "key1"
for index := range validKeyList {
    if validKeyList[index] == key {
        found = true
        break
    }
}

if found {
    fmt.Println("found via list")
} else {
    fmt.Println("not found via list")
}

方式三：使用sort库

借助sort库，先将切片排序，然后通过调用SearchStrings查找目标字符串：

sort.Strings(validKeyList)
index := sort.SearchStrings(validKeyList, key)
found = (index < len(validKeyList) && validKeyList[index] == key)

if found {
    fmt.Println("found via sort lib")
} else {
    fmt.Println("not found via sort lib")
}

方式四：使用switch

使用switch语句的特性，遍历所有字符串查找，如下：

key := "key1"

switch key {

    case "key1":
        fallthrough

    case "key2":
        fallthrough

    case "key3":
        fallthrough

    case "key4":
        fallthrough

    case "key5":
        fallthrough

    case "key6":
        fmt.Println("found via switch")
    default:
        fmt.Println("not found via switch")
    }

总结

方式一由于定义一个map，内存相对其他方式有一定的开销，但是该方式查找效率最高，时间复杂度为常数O(1)，所以一般推荐使用；

方式二由于需要遍历所有字符串，时间复杂度是O(N)，N是切片的长度，随着长度增大，查找时间越长，但是相比方式四，代码少了很多，谨记代码越少出错概率越小，要想软件没有bug，唯一的方法就是不写代码；

方式三通过使用go标准库sort，将切片先排序后，使用二分法查找目标字符串，算法复杂读相对方式二和方式四较好，为O(logN)，N为切片长度，可读性较好，比方式二更优，但会改变原切片元素顺序，若对元素顺序敏感慎用；

方式四借助switch语句特性，时间复杂度不定。若查找的字符串是key1，则时间复杂度O(1)，但是若查找的字符串是最后一个字符串时，时间复杂度和方式二一样，都是O(N)，N表示字符串个数，但是该方式没有没有使用任何数据结构，如果对内存开销要求高，可以推荐使用。

附上完整代码

package main

import (
    "fmt"
    "sort"
)

func main() {

    var validKeyList = []string{
        "key1",
        "key2",
        "key3",
        "key4",
        "key5",
        "key6",
    }

    var validKeyMap = map[string]bool{
        "key1": true,
        "key2": true,
        "key3": true,
        "key4": true,
        "key5": true,
        "key6": true,
    }

    key := "key1"
    if validKeyMap[key] {
        fmt.Println("found via map")
    } else {
        fmt.Println("not found via map")
    }

    var found bool
    for index := range validKeyList {

        if validKeyList[index] == key {
            found = true
            break
        }

    }

    if found {
        fmt.Println("found via list")
    } else {
        fmt.Println("not found via list")
    }

    sort.Strings(validKeyList)
    index := sort.SearchStrings(validKeyList, key)
    found = (index < len(validKeyList) && validKeyList[index] == key)

    if found {
        fmt.Println("found via sort lib")
    } else {
        fmt.Println("not found via sort lib")
    }

    switch key {

    case "key1":
        fallthrough

    case "key2":
        fallthrough

    case "key3":
        fallthrough

    case "key4":
        fallthrough

    case "key5":
        fallthrough

    case "key6":
        fmt.Println("found via switch")
    default:
        fmt.Println("not found via switch")
    }
}

输出

found via map
found via list
found via sort lib
found via switch


LEo at 21:20

about blog github