Hacker News new | past | comments | ask | show | jobs | submit login

Sets, if you mean a collection that contains no more than 1 of something, are easy. Use a map with struct{}{} values. If ordering is important, it's ~30 lines of simple code to encase a slice and a map in a struct and define your desired interface.

Testing for a key's existence is easy as well. Accessing a map returns two variables--the 1st is the value itself. The 2nd variable is that "exists" variable you're asking for. It's true when the key is present in the map and false if not. Often you'll see the 2nd variable omitted, but if you need to test for existence it's there for you to use.




Testing membership is the easy part of sets. What about subset, superset, union, intersection, difference? So many problems are trivial thanks to sets.

I'd sooner give up regex support in python than the set type, that is how useful they are.


This repository was named to emphasise the comedy of its existence :) https://github.com/frou/poor-mans-generics/


Ouch!

  type Strings map[string]stdext.Unit
  […]
  func (a Strings) Intersection(b Strings) Strings {
  	result := NewStrings()
  	for as, _ := range a {
  		for bs, _ := range b {
  			if as == bs {
  				result.Add(as)
  				break
  			}
  		}
  	}
  	return result
  }



Ick, good point. Since the fake set is a map, that should use key lookup?


Yes. Basically:

  for k := range s1 {
    if s2.Contains(k) {
      result.Add(k)
    }
  }


Yes, the boolean group operations make many otherwise non-trivial problems remarkably easy. That's why I consider sets such a crucial feature.


Could you give some examples please?


Sure, let's get a really simple one.

You have N groups of something (persons, sales units, cars, tools, whatever). Find the values that are present in all of them. This problem comes up, all the time, in some form.

With sets it's trivial. Take the first set, and calculate a cascading intersection with every other set. At the end you're left with only the values that appeared in every one. In very clear python the code might look like this:

    common = ALL_SETS[0]
    for _set in ALL_SETS[1:]:
      common = common.intersection(_set)
    return common
Now, you can argue that underneath the hood that's still going to do N expensive iterations and you'd be right. This is where proper optimisations come in - when provided by a robust stdlib, we expect the set operations to be implemented with bitmaps.[0, 1] These are not something you'd see in a casual implementation.

Btw, in the above code example I have deliberately omitted a trivial optimisation. Let's leave that as an exercise for the reader. :)

0: http://roaringbitmap.org/about/

1: https://en.wikipedia.org/wiki/Bit_array


Examples like this really make me miss fold.

    return functools.reduce(lambda x,y: x&y, ALL_SETS)


If sets are a good match for your problem (and I agree, they tend to be for many common ones), you definitely should use them in Go. Just write the fucking code.

Even if you use the most obvious, naive code to implement fundamental set operation in Go, the resulting program is probably still faster than whatever you're going to write in Python.

In the absolute worst case, you need to generate an extra copy to use with some other type. Mildly annoying for sure, but easily dealt with.


If a hundred people need to write that code anew a thousand times, somebody's going to screw it up. Widely used and heavily tested code is how we get a more powerful foundation to build on.

If the answer is to generate the Go, then we should be having human beings focus on the more powerful language controlling that generator.


Yes you can hack sets into most any modern language, but mostly involves writing annoying looking boilerplate, or pulling in external libraries.

I think parent is looking for a native set type (which I agree with). I don't know if it has a place in golang, but I always sigh and roll my eyes when I have to implement a set in most languages.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: