Как использовать набор в Go

Go

Сегодня поговорим о том, как Go использует set.В этой статье мы рассмотрим две структуры данных: set и bitset.

Примечание. Потребовалось некоторое время, чтобы записать эту тему на видео и проверить ее на станции B.видео.

Структуры данных в Go

В Go не так много встроенных структур данных. В нашей работе чаще всего используются две структуры данных — slice и map, а именно slice и map. На самом деле в Go тоже есть массивы, нижний слой слайсов — это массивы, но из-за существования слайсов мы редко их используем.

В дополнение к встроенным структурам данных Go, существуют также некоторые структуры данных, предоставляемые официальным контейнерным пакетом Go, такие как куча кучи, двусвязный список списка и кольцевой связанный список. Но мы не будем о них сегодня говорить, эти структуры данных будут использоваться опытными пользователями, просто просмотрев документацию.

Сегодня мы поговорим о наборах и битсетах в будущем. Насколько я знаю, некоторые другие языки, такие как Java, имеют обе структуры данных. Но Go в настоящее время недоступен ни в какой форме.

Реализовать идеи

Сначала посмотрите на статью, посетите адрес2 basic set implementationsчитать. В этой статье представлены две идеи реализации set in go, а именно map и bitset.

Если вам интересно, вы можете прочитать эту статью, далее мы подробно расскажем о ней.

map

Мы знаем, что ключ карты должен быть уникальным, а это точно так же, как и характеристики набора, что, естественно, гарантирует уникальность членов набора. Более того, когда 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

Это легче понять, создав map[string]bool для хранения набора строк. Но здесь все еще есть проблема.Значение map имеет логический тип, из-за чего набор будет занимать определенное количество памяти, и у набора не должно быть этой проблемы.

Как решить эту проблему?

Установите значение пустой структуры.В 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

Я видел, как кто-то в Интернете делал упаковку по этой идее раньше, и также написалстатья, вы можете прочитать это.

На самом деле на гитхабе уже есть зрелый пакет под названием golang-set, который также реализован с использованием этой идеи. адресgolang-set, в описании сказано, что Docker тоже его использует. В пакете есть две реализации набора: потокобезопасный набор и не потокобезопасный набор.

Продемонстрируйте простой случай.

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

Продолжайте говорить о наборе битов. Каждое число в наборе битов может быть представлено одним битом. Для числа int8 мы можем использовать его для представления 8 чисел, что может помочь нам значительно сэкономить место для хранения данных.

Наиболее распространенными применениями битового набора являются растровое изображение и флаг, то есть растровое изображение и бит флага. Здесь мы сначала пытаемся использовать его для представления флаговых битов некоторых операций. Например, в определенном сценарии нам нужны три флага для представления разрешения 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))
    }
}

В примере изначально нам нужно было три числа для представления этих трех флагов, но теперь мы можем передать uint8. Некоторые операции с набором битов, такие как установка Set, очистка Clear, переключение Toggle и проверка Has, могут быть реализованы с помощью битовой операции, и это очень эффективно.

bitset имеет естественные преимущества для операций над множествами, которые могут быть реализованы непосредственно через битовые операторы. Такие как пересечение, объединение и разность, примеры следующие:

  • Пересечение: а и б
  • Союз: A | B
  • Разница: а и (~б)

Языки низкого уровня, библиотеки и фреймворки часто используют этот метод для установки флагов.

В приведенном выше примере показано, как обрабатывать небольшой объем данных: uint8 занимает 8 бит пространства и может представлять только 8 чисел. Можно ли использовать эту идею в сценариях с большими данными?

Мы можем объединить набор битов со слайсами в Go и переопределить тип Bits следующим образом:

type Bitset struct {
    data []int64
}

Но это также создаст некоторые проблемы, установить бит, как мы узнаем, где он находится? Если подумать, эта информация о позиции состоит из двух частей, а именно позиции индекса среза числа, которое содержит бит, и бита в числе, именованного индексом и позицией соответственно. Как получить его?

Индекс можно получить целочисленным делением.Например, если мы хотим знать, какой индекс слайса, представляющего 65 бит, находится в слайсе, мы можем получить его с помощью 65 / 64. Если это эффективно, это также может быть достигнуто побитовой операцией, то есть заменой деления на сдвиг, например 65 >> 6, 6 представляет смещение сдвига, то есть n из 2^n = 64.

позиция — это остаток от деления, который мы можем получить с помощью операции по модулю, например, 65 % 64 = 1. Также для эффективности существуют соответствующие битовые операции, такие как 65 и 0b00111111, то есть 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<<uint(n&mask)) != 0
}

func main() {
	set := NewBitSet(65)
	fmt.Println("set contains 65", set.Contains(65))
	fmt.Println("set contains 64", set.Contains(64))
}

выходной результат

set contains 65 true
set contains 64 false

Вышеприведенный пример функции очень прост, просто для демонстрации, только две функции создания набора битов и содержит, другие функции, такие как добавление, удаление, пересечение, объединение и различие между разными наборами битов, не были реализованы. Заинтересованные друзья могут продолжать попытки.

На самом деле пакет bitset тоже реализован, адрес githubbit. Вы можете прочитать его исходный код, и идеи реализации аналогичны описанным выше.

Ниже приведен пример использования.

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

Смысл кода понять несложно, то есть некоторые операции добавления, удаления, модификации, поиска и сбора. Следует отметить, что разница между набором битов и предыдущим набором заключается в том, что элементы набора битов могут быть только целыми числами, что не так гибко, как набор. Обычных сценариев использования также относительно немного, в основном они используются в сценариях с высокими требованиями к эффективности и объему памяти.

Суммировать

В этой статье представлены принципы реализации двух наборов в Go и на этой основе представлено простое использование двух соответствующих им пакетов. Я думаю, что с помощью этой статьи использование set в Go в принципе может быть реализовано.

В дополнение к этим двум пакетам добавьте еще два.zoumo/gosetиGitHub.com/will F/цвет носа….

波罗学的微信公众号

Категории