4 ms·
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
by otikik 8y ago
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 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
or
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.
- Insanity 8y agoMy 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.
- hopler 8y agoA proper map based set is a map[type]void or whatever golang has for void.
- carbocation 8y agoCorrect - for go, we would canonically use struct{} which occupies zero bytes of storage.
- Insanity 8y agoBut 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 :)
- bjterry 8y agoAlmost 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{}.
- Insanity 8y agofacepalm 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 ;-)