hashset 대신 golang 성능 최적화 bitset

3975 단어
hashset 은 매우 효율 적 인 데이터 구조 로 삽입 과 조회 의 복잡 도 는 모두 O (1) 로 대부분 장면 의 성능 수 요 를 만족 시 킬 수 있 지만 일부 특수 한 장면 에서 빈도 가 매우 높 은 호출 은 성능 병목 (pprof 분석) 이 될 수 있다. 예 를 들 어 광고 안의 방향 논리, 한 번 의 요청 에서 여과 논 리 는 수천 번 실 행 될 수 있다.그 중에서 일부 여과 은 모두 매 거 진 값 이다. 예 를 들 어 성별 방향, 연령 방향 등 이다. 이런 매 거 진 값 에 대해 bitset 로 최적화 할 수 있 고 20 여 배의 성능 을 향상 시 킬 수 있다.
bitset 의 본질 도 hashset 입 니 다. 다만 해시 통 은 uint 64 로 표 시 했 습 니 다. uint 64 의 모든 사람 은 하나의 요소 가 존재 하 는 지 여 부 를 나타 내 는 데 사 용 됩 니 다. 1 에 존재 하 는 지, 0 에 존재 하지 않 는 지, 삽입 과 조회 작업 은 비트 연산 이 됩 니 다.
bitset 구현
bitset 의 실현 이 비교적 쉽 습 니 다. 다음은 매 거 진 값 만 64 를 초과 하지 않 는 버 전 입 니 다. 물론 임의의 길이 로 확장 할 수 있 습 니 다. uint 64 배열 을 hash 통 으로 사용 하면 됩 니 다.
type BitSet struct {
    bit uint64
}

func (bs *BitSet) Add(i uint64) {
    bs.bit |= 1 << i
}

func (bs *BitSet) Del(i uint64) {
    bs.bit &= ^(1 << i)
}

func (bs BitSet) Has(i uint64) bool {
    return bs.bit&(1< 0
}

성능 테스트
func BenchmarkSetContains(b *testing.B) {
    bitset := NewBitSet()
    hashset := map[uint64]struct{}{}
    for _, i := range []uint64{1, 2, 4, 10} {
        bitset.Add(i)
        hashset[i] = struct{}{}
    }

    b.Run("bitset", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            for i := uint64(0); i < uint64(10); i++ {
                _ = bitset.Has(i)
            }
        }
    })

    b.Run("hashset", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            for i := uint64(0); i < uint64(10); i++ {
                _, _ = hashset[i]
            }
        }
    })
}
BenchmarkSetContains/bitset-8           500000000            3.81 ns/op        0 B/op          0 allocs/op
BenchmarkSetContains/hashset-8          20000000            89.4 ns/op         0 B/op          0 allocs/op

bitset 가 hashset 보다 20 배 이상 성능 이 향상 되 었 음 을 볼 수 있 습 니 다.
참조 링크
코드 주소:https://github.com/hatlonely/easygolang/blob/master/datastruct/bitset.go
전재 출처 본문 링크 를 밝 혀 주 십시오.http://www.hatlonely.com/2018/04/12/golang-성능 최적화 비트 셋 - 대체 - set /
자바 소스 코드 분석 차단 대기 열 Array BlockingQueue 기능 안내
Inner join, Outer join

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage