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

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.




Applications are open for YC Summer 2019

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

Search: