Kiểm tra xem một lát chuỗi có chứa một giá trị nhất định trong Go

Question

Cách tốt nhất để kiểm tra xem một giá trị nhất định có nằm trong một lát chuỗi không? Tôi sẽ sử dụng một Set bằng ngôn ngữ khác, nhưng Go không có.

thử tốt nhất của tôi là thế này cho đến nay:

package main 

import "fmt" 

func main() { 
    list := []string{"a", "b", "x"} 
    fmt.Println(isValueInList("b", list)) 
    fmt.Println(isValueInList("z", list)) 
} 

func isValueInList(value string, list []string) bool { 
    for _, v := range list { 
     if v == value { 
      return true 
     } 
    } 
    return false 
} 

http://play.golang.org/p/gkwMz5j09n

Giải pháp này nên được ok cho lát nhỏ, nhưng phải làm gì để lát với nhiều yếu tố?

Answer 1

Nếu bạn có một lát chuỗi trong một trật tự tùy ý, việc tìm kiếm nếu một giá trị tồn tại trong lát đòi hỏi O (n) thời gian. Điều này áp dụng cho tất cả các ngôn ngữ.

Nếu bạn có ý định thực hiện tìm kiếm lặp đi lặp lại, bạn có thể sử dụng các cấu trúc dữ liệu khác để thực hiện tra cứu nhanh hơn. Tuy nhiên, việc xây dựng các cấu trúc này đòi hỏi ít nhất thời gian O (n). Vì vậy, bạn sẽ chỉ nhận được lợi ích nếu bạn tra cứu bằng cách sử dụng cấu trúc dữ liệu nhiều lần.

Ví dụ: bạn có thể tải chuỗi của mình vào bản đồ. Sau đó, tra cứu sẽ mất O (1) thời gian. Các lần chèn cũng mất O (1) thời gian để tạo bản dựng ban đầu có thời gian O (n):

set := make(map[string]bool) 
for _, v := range list { 
    set[v] = true 
} 

fmt.Println(set["b"]) 

Bạn cũng có thể sắp xếp lát chuỗi và sau đó thực hiện tìm kiếm nhị phân. Tìm kiếm nhị phân xảy ra trong thời gian O (log (n)). Tòa nhà có thể mất thời gian O (n * log (n)).

sort.Strings(list) 
i := sort.SearchStrings(list, "b") 
fmt.Println(i < len(list) && list[i] == "b") 

Mặc dù trong lý thuyết cho một số lượng vô hạn các giá trị, bản đồ nhanh hơn, trên thực tế rất có khả năng tìm kiếm danh sách được sắp xếp sẽ nhanh hơn. Bạn cần tự chuẩn bị nó.

Answer 2

Để thay thế các bộ, bạn có thể sử dụng map[string]whatever. Điều này sẽ không được nhẹ hơn bạn có thể tưởng tượng (có một con trỏ đến giá trị mà bạn không cần) nhưng ngoài việc viết bảng băm của bạn nó là hiệu quả nhất, và nó khá tối ưu vì nó được xây dựng.

set := make(map[string]uint8) 

Để đưa một mục:

set[item]=1 

Để kiểm tra xem một mục hiện diện:

_, ok = set[item] 

Đây là một thành ngữ phổ biến ở Go. Nếu ok là đúng, thì có mặt. Nếu ok là sai, thì mục đó không có mặt.

Answer 3

Bạn có thể sử dụng bản đồ và có giá trị, ví dụ: một bool

m := map[string] bool {"a":true, "b":true, "x":true} 
if m["a"] { // will be false if "a" is not in the map 
    //it was in the map 
} 

Ngoài ra còn có các gói sort, vì vậy bạn có thể sắp xếp và nhị phân tìm kiếm lát bạn