Go 작은 지식의 Go 에서 set 를 어떻게 사용 하 는 지

본문 선발
내 블 로그 잘 썼 다 고 생각하면 좋아요 눌 러 서 더 많은 친구 들 이 볼 수 있 게 해 주세요.
오늘 은 Go 가 set 를 어떻게 사용 하 는 지 에 대해 이야기 하 겠 습 니 다. 본 고 는 set 와 bitset 두 가지 데이터 구 조 를 다 룰 것 입 니 다.
Go 의 데이터 구조
Go 에 내 장 된 데이터 구 조 는 많 지 않 습 니 다.작업 중 에 우리 가 가장 자주 사용 하 는 두 가지 데이터 구 조 는 각각 slice 와 map, 즉 절편 과 맵 이다.사실 Go 에 도 배열 이 있 는데 절편 의 밑부분 은 바로 배열 이다. 단지 절편 이 존재 하기 때문에 우 리 는 평소에 그것 을 거의 사용 하지 않 는 다.
Go 에 내 장 된 데이터 구 조 를 제외 하고 일부 데이터 구 조 는 Go 의 공식 container 패키지 에서 제공 합 니 다. 예 를 들 어 힙 더미, list 양 방향 링크 와 ring 루프 링크 등 입 니 다.그러나 오늘 우 리 는 그것들 을 말 하지 않 는 다. 이런 데이터 구 조 는 숙련자 에 게 문 서 를 보면 사용 할 것 이다.
우리 가 오늘 이야기 할 것 은 set 와 bitset 이다.내 가 알 기 로 는 자바 와 같은 다른 언어 들 은 이 두 가지 데이터 구조 가 있다.그러나 고 는 아직 어떤 형태 로 도 제공 되 지 않 았 다.
사고의 방향 을 실현 하 다.
먼저 글 한 편 을 보고 주소 2 basic set implementations 를 방문 하여 읽 습 니 다.글 에서 두 가지 go 가 set 를 실현 하 는 사고방식 을 소 개 했 는데 그것 이 바로 맵 과 bitset 이다.
관심 이 있 으 면 이 글 을 읽 어도 됩 니 다. 우 리 는 이어서 구체 적 으로 소개 하 겠 습 니 다.
map
우 리 는 map 의 key 가 유일한 것 임 을 알 고 있 습 니 다. 이것 은 set 의 특성 과 일치 하고 set 의 구성원 의 유일 성 을 천연 적 으로 보장 합 니 다.또한 맵 을 통 해 set 를 실현 하여 특정한 요소 가 존재 하 는 지 확인 할 때 를 직접 사용 할 수 있 습 니 다.ok: = m [key] 의 문법 은 효율 이 높다.
먼저 간단 한 실현 을 살 펴 보 자. 다음 과 같다.

set := make(map[string]bool) // New empty set
set["Foo"] = true            // Add
for k := range set {         // Loop
    fmt.Println(k)
}
delete(set, "Foo")    // Delete
size := len(set)      // Size
exists := set["Foo"]  // Membership

맵 [string] bool 을 만들어 string 의 집합 을 저장 하면 이해 하기 쉽다.그러나 여기에 또 하나의 문제 가 있 습 니 다. map 의 value 는 불 형식 입 니 다. 이 로 인해 set 는 일정한 메모리 공간 을 많이 차지 할 수 있 습 니 다. set 는 이 문제 가 있어 서 는 안 됩 니 다.
이 문 제 를 어떻게 해결 합 니까?
value 를 빈 구조 체 로 설정 합 니 다. Go 에 서 는 빈 구조 체 가 메모리 에서 차지 하지 않 습 니 다.물론 확실 하지 않 으 면 이 결론 을 증명 할 수도 있다.

unsafe.Sizeof(struct{}{}) //     0

최 적 화 된 코드 는 다음 과 같다.

type void struct{}
var member void

set := make(map[string]void) // New empty set
set["Foo"] = member          // Add
for k := range set {         // Loop
    fmt.Println(k)
}
delete(set, "Foo")      // Delete
size := len(set)        // Size
_, exists := set["Foo"] // Membership

전에 인터넷 에서 누군가가 이 생각 에 따라 포장 을 한 것 을 보 았 고 한 편의 문장 도 썼 으 니 읽 어 보 세 요.
사실 github 에는 이미 성숙 한 가방 이 있 는데 이름 은 golang - set 이 고 이 사고방식 으로 이 루어 진 것 이다.방문 주소 golang-set, 설명 에서 Docker 가 사용 하 는 것 도 그것 입 니 다.가방 에 두 가지 set 실현, 스 레 드 안전 set 와 비 스 레 드 안전 set 를 제공 합 니 다.
간단 한 사례 를 시범 하 다.

package main

import (
    "fmt"

    mapset "github.com/deckarep/golang-set"
)

func main() {
    //           ，        
    //      NewThreadUnsafeSet   ，         。
    s1 := mapset.NewSet(1, 2, 3, 4)  
    fmt.Println("s1 contains 3: ", s1.Contains(3))
    fmt.Println("s1 contains 5: ", s1.Contains(5))

    // interface   ，        
    s1.Add("poloxue")
    fmt.Println("s1 contains poloxue: ", s1.Contains("poloxue"))
    s1.Remove(3)
    fmt.Println("s1 contains 3: ", s1.Contains(3))

    s2 := mapset.NewSet(1, 3, 4, 5)

    //   
    fmt.Println(s1.Union(s2))
}

출력 은 다음 과 같 습 니 다:

s1 contains 3:  true
s1 contains 5:  false
s1 contains poloxue:  true
s1 contains 3:  false
Set{4, polxue, 1, 2, 3, 5}

예 를 들 어 간단 한 사용 방식 을 보 여 주 었 다. 만약 에 모 르 는 것 이 있 으 면 소스 코드 를 보면 이런 데이터 구조의 조작 방법 명 은 모두 흔히 볼 수 있다. 예 를 들 어 교차 Intersect, 차 집 Difference 등 은 한눈 에 알 수 있다.
bitset
bitset 에 대해 계속 이야기 하 세 요. bitset 에서 모든 숫자 는 하나의 bit 로 표시 할 수 있 습 니 다. int8 의 숫자 에 대해 우 리 는 8 개의 숫자 를 표시 할 수 있 고 데이터 의 저장 공간 을 크게 절약 할 수 있 습 니 다.
bitset 에서 가장 흔히 볼 수 있 는 응용 프로그램 은 bitmap 와 flag, 즉 비트 맵 과 표지 판이 있 습 니 다.여기 서, 우 리 는 먼저 그것 으로 조작의 표지 위 치 를 표시 하려 고 시도 한다.예 를 들 어 특정한 장면 에서 우 리 는 세 개의 flag 가 각각 권한 1, 권한 2 와 권한 3 을 나타 내 고 몇 개의 권한 이 공존 할 수 있 습 니 다.우 리 는 각각 세 개의 상수 F1, F2, F3 로 위 치 를 표시 할 수 있다.
예제 코드 는 다음 과 같 습 니 다 (문장 참조 Bitmasks, bitsets and flags.

type Bits uint8

const (
    F0 Bits = 1 << iota
    F1
    F2
)

func Set(b, flag Bits) Bits    { return b | flag }
func Clear(b, flag Bits) Bits  { return b &^ flag }
func Toggle(b, flag Bits) Bits { return b ^ flag }
func Has(b, flag Bits) bool    { return b&flag != 0 }

func main() {
    var b Bits
    b = Set(b, F0)
    b = Toggle(b, F2)
    for i, flag := range []Bits{F0, F1, F2} {
        fmt.Println(i, Has(b, flag))
    }
}

예 에서 우 리 는 원래 세 개의 숫자 가 있어 야만 이 세 개의 표 지 를 표시 할 수 있 지만, 지금 은 하나의 uint 8 을 통과 하면 된다.bitset 의 일부 조작, 예 를 들 어 Set 설정, Clear 제거, Toggle 전환, Has 검사 가 비트 연산 을 통 해 이 루어 질 수 있 고 매우 효율 적 입 니 다.
bitset 는 집합 작업 에 천연 적 인 장점 을 가지 고 비트 연산 자 를 통 해 직접 실현 할 수 있 습 니 다.예 를 들 어 교 집, 병 집, 차 집 등 은 다음 과 같다.

교 집합: a & b

병 집: a | b

차 집: a & (~ b)

밑바닥 의 언어, 라 이브 러 리, 프레임 워 크 는 항상 이런 방식 으로 표지 위 치 를 설정한다.
이상 의 예 에서 소량의 데이터 처리 방식 만 보 여 주 었 고 uint 8 은 8 bit 공간 을 차지 하 며 8 개의 숫자 만 표시 할 수 있 습 니 다.그럼 빅 데이터 장면 은 이 아 이 디 어 를 사용 할 수 있 습 니까?
우 리 는 bitset 와 Go 의 절편 을 결합 하여 Bits 유형 을 다시 정의 할 수 있 습 니 다. 다음 과 같 습 니 다.

type Bitset struct {
    data []int64
}

그러나 이렇게 하면 문제 가 생 길 수 있 습 니 다. bit 를 설정 하면 어디 에 있 는 지 어떻게 알 수 있 습 니까?자세히 생각해 보면 이 위치 정 보 는 두 부분 을 포함 하고 있 습 니 다. 즉, 이 bit 의 수 를 절편 색인 위치 와 이 bit 가 숫자 에 있 는 어느 위치 에 저장 하고 각각 index 와 position 이 라 고 부 릅 니 다.그럼 어떻게 구 해요?
index 는 정 제 를 통 해 얻 을 수 있 습 니 다. 예 를 들 어 우 리 는 65 의 bit 가 절편 에 있 는 어떤 index 를 나타 내 는 지 알 고 싶 습 니 다. 65/64 를 통 해 얻 을 수 있 습 니 다. 효율 적 이면 비트 연산 으로 이 루어 질 수 있 습 니 다. 즉, 65 > 6, 6 은 자리 이동, 즉 2 ^ n = 64 의 n 을 바 꿀 수 있 습 니 다.
postion 은 나눗셈 의 나머지 이다. 우 리 는 모 연산 을 통 해 얻 을 수 있다. 예 를 들 어 65% 64 = 1 은 효율 을 위해 서도 해당 하 는 비트 연산 이 실현 된다. 예 를 들 어 65 & 0b 00111111, 즉 65 & 63 이다.
간단 한 예 는 다음 과 같다.

package main

import (
    "fmt"
)

const (
    shift = 6
    mask  = 0x3f //  0b00111111
)

type Bitset struct {
    data []int64
}

func NewBitSet(n int) *Bitset {
    //       
    index := n >> shift

    set := &Bitset{
        data: make([]int64, index+1),
    }

    //    n    bitset
    set.data[index] |= 1 << uint(n&mask)

    return set
}

func (set *Bitset) Contains(n int) bool {
    //       
    index := n >> shift
    return set.data[index]&(1<

출력 결과

set contains 65 true
set contains 64 false

이상 의 예 기능 은 매우 간단 합 니 다. 단지 프레젠테이션 을 위해 bitset 와 contains 두 가지 기능 을 만 들 었 을 뿐 추가, 삭제, 서로 다른 bitset 간 의 교차, 그리고 차 이 는 아직 실현 되 지 않 았 습 니 다.관심 있 는 친 구 는 계속 시도 해 볼 수 있다.
사실 bitset 패키지 도 'github 주소 bit' 를 실현 했다.그것 의 소스 코드 를 읽 을 수 있 고 사고 와 위의 소개 가 많 지 않다.
다음은 사용 사례 다.

package main

import (
    "fmt"

    "github.com/yourbasic/bit"
)

func main() {
    s := bit.New(2, 3, 4, 65, 128)
    fmt.Println("s contains 65", s.Contains(65))
    fmt.Println("s contains 15", s.Contains(15))

    s.Add(15)
    fmt.Println("s contains 15", s.Contains(15))

    fmt.Println("next 20 is ", s.Next(20))
    fmt.Println("prev 20 is ", s.Prev(20))

    s2 := bit.New(10, 22, 30)

    s3 := s.Or(s2)
    fmt.Println("next 20 is ", s3.Next(20))

    s3.Visit(func(n int) bool {
        fmt.Println(n)
        return false  //    true       
    })
}

실행 결과:

s contains 65 true
s contains 15 false
s contains 15 true
next 20 is 65
prev 20 is 15
next 20 is 22
2
3
4
10
15
22
30
65
128

코드 의 뜻 은 잘 이해 되 는데, 바로 추가 삭제 와 검사 와 집합 작업 이다.주의해 야 할 것 은 bitset 와 앞의 set 의 차이 점 입 니 다. bitset 의 구성원 은 int 정형 일 뿐 set 유연성 이 없습니다.평소에 사용 하 는 장면 도 비교적 적 고 주로 효율 과 저장 공간 에 대한 요구 가 높 은 장면 에 사용 된다.
총결산
본 고 는 Go 에서 두 가지 set 의 실현 원 리 를 소개 하고 이 를 바탕 으로 이들 에 대응 하 는 두 개의 가방 을 간단하게 사용 하 는 것 을 소개 했다.나 는 이 글 을 통 해 Go 에서 set 의 사용 은 기본적으로 모두 해결 할 수 있다 고 생각한다.
이 두 개의 가방 을 제외 하고 두 개 를 더 보충한다. zoumo/goset 와 github.com/willf/bitset.