4 ms·

Although the examples are all about strings, there's no reason to be so specific. One nice property of the algorithms described in the article is that they onl

Although the examples are all about strings, there's no reason to be so specific. One nice property of the algorithms described in the article is that they only require the elements to be comparable (even better, the first two implementations only require them to have an equivalence relation), while yours requires that they be hashable.

scott_s 8y ago
One could use a tree-based set, which would only require being comparable, but that would get us back to average-case O(n log n).
Sean1708 8y ago
That's fair, but in practical terms how often are you going to come across a problem like this when you're values aren't hashable? Maybe I'm missing something obvious, but I feel like the kind of types that aren't hashable are also the kind of types that you wouldn't have to do something like this with.
jdmichal 8y ago
Is there an example of a type that has an equivalence operation but cannot have a hash operation? Seems to me that those two are identical. If you have a subset of elements within a type that defines identity, then you can hash that identity.
- thedufer 8y ago
  Yes, in a garbage-collected language a ref cell is typically unhashable since the only identifying data about it is the pointer location, which could change between calls to the hash function. However, you can still define equality pretty easily (just compare the pointer values). This is also my best example of something with an equivalence relation that is not comparable. I don't have a ready example of something that is comparable but not hashable, but it isn't uncommon in my experience to come across an opaque type whose author simply didn't expose enough information to hash it, while they did expose a compare function.
munificent 8y ago
Every object is hashable. Here's a hash function that works with anything: int hash(Object anything) { return 3; } Most objects permit more effective hash functions with better distribution properties than that. In practice, I think more types are hashable than are comparable.

scott_s 8y ago

One could use a tree-based set, which would only require being comparable, but that would get us back to average-case O(n log n).

Sean1708 8y ago

That's fair, but in practical terms how often are you going to come across a problem like this when you're values aren't hashable? Maybe I'm missing something obvious, but I feel like the kind of types that aren't hashable are also the kind of types that you wouldn't have to do something like this with.

jdmichal 8y ago

Is there an example of a type that has an equivalence operation but cannot have a hash operation? Seems to me that those two are identical. If you have a subset of elements within a type that defines identity, then you can hash that identity.

thedufer 8y ago
Yes, in a garbage-collected language a ref cell is typically unhashable since the only identifying data about it is the pointer location, which could change between calls to the hash function. However, you can still define equality pretty easily (just compare the pointer values). This is also my best example of something with an equivalence relation that is not comparable. I don't have a ready example of something that is comparable but not hashable, but it isn't uncommon in my experience to come across an opaque type whose author simply didn't expose enough information to hash it, while they did expose a compare function.

munificent 8y ago

Every object is hashable. Here's a hash function that works with anything: int hash(Object anything) { return 3; } Most objects permit more effective hash functions with better distribution properties than that. In practice, I think more types are hashable than are comparable.