deckarep / golang-set Goto Github PK
View Code? Open in Web Editor NEWA simple, battle-tested and generic set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.
License: Other
A simple, battle-tested and generic set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.
License: Other
The interview question url is:https://zhuanlan.zhihu.com/p/26972862
The title is 9、下面的迭代会有什么问题?
Your code url is :
https://github.com/deckarep/golang-set/blob/master/threadsafe.go#L154
I think that code is right, no bug. So what you opinion?
The internals of this library use a downcast of the Set interface to *threadSafeSet
and *threadUnsafeSet
everywhere. I'm unclear why an interface is used in this package when the logic panics if you use literally any implementation of the interface other than one that matches the type of set you requested.
For example:
https://github.com/deckarep/golang-set/blob/main/threadsafe.go#L88
Right now, the API is suggesting that any implementation of the Set interface is acceptable (that's what an interface means), but that's not true. In fact, once you have two Sets returned from this package, you can't even tell if they are compatible or if they'll panic when you try to use methods of one on the other.
s1 := mapset.NewSet[int]()
s1.Add(1)
s2 := mapset.NewThreadUnsafeSet[int]()
s2.Add(2)
s1.Union(s2) // compiles, but panics at runtime
My suggestion is instead to simply return structs for both the threadsafe and unsafe versions. The Set interface is not giving the package any benefit, and indeed, there is actually a negative to its existence, since the two types are incompatible (as are any third-party implementations). If they each just were structs and the arguments you pass to Union etc were structs, there would be compile-time safety that ensures you don't pass in a struct that the code doesn't work with.
threadSafeSet.SymmetricDifference doesn't lock any set, it is thread unsafe.
like java equals
method of Object class
It might be useful to add a set implementation which is thread-safe. It'd be trivially simple. You'd make something like the following changes:
I'd be happy to make this changes and submit a pull request if you'd like. I figured I'd consult you on what you thought about the changes before I did, though.
First of all, this suggestion would be a breaking change.
You could separate your concerns better if you implemented the thread-safe mutex code as a decorator for another Set
. Then your core implementation would only need the thread-unsafe version. A new a mapset.ThreadSafe(Set)
function would be added to the API.
The two advantages are
Set
implementations outside of yours need only provide a thread-unsafe implementation. The mutex decorator I am proposing would make it easy to get thread-safe versions of any implementation.mapset.NewSet()
and mapset.NewSetFromSlice([]interface)
functions would normally return the thread-unsafe flavour and the new mapset.ThreadSafe(Set)
function would be used to wrap the result.There would be a tiny performance reduction, but the greater clarity and generality would be worth it.
Hey, I am trying to use elements of a set individually on different go routines using Iterator. But facing a weird issue. When using a go routine for each element, the value duplicates (or skips a value?). Have a look at the example below:
package main
import (
"fmt"
"github.com/deckarep/golang-set"
)
func main() {
set := mapset.NewSet()
set.Add("one")
set.Add("two")
set.Add("three")
set.Add("three")
set.Add("four")
set.Add("five")
set.Add("five")
fmt.Println(set)
iterator := set.Iterator()
fmt.Println("\nIndividual elements are:")
for ele := range iterator.C {
go func() {
fmt.Println(ele)
}()
}
}
The output looks like this:
Set{one, two, three, four, five}
Individual elements are:
two
two
four
five
I do see the set has unique elements in it. But on iterating and reading elements on different goroutines, it does not work as expected. Elements one, three are missing and two appears twice.
Am I missing something? Or using go routines inappropriately?
Thanks
type HashSet4String struct {
set mapset.Set
}
func NewHashSet4String() *HashSet4String {
var result HashSet4String
result.set = mapset.NewSet()
return &result
}
func (s *HashSet4String) Contains(items ...interface{}) bool {
return s.set.Contains(items)
}
My Contains function will crash, why? Thank you!
Hello,
Could you please tag v1 so that I can import a stable version of this code using http://labix.org/gopkg.in
Should be as simple as:
git tag v1
git push --tags
Thanks!
Xavier
I realise it is not intended for use at this point, but thought it might be useful to bring to your attention.
The generics branch works great on go1.18beta1 & go1.18beta2
But on go1.18rc1, it has these errors:
# github.com/deckarep/golang-set
./set.go:169:17: any does not implement comparable
./set.go:172:37: any does not implement comparable
./threadsafe.go:230:43: any does not implement comparable
./threadsafe.go:232:55: any does not implement comparable
./threadsafe.go:235:24: any does not implement comparable
./threadsafe.go:237:44: any does not implement comparable
./threadsafe.go:238:26: any does not implement comparable
./threadsafe.go:249:63: any does not implement comparable
./threadsafe.go:255:72: any does not implement comparable
./threadsafe.go:256:24: any does not implement comparable
./threadsafe.go:256:24: too many errors
I think this is as a consequence of golang/go#50646 (reference)
I've had a good look at it, and made some adjustments which seem to resolve most of it. But I wasn't able to find a way to get PowerSet
working
For Pop
:
func (s *threadUnsafeSet[T]) Pop() (v T, ok bool) {
for item := range *s {
delete(*s, item)
return item, true
}
return
}
(Though this does require a change to the method signature - an alternative might be to introduce a new method and return the zero value on the old one, or to return a pointer)
Edit: For CartesianProduct
, your intended code still seems to have the same problem
For PowerSet
, the problem is that it won't allow Set[Set[T]]
(Set[T] does not implement comparable), and the interface cannot be declared as comparable (interface is (or embeds) comparable)
Perhaps an alternative might be to return []Set[T]
(?)
would be nice to be able to serialize to a json array and back.
In order to loop (for loop) over a Set, I need to prior use the ToSlice()
method.
I was wondering why is that? Why not simply allow to loop over the Set instance?
It would be really valuable if this set type implemented the BurntSushi TextUnmarshaler
interface, so it can be used with that library without needing to wrap the set (or fork the repo)
Hey,
I wanted to use your package and started to read documentation, but I couldn't find the complexity of operations on it. From my previous experience the access operation (Contains) should take O(log(n)) by using something like radix index. Instead it turned out O(n) as it seems you just iterate through all items.
Could you please document in the readme approximate cost of each operation? Thank you!
I've been watching this repo waiting for a tag to be cut for the new generic-based code.
Today I finally realized that a version was cut nearly a week ago... but I never saw it because https://github.com/deckarep/golang-set/releases points to v1.7.1
However, the newest released tag is actually https://github.com/deckarep/golang-set/releases/tag/v2.1.0
Can you update that latest release to show v2.1.0
as the latest?
That will also likely cut down on folks reporting bugs against the v1 series, not realizing they should switch to the v2 series...
Hello I'm new to Go and your library.
Consider the following code:
package main
import (
"fmt"
set "github.com/deckarep/golang-set"
)
func main() {
s1 := set.NewSet()
s2 := set.NewSet()
s1.Add(1)
s1.Add(2)
s2.Add(1)
s2.Add(2)
parent := set.NewSet()
parent.Add(s1)
parent.Add(s2)
fmt.Println(parent)
}
It outputs:
Set{Set{1, 2}, Set{1, 2}}
Is it possible, for the parent set to recognize that
s1 and s2 are having the same content and
add only one?
Thanks
Let's say i'v a Set, i want to cycle all the elements in this set and ask the user to select which element remove from the set, the problem now is that if you try to remove the element with myset.Remove(element)
in the cycle it will hang (probably because you cant iterate the elements and remove them in the same time).
mySet := mapsetNewSet()
//fill set with stuff
myIt := mySet.Iterator()
scanner := bufio.NewScanner(os.Stdin)
for stuff := range myIt.C {
fmt.Println("Found " + stuff.(string) + " remove it?[Y/n]")
scanner.Scan()
text := scanner.Text()
if text == "y" || text == "Y" {
fmt.Println("removing")
mySet.Remove(stuff) //this will hang
fmt.Println("done")
}
}
One solution is to create another Set and filling it with the value from the cycle and after the end of cycle use myset.Difference(OtherSet)
but i don't want to create another set just for this, do you have another solution more efficient than this
EDIT: as i can see, you can't add stuff to a set while you are iterating another set, still will hang
mySet := mapsetNewSet()
diffSet := mapsetNewSet()
//fill set with stuff
myIt := mySet.Iterator()
scanner := bufio.NewScanner(os.Stdin)
for stuff := range myIt.C {
fmt.Println("Found " + stuff.(string) + " remove it?[Y/n]")
scanner.Scan()
text := scanner.Text()
if text == "y" || text == "Y" {
fmt.Println("removing")
diffSet.Add(stuff) //this will hang too
fmt.Println("done")
}
}
mySet := mySet.Difference(diffSet)
How is NewSet
different from NewSetWith
?
Lines 178 to 180 in 645e1ba
Lines 188 to 190 in 645e1ba
According to NewSet
's documentation, it returns reference to an empty set. But that's not true. It returns reference to a set with all the items passed in parameters.
That's exactly what NewSetWith
does. So how are they different?
Am i missing something here?
I think the IsSubset
doc is backwards it states :
// Determines if every element in the other set
// is in this set.
//
// Note that the argument to IsSubset
// must be of the same type as the receiver
// of the method. Otherwise, IsSubset will
// panic.
IsSubset(other Set) bool
It seems to be backwards from how it actually functions, this is probably what it should say :
Determines if every element in this set is in the other set.
I can create sets of sets, but the information that the contents are sets is lost somehow.
something := mapset.NewSet()
something.Add("anything")
rules := mapset.NewSet()
rules.Add(something)
c := rules.Iter()
for item := range c {
fmt.Println(item)
fmt.Println(item.Cardinality())
...
gives me
item.Cardinality undefined (type interface {} has no field or method Cardinality)
i create a set with golang-set/v2 and try to range over it use Iterator() function,which source code tells me that
// Returns an Iterator object that you can
// use to range over the set.
Iterator() *Iterator[T]
but i write this code and it doesn't work for me,
func TestSet(t *testing.T) {
vSet := set.NewSet[string]()
vSet.Add("test1")`
vSet.Add("test1")`
for _, v := range vSet.Iterator() {
`fmt.Println(v)
}
fmt.Println(vSet.Cardinality())
}
error occurs after run this test code :cannot range over vSet.Iterator() (value of type *mapset.Iterator[string])
There is the Cardinality function, but I don't see why len(Set) shouldn't return the number of elements.
Feel free to close if you disagree heavily.
Perhaps I didn't test it, but the Iter logic returns the index from the set and not the actual value.
Oops, easily fixed...(note: write a test case for it)
It's helpful if everyone using the package can use the same name to refer to its contents, which implies that the package name should be good: short, concise, evocative. By convention, packages are given lower case, single-word names; there should be no need for underscores or mixedCaps.
http://golang.org/doc/effective_go.html#package-names
It's mostly a problem of taste, but changing the project name into mapset or even changing both the project name and the package name into something like goset or something else would be wonderfully nice. Because it's simply recommend by the Go authors. :D
It's weird that NewThreadUnsafeSet()
doesn't take optional elements and includes them in the returned set.
The ergonomics of NewSet(... interface{})
are much nicer!
Also, the docs for NewSet()
say it returns an empty set, yet that's not necessarily true... I was going to open a PR to fix that when I noticed the inconsistency with NewThreadUnsafeSet()
.
So would you rather they both take optional args, or neither?
IMO the former is both backwards compatible and also a more pleasant API.
NOTE: I'm new to golang, so please ignore this if you think this issue/suggestion isn't relevant. If it's not relevant, please ignore this and sorry for the trouble.
Example:
func (set *threadUnsafeSet) Add(i interface{}) bool
Aren't Maps reference types, so aren't they allways passed by reference?
What's the difference between using:
func (set threadUnsafeSet) Add(i interface{}) bool
Hello,
I was wondering what your thoughts were on adding a func to create a Set from Map
mapset.NewSetFromMapKey[T](map[T]any)
mapset.NewSetFromMapValue[T](map[any]T)
I find myself doing this often. Thought others might as well
Currently, methods like ToSlice() return a slice of interface objs, which makes sense.
In practice, we find ourselves having to write multiple helpers to go from interface slices to primitives like strings, int, etc., whether it be for using NewSetFromSlice
, or ToSlice
.
Is value in added a set of helpers under the mapset
package to support transformations between core primitive types, and interface{}
?
(I am happy to contribute.)
It looks like the commits on the generics
branch were merged into main
.
What do you think about deleting the generics
branch to reduce confusion?
I think there are extra empty elements in the String() and ToSlice() methods:
func (set *threadUnsafeSet) ToSlice() []interface{} {
keys := make([]interface{}, 0, set.Cardinality())
for elem := range *set {
keys = append(keys, elem)
}
return keys
}
The make call creates an array of the specified size with empty values. For instances if the interface is just an int, it initializes the array with 0s of the specified cardinality. Then the append append() call appends the keys to the end of the array. As a result, all the values get appended.
Would this be better?
func (set *threadUnsafeSet) ToSlice() []interface{} {
var keys []interface{}
for elem := range *set {
keys = append(keys, elem)
}
return keys
}
Or making the slice with the length and then iterating through the slice and assigning to the index value rather than appending to the slice.
package main
import (
"github.com/deckarep/golang-set"
"sync"
)
func main() {
var wg sync.WaitGroup
set := mapset.NewSet()
workers := 10
wg.Add(workers)
for i := 1; i <= workers; i++ {
go func() {
for j := 0; j < 1000; j++ {
set.Add(1)
set.ToSlice()
}
wg.Done()
}()
}
wg.Wait()
}
result:
fatal error: all goroutines are asleep - deadlock!
The reason is that in threadSafeSet.ToSlice
func (set *threadSafeSet) ToSlice() []interface{} {
set.RLock()
keys := make([]interface{}, 0, set.Cardinality())
for elem := range set.s {
keys = append(keys, elem)
}
set.RUnlock()
return keys
}
It calls set.RLock() twice.
One in threadSafeSet.ToSlice(), another in threadSafeSet.Cardinality().
consider the following execution sequence:
R1->W1->R2
R1 and R2 are in the same goroutine.
R2 is waiting for W1;
W1 is waiting for R1;
R1 is waiting for R2;
As a result, a deadlock happens!
To avoid it, modify threadSafeSet.ToSlice:
keys := make([]interface{}, 0, len(set.s))
The api has changed...I need to update the README.MD file and probably provide a few more examples!
Recently I use golang-set to help optimize a DFA generator.
And I noticed DFA‘s compile time increased a lot.
golang-set
based on map. I guess frequently insert caused rehashes and memory copies.
I tried to reuse nextKeys and failNext, but nothing happened. I found this from golang-set's code:
Every time I clear the set, a new one created to replace the old one.
As we know, golang never reclaim memory from alive maps, so I use a for loop to remove all items from set instead of another create. But, new clear is more slower than before because remove loop takes more time.
I wrote a new clear function to reduce realloc of map:
This Time, results are better than before:
Saved about 1s, add
function of set still takes biggest part of times. I suppose 2~3s will be saved if we set a proper capacity for Difference
, Intersect
, Union
, etc.
P.S. The conclusion of first version is wrong, I'm sorry for my fault.
Is there any doc around on how to use this library with a generic type?
What i'm trying to achieve is to have sets of type A
and be able to diff between multiple sets.
Thank you in advance!
It is possible to make golang-set work with encoding/gob? gob is the good "go to" for serializing things for internal consumption later.
I've prepare a demo here, currently it is giving out error of:
SaveState failed:gob: type sync.RWMutex has no exported fields
Thanks
Look at building an OrderedSet implementation of the set which preserves order of items added.
One idea, is to still use a map where the value is an int which indicates order.
Is this even useful to many people? Must not be a breaking change.
Gotchas:
It'd be nice to have some way to iterate over all elements in one set.
If there already is a way, please document it more explicitly. Thanks!
The last release (v1
) was quite a while ago (Mar 9, 2014
). Would you mind tagging a newer release with some of the changes since v1? 😄
It looks like main
is the actively used branch... can you delete master
to reduce confusion?
Hello,
Could you kindly point me any way to create a set directly from map keys without iterating by map items?
Thanks in advance.
func main() {
var s mapset.Set
s.Add(0)
}
Actually, I declare a field of set type in a struct, then I want to add something but it causes a runtime error.
@deckarep Would you be willing to tag another release with what's on master? Theres been a fix to a deadlock and a few new features since the 1.5 release, so now would be a decent time to do a 1.6.
It would help me a lot since it would mean less random git sha's in my glide.yaml, and would make it easier for me to determine if/when a new release might be available automatically.
Simple example
s := mapset.NewSetFromSlice([]interface{}{"foo", "bar", "baz"})
fmt.Println(s)
for item := range s.ToSlice() {
fmt.Println(item)
}
produces below:
Set{foo, bar, baz}
0
1
2
Is this designed behavior?
I expected below:
Set{foo, bar, baz}
foo
bar
baz
(I found I could use s.Iter() to produce expected output though)
Is this intentional or am I missing it?
Thank you
example:
for v := range s.Iter() {
if v, ok := v.(int); ok {
if v == definedValue {
break
}
}
}
the channel Iter() returned will be never closed?
I'd like to see an Ethereum address added to the custom
property of the FUNDING.yml
file for GitHub Sponsors. This would allow a canonical address to send funds to. For example, projects could parse out the address and provide donation capabilities to the user.
We've got NewSet(vals...T)
for creating a set from multiple values.
But today I found myself wanting to add a slice of objects to an existing set... today I have to write a for loop to range over the objects.
What about adding an append(vals... T)
method... similar to Python, which allows adding multiple objects.
Alternatively Add(val T) bool
could be modified to take multiple args, which would keep the API surface small. But it's a little undefined that it returns a bool... for multiple objects would that return true if all the objects got added to the existing set, or if at least one object got added?
Thoughts?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.