fatih / set Goto Github PK

I like the idea and I think this package also should support it. This issue is an opinion and open to any comments.

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

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.

Can you please elaborate and add it to the README and godoc?

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.

Stemming from issue 14, working on fix for api to require 2 sets in certain functions

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?

considering the map is builtin and list is already in the stdlib:)

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.

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.

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?

Check out the screenshot please.

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.

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

.

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.)

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?

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.

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)
}

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
    }
    // ...
}