fatih / set Goto Github PK
View Code? Open in Web Editor NEWSet data structure for Go
License: MIT License
Set data structure for Go
License: MIT License
This package solved the problem I was facing like a charm, but I don't see much development going on after 2014. Is this package still maintained?
IsEqual returns true as long as the two sets are of the same size-regardless of their content. The tests don't cover such a case.
equal := true
if equal = len(s.m) == t.Size(); equal {
t.Each(func(item interface{}) (equal bool) {
_, equal = s.m[item]
return
})
}
return equal
.
One can easily mix up Set interfaces and pass them to functions like Difference
, Union
, etc... This can be fix easily with a simple trick. We should have types of Set implementations and each Interface should have a new Type()
method that returns a simple type declaration (this can be a const enum).
And then we can simple check:
func Intersection(s Interface, t Interface) Interface {
if s.Type() != t.Type() {
panic("Set implementations mixed up: %v , %v", s.Type(), v.Type())
}
u := s.Copy()
u.Separate(Difference(u, t))
return u
}
However one can easily fake this up with a custom Type(), but for our set package this shouldn't be a concern.
Hi,
thanks for the awesome struct, it's very very useful!
Using it i noticed that there is a missing docstring here leaving an eerie
// Separate removes the set items containing in t from set s. Please aware that
that bodes doom.
considering the map is builtin and list is already in the stdlib:)
Without time complexity information for each Set method, it is difficult to determine whether or not to use this library. I thought about using this library, until I read the code for Intersect, which calls Union twice, which in turn calls Copy. The whole operation is hardly optimized. I DO understand that this library is for convenience purposes and I am NOT intending to bash your code, but if people are to rely on such libraries, they at least need to know the complexity of the operations.
To further make my point, I added a benchmark for a piece of code I wrote for the intersection of two sets, which I make no claim as being the fastest implementation, but the order is easily worked out as:
O( (len(set1) + len(set2)) * O(map) )
(I took the liberty of interleaving the results for easier comparison.)
// Returns the intersection of two slices
func SimpleIntersection(l1 []int, l2 []int) []int { // O((len(l1) + len(l2)) * O(map))
ret := []int{}
m := make(map[int]bool, len(l1))
for _, item := range l1 {
m[item] = true
}
for _, item := range l2 {
if m[item] == true {
ret = append(ret, item)
}
}
return ret
}
PASS
BenchmarkSetEquality-4 10000 780659 ns/op
BenchmarkSubset-4 10000 801358 ns/op
BenchmarkIntersection10-4 100000 13075 ns/op
BenchmarkSimpleIntersection10-4 2000000 601 ns/op
BenchmarkIntersection100-4 10000 118579 ns/op
BenchmarkSimpleIntersection100-4 200000 6183 ns/op
BenchmarkIntersection1000-4 1000 1302503 ns/op
BenchmarkSimpleIntersection1000-4 30000 53364 ns/op
BenchmarkIntersection10000-4 100 13888576 ns/op
BenchmarkSimpleIntersection10000-4 3000 573658 ns/op
BenchmarkIntersection100000-4 10 175577891 ns/op
BenchmarkSimpleIntersection100000-4 200 7036305 ns/op
BenchmarkIntersection1000000-4 1 2828214630 ns/op
BenchmarkSimpleIntersection1000000-4 10 144838095 ns/op
ok github.com/fatih/set 41.404s
a number of the receiver methods on the set are things that could reasonably be done as functions. would you be amenable to changing those to pure functions that take set arguments, so as to keep the interface confined strictly to those methods that need to access the internal datastructures directly?
hi,
might seem like an odd request, but it'd be nice if this lib provided an implementation without thread-safety in addition to the one with. that way i can pick which one makes sense depending on my use case. no reason they can't share an interface, of course.
if you're amenable, i'll code one up.
I like the idea and I think this package also should support it. This issue is an opinion and open to any comments.
I think set.New()
should not accept any items as inputs. Instead it should should just accept a type that defines the underlying set. This will simplify the usage of this current package. An example code would be
a := set.New(set.ThreadSafe)
b := set.New(set.NonThreadSafe)
c := set.New(set.SliceBased)
Each struct would then imply the Interface method.
This is a proposal and is open to any comments.
Check out and investigate how to implement it in a way that it doesn't break existing API, if any, then only in a minor fashion. Renaming Size()
to Len()
is one of those cases.
Stemming from issue 14, working on fix for api to require 2 sets in certain functions
Can you please elaborate and add it to the README and godoc?
Add a method to create a new set from an already existing array.
l := []string{"foo", "bar"}
s := set.New(l)
Trying with the variadic operator (set.New(l...)
) doesn't work either. Do I need to make loop to add them individually?
though it's maybe not so hot in golang circles, semver is still pretty much the de facto norm for release versioning. i noticed the one tag that's present so far is 0.1, which isn't quite there (0.1.0 is probably the equivalent). for future releases, would you be OK with adopting semver?
like, once we finish this non-ts set implementation, a 0.2.0 would probably be in order. (or maybe a 1.0.0, if you feel like the API is stable.)
turns out, defer is slow.
https://code.google.com/p/go/issues/detail?id=6980
not in the grand scheme of things, but since it's relatively painless for us to stop using it, we should.
Has is equivalent to IsSuperset and all sets are supersets of the empty set, but both implementations of Has look like:
func (s *set) Has(items ...interface{}) bool {
if len(items) == 0 {
return false
}
// ...
}
I have an array of sets and I want to find the union of all the sets. Rather then doing type cast it would be great if you can provide an inbuilt feature to return the SetNonTS or Set instance rather than an interface.
Code:
unionSet := set.NewNonTS() // find unique files across agents
for _, records := range Agents { // iterate through agents(100 in size) and get files stored on them,
agentSet := set.NewNonTS() // Create set of those files
for _, catalog := range records {
agentSet.Add(catalog.Path)
}
unionSet = set.NewNonTS(set.Union(unionSet, agentSet)) // Needed Feature: unionSet = set.Union(unionSet, agentSet) just like array1 = append(array1, array2)
}
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.