foo := []string{"foo","bar","FoO","baR"}
sayIfExists("baR") //func(string)bool
Can anyone make the sayIfExists() function with the highest efficiency?
for _,v := range foo {
if givenStr == v {
return true
}
}
this example is not efficient.because if I search the last value, it need to loop through the whole slice.
And it’s too bad for a very large dataset.
Any better idea?
If the slice has no order, then you are stuck with linear search, which is O(n). If it is sorted, you can do it in O(log(n)) with a binary search. That’s assuming you have no decision over the data structure and how it gets populated.
use sort package
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 {
// match
} else {
// not match
}
}
the best way, use map, go map implement by hash table, it have O(1) time complexity
foo = map[string]struct{}{"foo":struct{}{}, "bar":struct{}{}, "FoO": struct{}{}, "baR": struct{}{}}
_, ok:= foo["baR"]
// process
But the hash has to be calculated. Most efficient version, especially if the set is dynamic, a prefix tree might be the most efficient thing, runtime at least.
It’s runtime depends on the length of the word to search. It’s memory overhead might be more than gos native maps though…
yes, prefix tree is better than hash when data is dynamic
Go maps are not O(1).