Go資料結構：集合

分析和實現Go語言中的集合資料結構

集合是一組值的集合。您可以對這些值進行迭代，添加新值，刪除值並清除集合，獲取集合大小，以及檢查集合是否包含某個項目。集合中的值可能只會被存儲一次，不允許重複。

第一個實現

這是一個簡單的集合實現，尚未具備並發安全性，為了簡潔和易於理解，並沒有鎖定資源。稍後在本文中將添加鎖定。

請注意第二行，它允許我們通過生成此通用資料結構的特定實現來使用任何類型的集合。

set.go

// 包set為Item類型創建ItemSet資料結構
package set

import "github.com/cheekybits/genny/generic"

// Item 集合的類型
type Item generic.Type

// ItemSet 集合項目的集合
type ItemSet struct {
	items map[Item]bool
}

// Add 向集合中添加新元素。返回集合的指針。
func (s *ItemSet) Add(t Item) *ItemSet {
	if s.items == nil {
		s.items = make(map[Item]bool)
	}
	_, ok := s.items[t]
	if !ok {
		s.items[t] = true
	}
	return s
}

// Clear 從集合中刪除所有元素
func (s *ItemSet) Clear() {
	s.items = make(map[Item]bool)
}

// Delete 從集合中刪除項目並返回有無(項目)
func (s *ItemSet) Delete(item Item) bool {
	_, ok := s.items[item]
	if ok {
		delete(s.items, item)
	}
	return ok
}

// Has 如果集合包含項目，則返回true
func (s *ItemSet) Has(item Item) bool {
	_, ok := s.items[item]
	return ok
}

// Items 返回存儲的項目
func (s *ItemSet) Items() []Item {
	items := []Item{}
	for i := range s.items {
		items = append(items, i)
	}
	return items
}

// Size 返回集合的大小
func (s *ItemSet) Size() int {
	return len(s.items)
}

測試實現

以下是上面的代碼的測試套件，它以詳細方式解釋了如何使用它以及任何操作的預期結果。

set_test.go

package set

import (
	"fmt"
	"testing"
)

func populateSet(count int, start int) *ItemSet {
	set := ItemSet{}
	for i := start; i < (start + count); i++ {
		set.Add(fmt.Sprintf("item%d", i))
	}
	return &set
}

func TestAdd(t *testing.T) {
	set := populateSet(3, 0)
	if size := set.Size(); size != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", size)
	}
	set.Add("item1") //不應該添加，已經存在
	if size := set.Size(); size != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", size)
	}
	set.Add("item4") //不應該添加，已經存在
	if size := set.Size(); size != 4 {
		t.Errorf("錯誤的計數，期望4獲得%d", size)
	}
}

func TestClear(t *testing.T) {
	set := populateSet(3, 0)
	set.Clear()
	if size := set.Size(); size != 0 {
		t.Errorf("錯誤的計數，期望0獲得%d", size)
	}
}

func TestDelete(t *testing.T) {
	set := populateSet(3, 0)
	set.Delete("item2")
	if size := set.Size(); size != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", size)
	}
}

func TestHas(t *testing.T) {
	set := populateSet(3, 0)
	has := set.Has("item2")
	if !has {
		t.Errorf("期望item2存在")
	}
	set.Delete("item2")
	has = set.Has("item2")
	if has {
		t.Errorf("期望item2被刪除")
	}
	set.Delete("item1")
	has = set.Has("item1")
	if has {
		t.Errorf("期望item1被刪除")
	}
}

func TestItems(t *testing.T) {
	set := populateSet(3, 0)
	items := set.Items()
	if len(items) != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", len(items))
	}
	set = populateSet(520, 0)
	items = set.Items()
	if len(items) != 520 {
		t.Errorf("錯誤的計數，期望520獲得%d", len(items))
	}
}

func TestSize(t *testing.T) {
	set := populateSet(3, 0)
	items := set.Items()
	if len(items) != set.Size() {
		t.Errorf("錯誤的計數，期望%d獲得%d", set.Size(), len(items))
	}
	set = populateSet(0, 0)
	items = set.Items()
	if len(items) != set.Size() {
		t.Errorf("錯誤的計數，期望%d獲得%d", set.Size(), len(items))
	}
	set = populateSet(10000, 0)
	items = set.Items()
	if len(items) != set.Size() {
		t.Errorf("錯誤的計數，期望%d獲得%d", set.Size(), len(items))
	}
}

並發安全版本

第一個版本並不安全，因為當另一個程序正在獲取項目或大小時，一個程序可能會向集合中添加一個項目。

以下代碼將sync.RWMutex添加到資料結構中，使其具有並發安全性。上述測試也可以正常運行，而不需要對此實現進行任何修改。

該實現非常簡單，我們可以在結構中添加鎖定並使用defer解鎖。由於我們將為可能有多個相同文件中的特定實現生成代碼，因此我們需要將鎖定添加到結構中，或將通用類型添加到鎖定名稱(Itemlock)中。我選擇了第一個選項：

set.go

// 包set為Item類型創建ItemSet資料結構
package set

import (
	"sync"

	"github.com/cheekybits/genny/generic"
)

// Item 集合的類型
type Item generic.Type

// ItemSet 集合項目的集合
type ItemSet struct {
	items map[Item]bool
	lock  sync.RWMutex
}

// Add 向集合中添加新元素。返回集合的指針。
func (s *ItemSet) Add(t Item) *ItemSet {
	s.lock.Lock()
	defer s.lock.Unlock()
	if s.items == nil {
		s.items = make(map[Item]bool)
	}
	_, ok := s.items[t]
	if !ok {
		s.items[t] = true
	}
	return s
}

// Clear 從集合中刪除所有元素
func (s *ItemSet) Clear() {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = make(map[Item]bool)
}

// Delete 從集合中刪除項目並返回Has(string)
func (s *ItemSet) Delete(item Item) bool {
	s.lock.Lock()
	defer s.lock.Unlock()
	_, ok := s.items[item]
	if ok {
		delete(s.items, item)
	}
	return ok
}

// Has 如果集合包含項目，則返回true
func (s *ItemSet) Has(item Item) bool {
	s.lock.RLock()
	defer s.lock.RUnlock()
	_, ok := s.items[item]
	return ok
}

// Items 返回存儲的項目
func (s *ItemSet) Items() []Item {
	s.lock.RLock()
	defer s.lock.RUnlock()
	items := []Item{}
	for i := range s.items {
		items = append(items, i)
	}
	return items
}

// Size 返回集合的大小
func (s *ItemSet) Size() int {
	s.lock.RLock()
	defer s.lock.RUnlock()
	return len(s.items)
}

創建具體的集合資料結構

首先，如果尚未安裝genny，請先進行安裝。

運行以下命令：

//生成字符串的StringSet集合
genny -in set.go -out set-string.go gen "Iten=string Value=int"

//生成int的IntSet集合
genny -in set.go -out set-int.go gen "Item=int"

這是set-string.go生成文件的示例：

// This file was automatically generated by genny.
// Any changes will be lost if this file is regenerated.
// see https://github.com/cheekybits/genny

// Package set creates a StringSet data structure for the string type
package set

import "sync"

// StringSet the set of Strings
type StringSet struct {
	items map[string]bool
	lock  sync.RWMutex
}

// Add adds a new element to the Set. Returns a pointer to the Set.
func (s *StringSet) Add(t string) *StringSet {
	s.lock.Lock()
	defer s.lock.Unlock()
	if s.items == nil {
		s.items = make(map[string]bool)
	}
	_, ok := s.items[t]
	if !ok {
		s.items[t] = true
	}
	return s
}

// Clear removes all elements from the Set
func (s *StringSet) Clear() {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = make(map[string]bool)
}

// Delete removes the string from the Set and returns Has(string)
func (s *StringSet) Delete(item string) bool {
	s.lock.Lock()
	defer s.lock.Unlock()
	_, ok := s.items[item]
	if ok {
		delete(s.items, item)
	}
	return ok
}

// Has returns true if the Set contains the string
func (s *StringSet) Has(item string) bool {
	s.lock.RLock()
	defer s.lock.RUnlock()
	_, ok := s.items[item]
	return ok
}

// Strings returns the string(s) stored
func (s *StringSet) Strings() []string {
	s.lock.RLock()
	defer s.lock.RUnlock()
	items := []string{}
	for i := range s.items {
		items = append(items, i)
	}
	return items
}

// Size returns the size of the set
func (s *StringSet) Size() int {
	s.lock.RLock()
	defer s.lock.RUnlock()
	return len(s.items)
}

// Package set creates a IntSet data structure for the int type

// IntSet the set of Ints
type IntSet struct {
	items map[int]bool
	lock  sync.RWMutex
}

// Add adds a new element to the Set. Returns a pointer to the Set.
func (s *IntSet) Add(t int) *IntSet {
	s.lock.Lock()
	defer s.lock.Unlock()
	if s.items == nil {
		s.items = make(map[int]bool)
	}
	_, ok := s.items[t]
	if !ok {
		s.items[t] = true
	}
	return s
}

// Clear removes all elements from the Set
func (s *IntSet) Clear() {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = make(map[int]bool)
}

// Delete removes the int from the Set and returns Has(int)
func (s *IntSet) Delete(item int) bool {
	s.lock.Lock()
	defer s.lock.Unlock()
	_, ok := s.items[item]
	if ok {
		delete(s.items, item)
	}
	return ok
}

// Has returns true if the Set contains the int
func (s *IntSet) Has(item int) bool {
	s.lock.RLock()
	defer s.lock.RUnlock()
	_, ok := s.items[item]
	return ok
}

// Ints returns the int(s) stored
func (s *IntSet) Ints() []int {
	s.lock.RLock()
	defer s.lock.RUnlock()
	items := []int{}
	for i := range s.items {
		items = append(items, i)
	}
	return items
}

// Size returns the size of the set
func (s *IntSet) Size() int {
	s.lock.RLock()
	defer s.lock.RUnlock()
	return len(s.items)
}

添加更多集合操作

現在，我們的集合是一個有趣的資料結構，但通過實現一些常見的數學集合操作，可以更加完善它：聯合，交集，差集和子集。

聯合

// Union返回一個新集合，其中包含來自給定兩個集合的元素
func (s *ItemSet) Union(s2 *ItemSet) *ItemSet {
	s3 := ItemSet{}
	s3.items = make(map[Item]bool)
	s.lock.RLock()
	for i := range s.items {
		s3.items[i] = true
	}
	s.lock.RUnlock()
	s2.lock.RLock()
	for i := range s2.items {
		_, ok := s3.items[i]
		if !ok {
			s3.items[i] = true
		}
	}
	s2.lock.RUnlock()
	return &s3
}

測試

func TestUnion(t *testing.T) {
	set1 := populateSet(3, 0)
	set2 := populateSet(2, 3)
	
	set3 := set1.Union(set2)
	
	if len(set3.Items()) != 5 {
		t.Errorf("錯誤的計數，期望5獲得%d", set3.Size())
	}
	//不要編輯原始集合
	if len(set1.Items()) != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", set1.Size())
	}
	if len(set2.Items()) != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", set2.Size())
	}
}

交集

// Intersection返回一個新集合，其中僅包含存在於兩個集合中的元素
func (s *ItemSet) Intersection(s2 *ItemSet) *ItemSet {
	s3 := ItemSet{}
	s3.items = make(map[Item]bool)
	s.lock.RLock()
	s2.lock.RLock()
	defer s.lock.RUnlock()
	defer s2.lock.RUnlock()
	for i := range s2.items {
		_, ok := s.items[i]
		if ok {
			s3.items[i] = true
		}
	}
	return &s3
}

測試

func TestIntersection(t *testing.T) {
	set1 := populateSet(3, 0)
	set2 := populateSet(2, 0)

	set3 := set1.Intersection(set2)

	if len(set3.Items()) != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", set3.Size())
	}
	//不要編輯原始集合
	if len(set1.Items()) != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", set1.Size())
	}
	if len(set2.Items()) != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", set2.Size())
	}
}

差集

// Difference返回耳機新集合，其中為存在於第一個集合中且不存在於第二個集合中的元素
func (s *ItemSet) Difference(s2 *ItemSet) *ItemSet {
	s3 := ItemSet{}
	s3.items = make(map[Item]bool)
	s.lock.RLock()
	s2.lock.RLock()
	defer s.lock.RUnlock()
	defer s2.lock.RUnlock()
	for i := range s.items {
		_, ok := s2.items[i]
		if !ok {
			s3.items[i] = true
		}
	}
	return &s3
}

測試

func TestDifference(t *testing.T) {
	set1 := populateSet(3, 0)
	set2 := populateSet(2, 0)

	set3 := set1.Difference(set2)

	if len(set3.Items()) != 1 {
		t.Errorf("錯誤的計數，期望2獲得%d", set3.Size())
	}
	//不要編輯原始集合
	if len(set1.Items()) != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", set1.Size())
	}
	if len(set2.Items()) != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", set2.Size())
	}
}

子集

// Subset如果s2是s的子集則返回true
func (s *ItemSet) Subset(s2 *ItemSet) bool {
	s.lock.RLock()
	s2.lock.RLock()
	defer s.lock.RUnlock()
	defer s2.lock.RUnlock()
	for i := range s.items {
		_, ok := s2.items[i]
		if !ok {
			return false
		}
	}
	return true
}

測試

func TestSubset(t *testing.T) {
	set1 := populateSet(3, 0)
	set2 := populateSet(2, 0)

	if set1.Subset(set2) {
		t.Errorf("期望false實際true")
	}

	//不要編輯原始集合
	if len(set1.Items()) != 3 {
		t.Errorf("錯誤的計數，期望3獲得%d", set1.Size())
	}
	if len(set2.Items()) != 2 {
		t.Errorf("錯誤的計數，期望2獲得%d", set2.Size())
	}

	//嘗試真正的子集
	set1 = populateSet(2, 0)
	if !set1.Subset(set2) {
		t.Errorf("期望true實際false")
	}

	set1 = populateSet(1, 0)
	if !set1.Subset(set2) {
		t.Errorf("期望true實際false")
	}
}