Hacker News Reader

Comment by otikik | Hacker News Reader

I would go a bit higher on the abstraction level - instead of using a hash I would use a Set. I see that Golang has at least one implementation:

https://github.com/deckarep/golang-set

If for some reason going "high level" is not an option, this:

> For trivial examples this works well, but for more complicated types with complex keys, it may require creating new types.

surprises me. Producing a small, unequivocal identifier for a value (be it using some kind of hash function, or just the raw memory address) seems like a very basic language feature. Doesn't the Go standard library have something similar to

    func memory_address(o interface{}) int

    func hash(o interface{}) string

If yes, then "complex keys" would not be needed: They would always be ints, strings, or whatever the aforementioned function returns.

View on HN

My initial reaction was that I'd use a map like one of the parent posters said. But instead of creating a Set we can just use a map[type]bool, which is essentially a Set.

Incidentally, I just wrote a Unique method today for a specific array.

      type Elements []Element
      func (es Elements) Uniq() []Element {
          seen := make(map[Element]bool, 0)
          results := make([]Element,0)
          for _,e := ranges es {
              if seen[e] {
                  continue
              }
              seen[e] = true
              results = append(results, e)
          }
          return results
      }

I did not think about performance all that much, but map lookup is pretty good and I iterate through the array one time.

(As a side-note, we know that the size will be below 100 so it's not perf critical)

EDIT: Wording EDIT2: To address one of your points, you could probably just create a hash yourself and use that as the map Key as well, as you have said.

A proper map based set is a map[type]void or whatever golang has for void.

Correct - for go, we would canonically use struct{} which occupies zero bytes of storage.

But how would you indicate something is found? What struct do you put in there?

Can you give me an example, I'm curious to know :)

Almost every language has a function that returns whether a key exists in the map. In go it would be something like:

    _, ok := m[thing_to_be_found]

So it doesn't matter what you put in there, including struct{}.

facepalm of course. Somehow that slipped my mind lol. I'm used to using the default zero-values in maps in go which is a lovely feature. But it means I don't often have to check if something is already in the map :P

EDIT: Now I still need to create an empty struct to use as a value when something is found, which is a bit less elegant in my eyes.

     var dummy struct{}
     found[key] = dummy

But that might just be taste, when reading it, the fact that it's a boolean value saying "found = true" just takes no overhead in parsing the meaning.

Thanks guys ;-)

You can just do

    found[key] = struct{}{}

Which still does not say much imo, but yeah it is an option :)

Reply on news.ycombinator.com