7 ms·
Usually a fine approach would be to construct a hash table as we walk the array, and if the element is not seen put it in the hash table, otherwise "remove" it
by kccqzy 8y ago
Usually a fine approach would be to construct a hash table as we walk the array, and if the element is not seen put it in the hash table, otherwise "remove" it by setting it to the empty string. If the hash table implementation is good, we can pretty much find out whether an entry has been seen before in O(1) time, making the whole process O(n).
That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array. You don't generally have to copy the original values (usually you just copy a pointer).
- masklinn 8y ago> That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array. Possibly the high constant cost, making them less than optimal for short sequences?
- theclaw 8y agoIf I recall correctly this is exactly what .net’s ‘Distinct()’ LINQ extension method does.
- masklinn 8y agoYes: https://github.com/dotnet/corefx/blob/8750960d3fafa46a9b838c351e995a01fa8b599f/src/System.Linq/src/System/Linq/Distinct.cs https://github.com/dotnet/corefx/blob/8750960d3fafa46a9b838c...
- deleted 8y ago[deleted]
- neel_k 8y ago> That's what the author called "alt" and I don't understand why the author objects to it. His "neutral pseudocode" is Go, which lacks good support for parameterized types. As a result there would be quite a bit of boilerplate code in doing things this way. This is also why the author remarks "For trivial examples this works well, but for more complicated types with complex keys, it may require creating new types." This post is a nice example of why it is important to eliminate friction from a a language if you want to get people to use a particular feature. However, the goal of removing friction interacts poorly with an observation Bjarne Stroustrup once made, that: * For new features, people insist on LOUD explicit syntax. * For established features, people want terse notation. That is, when a feature is new to a programmer, they want it to be loud to remind them that something unexpected is happening, and once it is known to them they want it to disappear so they can focus on their problem -- and if it doesn't disappear, the solution using it will be so noisy they won't do it that way. I expect the ultimate solution to this problem involves IDE design, rather than language design....
- otikik 8y agoI 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 ago
- bakhy 8y agoThis is what I'd do too, and it is quite strange that it was dismissed like that. Maybe because it's not as much fun :) BTW I believe it may be a bit more than just O(n) time on the whole. If your hash-table is auto-growing, you'll have to pay for its resizing. And OTOH if it's sized up front, then you'll have to allocate something proportional to the size of the full array, not just to the number of distinct elements.
- kevinventullo 8y agoAs long as the resizing e.g. doubles the size each time, the total running time will still be O(n). Basically because 1+2+4+...+2^k = O(2^k)
- bakhy 8y agoI think I get it. With doubling, the sum of all the work done for resizing is roughly (written chonologically backwards): n/2 + n/4 + ... ~= n, and O(n) + O(n) is still O(n). Thanks!
- gusmd 8y agoYep! This is generally referred to as "amortized linear time". It's the difference between considering the cost "per operation" vs. "per algorithm". The former is technically correct (as an upper bound), but too pessimistic when you consider the algorithm as a whole. See https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...
- deleted 8y ago[deleted]
- userbinator 8y agoYou could also build the hash table "in-place" using an array of indices, the same length as the size of the array, to chain items. It'll be between O(n) and O(n^2) depending on how many collisions you get, but I suspect that on average it will be faster than sorting.
- thedufer 8y agoAlthough 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 agoOne 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 agoThat'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 agoIs 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 agoYes, 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.
- 8y ago
- deleted 8y ago[deleted]
- leshow 8y agoA Set would be even better IMO
- bastawhiz 8y agoA set would still have n log n complexity, though, wouldn't it? At least if the set was a tree.
- deathanatos 8y agoThe comment you're replying to is replying to a comment about using a hash map; I read it as a suggestion to replace that with a hash set, which would be O(n) in time & space for the article's problem. (You don't need the "value" half of the hash map for this problem.)
- Sean1708 8y agoWhy would a set have to be a tree? In fact would expect trees to be the less common way to implement sets (I would expect hash tables to be more common).
- leshow 8y agoA set could have many implementations, it could be a HashSet and still have O(1) update/access. I was just referring to how using a hash map in this situation you actually don't need the value parameter-- so the correct data structure here is a set, not a map.
- KirinDave 8y agoVery few hash tables actually run in O(1) time and they tend to be bounded. You cannot have any collisions at all, and you need to use a lookup with fast, constant cost. Many hash tables in use today are actually either O(n^2) (for the homework kind), or O(n log n) for some large log factor like 32 (in the spirit of Bagwell's work).
- avian 8y ago> Many hash tables in use today are actually either O(n^2) or O(n log n) Do you have any citation for such an extraordinary claim? Or are you not talking about lookup complexity where n is the size of the table? I would think that a hash table with an O(n^2) or O(n log n) lookup is not a hash table at all. I mean, a simple linear search is O(n).
- KirinDave 8y agoO(n) == O(n^2) when n = 1.
- kevinwang 8y ago...
- KirinDave 8y agoIt is a jokey way to restate the absurd essence of the parent's argument.
- 15rthughes 8y agoThe whole point of this notation is to describe limiting behavior, the true value of N isn’t important in the slightest.
- KirinDave 8y agoThat is actually my point. Remember the goal is to nub an array into a set. Perfect hash tables where there are no collisions are O(1) but they're not suitable for casual use, you need to guarantee your data set never collides hash buckets. That is why most implementations of "maps" in programming languages map to very wide trees after a certain size. A common example is HAMTs (Bagwell is famois for these). They're flexible and perform well on modern hardware for arbitrary key lookiup. If your constant time hash tables is taken to the worst case (as we do in O analysis) then that operation would collide with the same bucket and require a potentially full linear search of the data every time to see if it places into your oversubscribed bucket. That's O(n^2). You could make it better by sorting on insert. That's O(n log n) because it's comparison based. I've provided a much better solution and links to code that does it. Maps and hash tables don't solve this problem any better than just sorting the array. It's worth noting that if we're ignoring preprocessing and the domain is well-constrained, we could probably make O(1) to do a bunch of these ops in bulk if we really wanna go off the deep end. But that's cheating because we'd be ignoring construction costs, as you are here.
- _cs2017_ 8y agoThere's one valid objection to hashing (not the one the author expressed): you may have an array of items that you can compare, but you cannot hash. For example, maybe you rely on a third-party service that lets you compare two items but does not provide you with a hash value. Or maybe you simply don't know the distribution of the items, so it's hard for you to write a good hash function. For instance, the items may be large strings of text. You can of course compare them. But to create a good hash function for them, you'd need to know a bit more about how they are distributed in the space of all possible strings. Maybe hashing the first few characters is good enough -- but that won't work if most of your strings start with the same prefix. Maybe splitting into words and hashing word frequencies is good -- but not if many strings are just reorderings of the same words. And so on.
- ygra 8y agoYou could still use a TreeSet which only requires ordering and equality, but not hashing. As a side note, though, your earlier example would not be comparable via Equals, as it violates transitivity. Which is also what makes it impossible to generate a hash code consistent with its Equals implementation.
- _cs2017_ 8y agoOh yeah absolutely you can use better structures even without hashing, I was just saying that a hash table isn't always an option. Lack of transitivity: you can still dedupe based on a transitive closure of whatever relationship I provide. It's easy if I want to dedupe numbers closer than 0.01 (using sorting) but much harder to do it efficiently for vectors.
- Thiez 8y ago> Which is also what makes it impossible to generate a hash code consistent with its Equals implementation. How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.
- jblow 8y agoHashing text is one of the easiest, most common uses of hashing. As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?
- ricardobeat 8y agoThat's exactly what came to mind immediately. Can't help but make a one-liner: Object.values(arr.reduce((o,s,i,a,k=s.toLowerCase()) => ((o[k] || (o[k]=s)), o), {})) Which turns out to be pretty efficient: each string seen once, low memory overhead. Or a simpler version using Set: let set = new Set() arr.filter((s, i, c, k = s.toLowerCase()) => !set.has(k) && set.add(k))
- deleted 8y ago[deleted]