Removing Array Duplicates(flak.tedunangst.com)
flak.tedunangst.com
Removing Array Duplicates
https://flak.tedunangst.com/post/removing-array-duplicates
198 comments
> 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....
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....
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
If yes, then "complex keys" would not be needed: They would always be ints, strings, or whatever the aforementioned function returns.
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.
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.
(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.
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
}
(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 :)
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]
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.
Thanks guys ;-)
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
Thanks guys ;-)
As a bit of a noob I certainly see that in JavaScript as things change. There will be a discussion about easily readable code and there are some explicit examples and everyone is happy about them because we all know what is happening, then the discussion turns to new syntax and it's terse and everyone is excited too ;)
I can't help but wonder "Hey guys do these conversations we just had make sense next to each other?"
Granted it's always a balancing act.
I can't help but wonder "Hey guys do these conversations we just had make sense next to each other?"
Granted it's always a balancing act.
There'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.
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.
Hashing 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?
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?
Hashing text isn't hard but to do it efficiently you may need to know the distribution.
Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions.
Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set.
About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)
Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions.
Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set.
About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)
Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs 1000 times.
Typically, you can tell the order between two strings early, after you read just the starting few characters. So for comparison you would usually read maybe 10 bytes per file on average, or 3 x 1000 x 10 bytes = 30KB in total. Or maybe 30MB if the strings have long common prefixes.
Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible.
Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.
Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible.
Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.
Maybe not, but I bet "someone else overrode == and you've been told not to mess with it" has.
You 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.
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.
Oh 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.
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.
> 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.
How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.
This 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.
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.
As 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)I 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!
Yep! 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_Arr...
See https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...
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.
Every object is hashable. Here's a hash function that works with anything:
In practice, I think more types are hashable than are comparable.
int hash(Object anything) { return 3; }
In practice, I think more types are hashable than are comparable.
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).
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.
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.
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.
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.
If I recall correctly this is exactly what .net’s ‘Distinct()’ LINQ extension method does.
Very 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).
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).
> 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).
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).
O(n) == O(n^2) when n = 1.
The whole point of this notation is to describe limiting behavior, the true value of N isn’t important in the slightest.
That 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.
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.
It's worth noting for clarification I'm talking about inserting to construct a set and reading out the keyspace. Not specifically reads, which is I think what folks below are objecting to.
The read side barely matters for the use case we're discussing.
The read side barely matters for the use case we're discussing.
Not sure why you're getting downvoted. It's plainly true that hash tables accesses are only O(1) amortized. The real worst case is ~O(n log n) (or whatever the bucket data structure is) in the case of collisions and/or filling up.
And we can always pre-allocate a huge array for the buckets, but the behavior of the hash function is always going to be a risk.
And we can always pre-allocate a huge array for the buckets, but the behavior of the hash function is always going to be a risk.
I don't know about the rest, but I downvoted both of you because your vague claims just add noise to the discussion. There's absolutely no sense whatsoever in the claim that the worst case for hash table access is O(n log n), when just a linear search will be O(n).
The task is not to find an object in a hash tables. It's to nub an array into a set.
Which is why we're not handwaving away the construction cost or ignoring key comparisons or other such thinking.
Saying, "A hash tables solves this" is the definition of noise, because if you have a perfect hash function for a data set to get the constants you want then you've already got the solution to the problem presented for discussion here. The hash tables itself just becomes cargo culting.
Which is why we're not handwaving away the construction cost or ignoring key comparisons or other such thinking.
Saying, "A hash tables solves this" is the definition of noise, because if you have a perfect hash function for a data set to get the constants you want then you've already got the solution to the problem presented for discussion here. The hash tables itself just becomes cargo culting.
Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear to the reader but clearly it wasn't.
So just to be fully explicit:
Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc.
So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure.
How about it?
And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.
So just to be fully explicit:
Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc.
So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure.
How about it?
And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.
I'm being downvoted because I deserve to be. I got involved in a computer science discussion on hacker news and now I don't have the self-control to extricate myself because I love this subject.
What are you calling n?
[deleted]
[deleted]
That'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), {}))
let set = new Set()
arr.filter((s, i, c, k = s.toLowerCase()) => !set.has(k) && set.add(k))You 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.
> 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?
Possibly the high constant cost, making them less than optimal for short sequences?
[deleted]
[deleted]
A Set would be even better IMO
A set would still have n log n complexity, though, wouldn't it? At least if the set was a tree.
The 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.)
A 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.
Why 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).
The author uses Go in this example, and they're really just struggling against the language. This is a pretty good example of why choice of language matters: in C++ this could be a simple, linear pass through the array with an std::unordered_set storing visited elements, with an optional std::remove_if/std::erase at the end if they wanted to actually get rid of the elements. All done in linear time, space overhead, and likely with shorter and faster code.
Yup, you can implement the whole ordeal in C++ like this:
int main(int argc, char** argv) {
std::vector<std::string> strings{
"apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple",
};
strings.erase(
std::remove_if(
std::begin(strings),
std::end(strings),
[seen = std::unordered_set<std::string>{}](std::string_view str) mutable {
std::string lower = "";
std::transform(std::begin(str), std::end(str), std::back_inserter(lower), ::tolower);
if (seen.find(lower) == std::end(seen)) {
seen.insert(lower);
return false;
}
return true;
}
),
std::end(strings)
);
for (auto& str : strings) {
std::cout << str << "\n";
};
}Yeah, this is definitely the downside to Go. You can write more or less the same code as your C++ in Rust like this:
EDIT: updated to make use of the fact that `set.insert` returns a boolean.
use std::collections::HashSet;
fn main () {
let strings = vec![
"apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple",
];
let mut set : HashSet<&'static str> = HashSet::new();
let strings : Vec<&str> = strings
.into_iter()
.filter(|string| set.insert(string))
.collect();
println!("{:?}", strings);
}
EDIT: updated to make use of the fact that `set.insert` returns a boolean.
For completeness, Java is basically the same:
The Go version only copies in the cleanup pass he doesn't show, so it copies each surviving element once, and no other elements. The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving). The C++ version uses remove_if, and the documentation doesn't specify how it does the copying [1], but knowing what C++ people are like, it will probably do the minimum of copying too. The Java version hits some truly hoopy code in removeIf [2], which does the same minimal copying, but does allocate a bitmap and walk the array twice, in order to support predicates which want to look at the rest of the list.
I would say all of these reflect their language's values. The Go code is efficient, but only because the programmer has to write it all out longhand, so there is nowhere for inefficiency to hide. The C++ code is (i think!) efficient, because C++ implementers value maximal efficiency in their libraries. The Java code sacrifices a little efficiency to allow its users to do silly things safely.
[1] https://en.cppreference.com/w/cpp/algorithm/remove
[2] http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/j...
List<String> strings = new ArrayList<>(List.of("apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple"));
Set<String> seen = new HashSet<>();
strings.removeIf(s -> !seen.add(s.toLowerCase()));
strings.forEach(System.out::println);
The Go version only copies in the cleanup pass he doesn't show, so it copies each surviving element once, and no other elements. The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving). The C++ version uses remove_if, and the documentation doesn't specify how it does the copying [1], but knowing what C++ people are like, it will probably do the minimum of copying too. The Java version hits some truly hoopy code in removeIf [2], which does the same minimal copying, but does allocate a bitmap and walk the array twice, in order to support predicates which want to look at the rest of the list.
I would say all of these reflect their language's values. The Go code is efficient, but only because the programmer has to write it all out longhand, so there is nowhere for inefficiency to hide. The C++ code is (i think!) efficient, because C++ implementers value maximal efficiency in their libraries. The Java code sacrifices a little efficiency to allow its users to do silly things safely.
[1] https://en.cppreference.com/w/cpp/algorithm/remove
[2] http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/j...
>The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving).
To be clear, the Rust version does not do any copying or moving of the strings. Both the set and the new Vec contains &'static str, same as the original Vec.
But a more realistic example is where the original Vec was of String elements instead of &'static str. The same point would still apply, but the result Vec of &str would borrow from the original Vec of String. If the goal was to produce a Vec of String, then it would need to copy (clone) the Strings from the original Vec.
To be clear, the Rust version does not do any copying or moving of the strings. Both the set and the new Vec contains &'static str, same as the original Vec.
But a more realistic example is where the original Vec was of String elements instead of &'static str. The same point would still apply, but the result Vec of &str would borrow from the original Vec of String. If the goal was to produce a Vec of String, then it would need to copy (clone) the Strings from the original Vec.
The output form this is a little different form the article, as it additionally requires:
* that the uniqueness check is done case-insensitively,
* that the casing from the first instance of the string in the input array should be used in the output, and
* that the output should be ordered based on the order of the first instance of the string in the input array
Possibly an unusual set of requirements (I'd generally expect that if removing duplicates from a list, that the output order wouldn't matter) but hey, different problems have different requirements.
The desired output is:
* that the uniqueness check is done case-insensitively,
* that the casing from the first instance of the string in the input array should be used in the output, and
* that the output should be ordered based on the order of the first instance of the string in the input array
Possibly an unusual set of requirements (I'd generally expect that if removing duplicates from a list, that the output order wouldn't matter) but hey, different problems have different requirements.
The desired output is:
apple
cAt
Dog
banana
apple
cAt
cat
Dog
dog
Cat
Apple
dOg
bananaI've tried to fix the Rust code, but I'm getting some lifetime errors. Can anyone spot the problem? (Note: I've used C++ for most of the time and am still uncomfortable with Rust)
use std::collections::HashSet;
fn main () {
let strings = vec![
"apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple",
];
let mut set : HashSet<&'static str> = HashSet::new();
let strings : Vec<&str> = strings
.into_iter()
.map(|string| (string, string.to_lowercase()))
.filter(|(_, lower)| set.insert(lower))
.map(|(string, _)| string)
.collect();
println!("{:?}", strings);
}The lower value is of type &String because the argument to filter is of type &(String, String) and the pattern match needs to propagate the &. The reference is only valid for the body of the filter closure (that is, it is &'short String, for some anonymous/unnamed lifetime 'short), but it is being put into a set that expects &'static str (the explicit type on the let line). The &String to &str type coercion is fine, but it's not correct to treat the &'short as a &'static (the short one is potentially invalid after filter's closure returns).
Changing the type annotations won't make this compile, because it is actually catching a real bug. The iterator is lazy and the full pipeline is executed for each element at once: lowercasing, inserting into the set, inserting into the Vec that's the result of the collect, and deallocating the lower string. This last step is the key/danger: if the HashSet held references/slices to the lower strings (instead of owning them), those references would become dangling immediately and future look-ups into the set won't work right/will trigger undefined behaviour.
The problem is a little clearer (and mostly fixed) if you simplify the code slightly by removing the two map calls, and instead call to_lowercase in the filter directly:
Changing the type annotations won't make this compile, because it is actually catching a real bug. The iterator is lazy and the full pipeline is executed for each element at once: lowercasing, inserting into the set, inserting into the Vec that's the result of the collect, and deallocating the lower string. This last step is the key/danger: if the HashSet held references/slices to the lower strings (instead of owning them), those references would become dangling immediately and future look-ups into the set won't work right/will trigger undefined behaviour.
The problem is a little clearer (and mostly fixed) if you simplify the code slightly by removing the two map calls, and instead call to_lowercase in the filter directly:
.into_iter()
.filter(|string| set.insert(string.to_lowercase()))
.collect();
Even with the hash set solution, it would be nice to not copy the string contents, which unfortunately is needed if the hash set contains lowercased versions of the strings. On the other hand, converting all strings to lowercase then comparing them isn't a great way to case-insensitively compare strings anyway, as Unicode doesn't guarantee that will work.
The UniCase crate defines a wrapper around strings with a case-insensitive Eq implementation, so this works:
The UniCase crate defines a wrapper around strings with a case-insensitive Eq implementation, so this works:
use std::collections::HashSet;
use unicase::UniCase;
fn main () {
let strings = vec![
"apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple",
];
let mut set = HashSet::new();
let strings: Vec<_> = strings
.iter()
.filter(|&string| set.insert(UniCase::new(string)))
.collect();
println!("{:?}", strings);
}
This is pretty cool. People might think it's cheating to pull in a crate. But IMO the fact that its super easy to pull in a crate in Rust is one of the best things about the language.
Similar to the C++, all of those are addressed by inserting lower-cased into the set, which can be achieved via an extra method call:
https://play.rust-lang.org/?version=stable&mode=debug&editio...
set.insert(string.to_lowercase())
https://play.rust-lang.org/?version=stable&mode=debug&editio...
Just like C++, your filter can be simplified like,
filter(|string| {set.insert(string)}
as insert return a bool.
filter(|string| {set.insert(string)}
as insert return a bool.
Oo, I didn't realise that. Super handy. I've updated my snippet to make use of your suggestion :)
if (seen.find(lower) == std::end(seen)) {
seen.insert(lower);
return false;
}
You can just return
seen.insert(lower).second
as insert function return a pair<iterator, bool>
You can just return
seen.insert(lower).second
as insert function return a pair<iterator, bool>
And today I learned something new. Been a long time since I wrote my last lines of C++ anyway.
Bonus points for using emplace() instead of insert
This is good enough for "small" arrays, but I wouldn't wanna run it on really large ones. You double the space with those lowercased copies + some extra space for the set itself. And you'll also spend a lot of time lowercasing the strings and std::hash'ing them for the set.
You need to be careful with C's tolower. It takes a signed integer, and negative values are undefined behaviour. It would be safer to cast to unsigned char before calling tolower. https://en.cppreference.com/w/cpp/string/byte/tolower
This is the author's choice to make the problem hard -- Go has a built-in map type that works fine for this, and produces code as compact as the C++ version, and is also O(n):
seen := make(map[string]bool)
for n, s := range array {
if seen[strings.ToLower(s)] {
array[n] = ""
} else {
seen[strings.ToLower(s)] = true
}
}Don't calculate strings.ToLower() twice and skip over s == "" to avoid the map lookups and some assignments when already tombstoned and you'll save a lot of time.
seen := make(map[string]bool)
for n, s := range array {
if s == "" {
continue
}
lower := strings.ToLower(s)
if seen[lower] {
array[n] = ""
} else {
seen[lower] = true
}
}How can an element be already tombstoned? Isn’t that the first loop, making only one pass?
Does Go just warp people's view of what's possible in programming languages? This is a trivial problem to solve for arrays on any data type, but the author can only think about solving it with strings and for whatever bizarre reason can't write out the name "hash set" for the simplest, most general and performant solution?
Yes. Or more precisely, any language puts various limits on what you can easily and conveniently express - in the strict sense, everything you can implement in one language you can implement in all of them as long as they're Turing-complete. However, the amount of effort required to express different things varies between the languages very significantly, and the users tend to confine their thinking to the most directly-supported features of the language they use, as they are most convenient to use most of the time. The term to search for is the "Blub paradox".
Go is a language which consciously limits the expressive power of the language in some areas, with the goal of simplifying the implementation and reducing the complexity of codebases written in Go (trading that for repetition). We'll see in 20 years how that plays out.
Anyway, constraining oneself to a single language is never good. Learning other languages widens the horizons of what you can imagine implemented (and how), also in your original language. I wish more people - especially starry-eyed fans of this or that language - learned about this fact... :)
Go is a language which consciously limits the expressive power of the language in some areas, with the goal of simplifying the implementation and reducing the complexity of codebases written in Go (trading that for repetition). We'll see in 20 years how that plays out.
Anyway, constraining oneself to a single language is never good. Learning other languages widens the horizons of what you can imagine implemented (and how), also in your original language. I wish more people - especially starry-eyed fans of this or that language - learned about this fact... :)
> Blub
I love the blub paradox story[0]. If you hadn't mentioned it, I was going to. The central idea is, each language lives at a particular spot on a 'power spectrum' -- perhaps 'expressiveness spectrum' is more accurate since theoretically any Turing-equiv lang is technically as powerful as the others.
When you look down the power spectrum, at less-expressive languages, it's easy to scoff and say "I can't believe that language is missing Feature X of my chosen language." But when you look up the spectrum (and in the article, LISP is the example given), the more powerful features in that language just look like nonsense. The money quote is "Blub is good enough for him, because he thinks in Blub."
For me, my primary language is C#. When I look at Go, I can't help but think "I can't believe it doesn't have generics, how can anyone get anything done in it?" But when I look at LISP metaprogramming, I get uncomfortable with my lack of understanding. Luckily I am a language nerd so I force myself to experience languages at all ends of the spectrum.
Highly recommended read.
[0]: http://www.paulgraham.com/avg.html
I love the blub paradox story[0]. If you hadn't mentioned it, I was going to. The central idea is, each language lives at a particular spot on a 'power spectrum' -- perhaps 'expressiveness spectrum' is more accurate since theoretically any Turing-equiv lang is technically as powerful as the others.
When you look down the power spectrum, at less-expressive languages, it's easy to scoff and say "I can't believe that language is missing Feature X of my chosen language." But when you look up the spectrum (and in the article, LISP is the example given), the more powerful features in that language just look like nonsense. The money quote is "Blub is good enough for him, because he thinks in Blub."
For me, my primary language is C#. When I look at Go, I can't help but think "I can't believe it doesn't have generics, how can anyone get anything done in it?" But when I look at LISP metaprogramming, I get uncomfortable with my lack of understanding. Luckily I am a language nerd so I force myself to experience languages at all ends of the spectrum.
Highly recommended read.
[0]: http://www.paulgraham.com/avg.html
> Luckily I am a language nerd
Oh, hi there, always good to meet others with the same hobby ;)
Yeah, the Blub essay is well-written and it influenced my thinking significantly when I read it for the first time. It was one of the reasons I started asking myself: "what other above-Blub languages are there, and what features do they boast?" and made me become a language nerd ;)
Many years later, after actually experiencing a whole lot of niche languages and wandering close to the verge of insanity countless times, I concluded that the "expressive power" is not that simple to define, that its definition can change over time (the essay is from 2001!). It's easy to imagine languages placed on steps of a ladder, where more expressive ones occupy higher positions. It can be a good mental model in practice when considering relatively similar languages, too.
The problem is, there are languages which use entirely different ladders! From the perspective of all languages on Blubby ladder, they set out to solve different problems, assume completely different contexts of use, use completely alien computation models, in short: work in a fundamentally different way.
It's not that they're not general-purpose languages, but still, directly comparing "expressive power" of Forth, Joy, Lisp, Prolog, Smalltalk, Clean, Idris, APL, Rebol with BASIC, Pascal, C/++/#, PHP, Python, JS and the likes just feels off somehow :) In other words, I believe that the phenomenon of language expressive power is not based simply on the number of features the language implements and even how advanced they are - it's got to be more complex than that. To me, rather than a single ladder, it looks like a 3d surface with randomly erected hills, where groups of similar languages gather around and below the local maxima. It's not certain if the relative heights of the hills are comparable in some way or if that comparison would have any meaning.
It was actually very pleasant realization: as I was heading towards the top of the ladder (starting at Pascal and C level), I stopped to look around and suddenly discovered that from this high up I can see a whole lot more hills worth climbing!
Anyway, whatever your approach and route would be, learning new languages is always good. Learning the concepts behind them gives you more mental tools for problem-solving, and learning about their internals often leads to a much better understanding of the concepts. Plus, forcing oneself to experience all of that is fun in its own right :)
Oh, hi there, always good to meet others with the same hobby ;)
Yeah, the Blub essay is well-written and it influenced my thinking significantly when I read it for the first time. It was one of the reasons I started asking myself: "what other above-Blub languages are there, and what features do they boast?" and made me become a language nerd ;)
Many years later, after actually experiencing a whole lot of niche languages and wandering close to the verge of insanity countless times, I concluded that the "expressive power" is not that simple to define, that its definition can change over time (the essay is from 2001!). It's easy to imagine languages placed on steps of a ladder, where more expressive ones occupy higher positions. It can be a good mental model in practice when considering relatively similar languages, too.
The problem is, there are languages which use entirely different ladders! From the perspective of all languages on Blubby ladder, they set out to solve different problems, assume completely different contexts of use, use completely alien computation models, in short: work in a fundamentally different way.
It's not that they're not general-purpose languages, but still, directly comparing "expressive power" of Forth, Joy, Lisp, Prolog, Smalltalk, Clean, Idris, APL, Rebol with BASIC, Pascal, C/++/#, PHP, Python, JS and the likes just feels off somehow :) In other words, I believe that the phenomenon of language expressive power is not based simply on the number of features the language implements and even how advanced they are - it's got to be more complex than that. To me, rather than a single ladder, it looks like a 3d surface with randomly erected hills, where groups of similar languages gather around and below the local maxima. It's not certain if the relative heights of the hills are comparable in some way or if that comparison would have any meaning.
It was actually very pleasant realization: as I was heading towards the top of the ladder (starting at Pascal and C level), I stopped to look around and suddenly discovered that from this high up I can see a whole lot more hills worth climbing!
Anyway, whatever your approach and route would be, learning new languages is always good. Learning the concepts behind them gives you more mental tools for problem-solving, and learning about their internals often leads to a much better understanding of the concepts. Plus, forcing oneself to experience all of that is fun in its own right :)
What do you do if you're in a Go project and need to implement this, though? The complexity of FFIs and the maintenance expense of adding another language/compiler is worse than having to work against the language.
> What do you do if you're in a Go project and need to implement this, though?
Learn from your mistakes.
Learn from your mistakes.
This is a bit like saying that English is a language superior to Danish, because there are better books out there in English.
I don't think this has anything to do with the language, it just happens that C++ ships with a much bigger standard library than Go.
I don't think this has anything to do with the language, it just happens that C++ ships with a much bigger standard library than Go.
Keep in mind that I’m not saying that C++ is a better language than Go here: I’d need a lot more evidence than an array deduplication routine to prove this. I’m just saying that Go is ill-suited for this particular task as compared to C++, and the author is struggling with this as they go through with implementing their algorithm; this leads them to settle on a clumsy and inefficient “solution” because there isn’t really a good alternative in the confines of the language that they chose. (FWIW, C++ does have a good standard library for implementing algorithms but this doesn’t really come into play here, since we’re not doing anything advanced. Any language with a set and filter would do the job. And for the record, I do think that C++ is a better language than Go, but I’m not going to argue it here because I don’t know the latter well enough to be confident in my viewpoint and don’t have enough space here to discuss it here if I did.)
It's much easier to implement in Javascript, too, even though JS has a much smaller standard library. The main problem is Go's lack of generics.
indeed, currently the standard library of JS is incredibly small.
It does have to do with the language. Writing a generic Set type is trivial in many languages, yet hard in Go.
> it just happens that C++ ships with a much bigger standard library than Go.
I thought go had much bigger standard library. Go has archive, compression, crypto, database, encoding, hash, html, and net etc.
I thought go had much bigger standard library. Go has archive, compression, crypto, database, encoding, hash, html, and net etc.
This article is incomplete. The Haskell Library "discrimination" has a linear time, "productive" (in that it can output partial results before the full input has been seen) version of this:
http://hackage.haskell.org/package/discrimination-0.3/docs/D...
A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. Sadly, this information is not well distributed among software engineers in industry.
http://hackage.haskell.org/package/discrimination-0.3/docs/D...
A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. Sadly, this information is not well distributed among software engineers in industry.
Do you have some good description / paper for that algorithm? The code is not super clear.
If you check my submission history you'll see me mention it a few times. The library has links[0] to the papers which describe how to use American Flag Sort in functional contexts to get high performance linear time sorts.
Most modern, thorough upper-division computer science programs cover how the sorting itself works. I think MIT Open Courseware has one [1].
Before thinking about how to do it productively, imagine that you sorted a list of objects based off their identity, and their identity was trivially comparable. Once sorted, the algorithm would be simple. You'd iterate the list, and every time you see a new object you didn't just see before (you only need a history of one object), you copy it to the output.
To do this in a productive way, you'd actually need to turn each potential bucket you're sorting into a future and then process all of those asynchronously (and ideally in parallel). Top down sorts like American Flag are uniquely suited to this.
[0]: https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p...
[1]: https://www.youtube.com/watch?v=pOKy3RZbSws
Most modern, thorough upper-division computer science programs cover how the sorting itself works. I think MIT Open Courseware has one [1].
Before thinking about how to do it productively, imagine that you sorted a list of objects based off their identity, and their identity was trivially comparable. Once sorted, the algorithm would be simple. You'd iterate the list, and every time you see a new object you didn't just see before (you only need a history of one object), you copy it to the output.
To do this in a productive way, you'd actually need to turn each potential bucket you're sorting into a future and then process all of those asynchronously (and ideally in parallel). Top down sorts like American Flag are uniquely suited to this.
[0]: https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p...
[1]: https://www.youtube.com/watch?v=pOKy3RZbSws
I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
This library is essentially a generic version of radix sort. For example to sort an array of strings in O(nk), where k is the maximum length all strings:
use bucket sort to split the strings into 256 buckets based on the first character. Take O(n)
* recursively sort each bucket based on the remaining k-1 characters. Takes O(n(k-1)).
concatenate sorted buckets
This is better than the O(nklog(n)) you get with comparison based sort. It turns out that you can implement radix sort for pretty much any type, where instead of a comparison operator for that type you have a 'split into buckets' operator.
The types might look something like this (in Haskell notation):
This is better than the O(nklog(n)) you get with comparison based sort. It turns out that you can implement radix sort for pretty much any type, where instead of a comparison operator for that type you have a 'split into buckets' operator.
The types might look something like this (in Haskell notation):
class Ord a where
compare :: a -> a -> Ordering
class Bucketable a where
splitIntoBuckets :: (b -> a) -> [b] -> [[b]]The first big insight Henglein brings in the first paper is structural: you can map searches sensibly over products and sums. This is actually a profound thing, but most folks outside of Haskell circles don't work with ADTs so they don't understand the universal applicability of this insight.
It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.
It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.
You can get partial results with really any enumerable style api pretty easily, e.g. python
def distinct(l):
seen = set()
for s in l:
if s.lower() not in seen:
yield s
seen.add(s.lower())A coroutine-ish solution is ultimately how Kmett did it too. What makes it tricky is when you do it over Sum types. You actually don't know how long either side of the sum will take to compute, so you need to execute them speculatively. You actually have to be able to yield for one of several coroutines.
`casefold` is for caseless comparisons, `lower` is for display.
There's also the classic one-liner:
unique_array = list(set(non_unique_array))Which is fine. I'm fairly sure that's n log n, although sometimes those end up being n^2 if they're biased towards memory friendliness.
It's O(n). Python's set has O(1) insertion and lookup.
https://wiki.python.org/moin/TimeComplexity#set
https://wiki.python.org/moin/TimeComplexity#set
The page you link says it's O(n) for lookup.
It says O(1) for lookup. Average case is the one that matters here.
Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/) Python has put significant effort into good default hashes[1] so you won't be vulnerable to attackers feeding in maliciously colliding hashes, nor will you have performance degradation from biased bits in the hashes if you've written an insufficiently uniform hash function.[2]
[1] https://python-security.readthedocs.io/vuln/cve-2012-1150_ha...
[2] For instance, pointers are usually aligned to cache line boundaries, and are biased toward page boundaries, and in C++, the hash function of an integer/pointer is the identity function. So in C++, a std::unordered_set of pointers will have ridiculously high collision rates. If you have 1024 pointers in a set of size 2048, you will only have only 32 buckets that have values in them, and each of those buckets will have roughly 32 elements, and the zero bucket will even more. Python doesn't let you shoot yourself in the foot, and whitens your hashes before going to the dictionary. C++ "solves" this problem by providing an API which allows you to override the hash function.
Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/) Python has put significant effort into good default hashes[1] so you won't be vulnerable to attackers feeding in maliciously colliding hashes, nor will you have performance degradation from biased bits in the hashes if you've written an insufficiently uniform hash function.[2]
[1] https://python-security.readthedocs.io/vuln/cve-2012-1150_ha...
[2] For instance, pointers are usually aligned to cache line boundaries, and are biased toward page boundaries, and in C++, the hash function of an integer/pointer is the identity function. So in C++, a std::unordered_set of pointers will have ridiculously high collision rates. If you have 1024 pointers in a set of size 2048, you will only have only 32 buckets that have values in them, and each of those buckets will have roughly 32 elements, and the zero bucket will even more. Python doesn't let you shoot yourself in the foot, and whitens your hashes before going to the dictionary. C++ "solves" this problem by providing an API which allows you to override the hash function.
> It says O(1) for lookup. Average case is the one that matters here.
No, it's actually not. Everyone else and the article were using the worst case asymptotic, so you'reswitching to this vernacular and suggesting, "Oh we mean the asymptotic of the average."
Redefining the entire conversation to your notational convenience is not a very fair call, and doesn't speak well of your intentions.
And what's more, it's typical to use big-theta notation to discuss average performance anyways. So even if we WERE using that, we'd be using different notation to be more consistent with the literature and less confusing.
> Worst case is for people who've intentionally written bad hash functions.
No. It's for people who do not know what kind of input they're going to receive or what kind of hardware they're going to execute on.
No, it's actually not. Everyone else and the article were using the worst case asymptotic, so you'reswitching to this vernacular and suggesting, "Oh we mean the asymptotic of the average."
Redefining the entire conversation to your notational convenience is not a very fair call, and doesn't speak well of your intentions.
And what's more, it's typical to use big-theta notation to discuss average performance anyways. So even if we WERE using that, we'd be using different notation to be more consistent with the literature and less confusing.
> Worst case is for people who've intentionally written bad hash functions.
No. It's for people who do not know what kind of input they're going to receive or what kind of hardware they're going to execute on.
> A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time.
Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).
> Sadly, this information is not well distributed among software engineers in industry.
Agreed, although you may be interested to know most software 3D rendering engines in the 90's used American flag sorting variants to efficiently implement the painter's algorithm.
Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).
> Sadly, this information is not well distributed among software engineers in industry.
Agreed, although you may be interested to know most software 3D rendering engines in the 90's used American flag sorting variants to efficiently implement the painter's algorithm.
> Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).
It is more subtle than this. Top-down radix sort (which discrimination generalizes) is linear time in the number of input bytes, rather than the number of input records. One special case is when each element has a constant number of bytes, like you mention, but it isn't the only case.
It is more subtle than this. Top-down radix sort (which discrimination generalizes) is linear time in the number of input bytes, rather than the number of input records. One special case is when each element has a constant number of bytes, like you mention, but it isn't the only case.
Can you name a non-infinite dataset with an unbounded domain? One without a trivial mapping function?
Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.
Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.
The code seems to "remove" items from the array by setting an empty string to them. But in all mainstream languages I know of, an empty string is also a valid string. So the item isn't "removed" it's simply replaced by the empty string. Am I completely misunderstanding what the author is trying to do?
Edit: Thanks: I missed the passage about this being the first step of two, with the compaction coming later (that step isn't in the article at all).
Edit: Thanks: I missed the passage about this being the first step of two, with the compaction coming later (that step isn't in the article at all).
His goal is to get ["apple", "dog", "cat"] from ["apple", "dog", "apple", "cat", "apple"].
He does it in two steps[0]:
Step ONE: Replace any duplicate values with the empty string (the tombstone) in the original array. (Going from ["apple", "dog", "apple", "cat", "apple"] to ["apple", "dog", "", "cat"]).
Step TWO: Compact the original array by creating a new array out of all non-tombstone values.
He shows 4 different algorithms for performing Step ONE. He shows 0 algorithms for performing Step TWO because it's trivial.
[0]: >We’d like solutions that conserve time and space. All solutions here work in place, using the tombstone technique to create a sparse array, then compacting it later.
He does it in two steps[0]:
Step ONE: Replace any duplicate values with the empty string (the tombstone) in the original array. (Going from ["apple", "dog", "apple", "cat", "apple"] to ["apple", "dog", "", "cat"]).
Step TWO: Compact the original array by creating a new array out of all non-tombstone values.
He shows 4 different algorithms for performing Step ONE. He shows 0 algorithms for performing Step TWO because it's trivial.
[0]: >We’d like solutions that conserve time and space. All solutions here work in place, using the tombstone technique to create a sparse array, then compacting it later.
That means it removes empty strings from the input.
If this were a library function, I don’t think that’s acceptable (rationale: if you want to remove all empty strings, but the library function doesn’t, you can easily correct that. If you want to keep the first empty string, but the library function removes it, calling the library function is as good as useless)
If this were a library function, I don’t think that’s acceptable (rationale: if you want to remove all empty strings, but the library function doesn’t, you can easily correct that. If you want to keep the first empty string, but the library function removes it, calling the library function is as good as useless)
On the flip side, if we're going to be discussing libraries, remember that things like "Maybe<String>" aren't free. That "Maybe" wrapper in the general case has to expand the size of the underlying data structure to adjoin an additional element to it, and that's something else a library may want to think twice about.
I say "in the general case" because in the specific case it is not always necessary. ISTR Rust implements a specialization on pointers where you can syntactically wrap an Option around something and it's smart enough to use the null pointer directly as the missing case under the hood. However, if you've got something like a plain ol' machine int, you have to expand it somehow to get an Option or Maybe, because the compiler is not entitled to remove even a single element out of those for its purposes.
How acceptable it is depends on your ability to declare an in-range (for the data type) element as the "impossible" element. Being able to use an in-range element is more efficient, but less general. In this case, simply by declaration Ted says empty strings are not valid. The next time he does this, they may be, and the technique would have to be adapted to that. A library that uses some equivalent to Option or Maybe is a good safe default for a library, of course. Another safe default is to create a new array and return that, too. It's not that hard to end up in a place where the safe default library is not suitable, although nowadays it takes enough data to choke a horse to get there since our computers are so darned fast.
I say "in the general case" because in the specific case it is not always necessary. ISTR Rust implements a specialization on pointers where you can syntactically wrap an Option around something and it's smart enough to use the null pointer directly as the missing case under the hood. However, if you've got something like a plain ol' machine int, you have to expand it somehow to get an Option or Maybe, because the compiler is not entitled to remove even a single element out of those for its purposes.
How acceptable it is depends on your ability to declare an in-range (for the data type) element as the "impossible" element. Being able to use an in-range element is more efficient, but less general. In this case, simply by declaration Ted says empty strings are not valid. The next time he does this, they may be, and the technique would have to be adapted to that. A library that uses some equivalent to Option or Maybe is a good safe default for a library, of course. Another safe default is to create a new array and return that, too. It's not that hard to end up in a place where the safe default library is not suitable, although nowadays it takes enough data to choke a horse to get there since our computers are so darned fast.
> ISTR Rust implements a specialization on pointers
Yes, and NonZeroU8 for Option<NonZeroU8> and friends:
https://doc.rust-lang.org/std/num/struct.NonZeroU8.html
Yes, and NonZeroU8 for Option<NonZeroU8> and friends:
https://doc.rust-lang.org/std/num/struct.NonZeroU8.html
"All solutions here work in place, using the tombstone technique to create a sparse array, then compacting it later. "
It just looks like the compacting step, creating the final array without the empty strings, has been omitted.
It just looks like the compacting step, creating the final array without the empty strings, has been omitted.
At least he mentions the name of his technique: setting tombstones.
Of course it's highly problematic not to explain why he choose "" as tombstone. It looks like a legal array value to me, so offline compaction will have a hard time to separate a tombstone from an empty string. Without documentation and assertions that "" is not a legal value on insert, certainly a bug.
But he fails to list other common useful techniques, without tombstones:
1) if it's the first index to be removed, just advance the array pointer by one, and keep the original pointer separate for the final free call. very useful for strings, cutting off prefixes.
2) sparse arrays: he mentioned it, but he doesn't use it in his code. Just leave out the hole. very useful for matrixes.
3) temporary hashes. if the array is long (like >256), use a temp. hash to find duplicates.
4) copy to new array, leaving out the duplicates. mostly together with a temp. hash. but for short arrays a linear search is also doable. he showed the linear search, but only with tombstones. This is the functional approach, always copy instead of destructive modifications. This is done in offline compaction.
5) for large arrays use a bloom filter to find dups. can be tuned to the best percentage. (This is what I used in my file deduper, which turned out better than normal hashes)
Of course it's highly problematic not to explain why he choose "" as tombstone. It looks like a legal array value to me, so offline compaction will have a hard time to separate a tombstone from an empty string. Without documentation and assertions that "" is not a legal value on insert, certainly a bug.
But he fails to list other common useful techniques, without tombstones:
1) if it's the first index to be removed, just advance the array pointer by one, and keep the original pointer separate for the final free call. very useful for strings, cutting off prefixes.
2) sparse arrays: he mentioned it, but he doesn't use it in his code. Just leave out the hole. very useful for matrixes.
3) temporary hashes. if the array is long (like >256), use a temp. hash to find duplicates.
4) copy to new array, leaving out the duplicates. mostly together with a temp. hash. but for short arrays a linear search is also doable. he showed the linear search, but only with tombstones. This is the functional approach, always copy instead of destructive modifications. This is done in offline compaction.
5) for large arrays use a bloom filter to find dups. can be tuned to the best percentage. (This is what I used in my file deduper, which turned out better than normal hashes)
> not to explain why he choose "" as tombstone
Because his "neutral pseudocode" (go) doesn't allow setting the string entries in an array to nil. You have to have some value, so commonly you'd use "".
Because his "neutral pseudocode" (go) doesn't allow setting the string entries in an array to nil. You have to have some value, so commonly you'd use "".
But one can not add an empty string to the array which is an obvious bug.
There are slices in go which should be used in this case.
There are slices in go which should be used in this case.
It's a toy example in a semi-funny (or trying) post. Did you really expect handling of all the edge cases?
No because it's Ted Unangst writing about "Removing Array Duplicates", the guy who added string arguments being comma-splitted at run-time instead of using safe and fast bitmasks to new OpenBSD API's. So we know already that he has no idea what he's doing, and shouldn't be let to any important API in serious projects.
But he writes like he has an idea what he's doing, so I had to explain the common cases for this problem. Using tombstones is a special case and you need to be lucky to have such a special illegal value available. Most cases don't allow it, esp. in strongly typed languages.
But he writes like he has an idea what he's doing, so I had to explain the common cases for this problem. Using tombstones is a special case and you need to be lucky to have such a special illegal value available. Most cases don't allow it, esp. in strongly typed languages.
Semisorting, and then running a filter to remove duplicates (which will be consecutive after the semisort) can solve this problem in O(n) expected work & space and O(log n) depth w.h.p. AFAIK the approach is reasonably practical as well. Note that the algorithm is not in-place.
Paper: https://people.csail.mit.edu/jshun/semisort.pdf
Paper: https://people.csail.mit.edu/jshun/semisort.pdf
Because the 'neutral pseudocode' was actually valid Go code I just benchmarked it:
(The 'alt' implementation is my own and maybe not what the author had in mind with 'a searchable data structure to record seen entries'.)
BenchmarkDedupe1-4 3000000 521 ns/op
BenchmarkDedupe2-4 5000000 275 ns/op
BenchmarkDedupe3-4 500000 3337 ns/op
BenchmarkAlt-4 1000000 3174 ns/op
(The 'alt' implementation is my own and maybe not what the author had in mind with 'a searchable data structure to record seen entries'.)
Benchmark times are going to vary quite a lot with size of array and number of unique elements so recording times for one specific size of array doesn’t say much.
To actually be useful, the benchmark should provide variations in total sequence size and frequency of duplicates.
Another alternative: only loop looking for duplicates when a Bloom filter (https://en.wikipedia.org/wiki/Bloom_filter) tells you you may have seen an item before.
O(n²) in theory, but typically a lot faster in practice, at small fixed (semi-fixed, if you size the filter based on the size of the input) overhead.
Also requires you to be able to normalize you strings (for strings, lowercasing or uppercasing may not be enough, depending on culture)
O(n²) in theory, but typically a lot faster in practice, at small fixed (semi-fixed, if you size the filter based on the size of the input) overhead.
Also requires you to be able to normalize you strings (for strings, lowercasing or uppercasing may not be enough, depending on culture)
That's "The alternative which shall not be named" and chances are you'd just use a set as your secondary data structure, there's limited point to using a bloom filter unless the input sequence is absolutely humongous.
It depends entirely on what you need to guarantee. Using a hash tabel you guarantee with a very high probability that you only remove duplicated elements. If you need 100% guarantee, then you must do something else.
Hash tables don’t work in a way that you assume here. Original keys don’t get lost, so you can check whether a key is actually in the table or just makes a collision.
In its simplest case, HT is an array1 of array2s of key-value pairs, where array1 is indexed via [hash(key) % a1.length] and then array2 (aka bucket) is searched linearly for a given key by comparing contents.
In its simplest case, HT is an array1 of array2s of key-value pairs, where array1 is indexed via [hash(key) % a1.length] and then array2 (aka bucket) is searched linearly for a given key by comparing contents.
A hash table does not need to have a collision resolution strategy. It's only definition is key/value pair. That you can have buckets function to avoid collisions is "extra" so to speak.
C# linq .Distinct() does not do that, it only checks on the key.
C# linq .Distinct() does not do that, it only checks on the key.
A hash table is a well-known term that covers multiple algorithms, but I never seen one that worked the way you describe. False positive lookups is a property of bloom filter-like struct, not of a hash table. Using false positives to remove duplicates would be wrong indeed.
Ed: I missed “It's only definition is key/value pair” part. No, that’s called key-value list or table. Hash table uses hashes of keys to partition itself into quick lookup segments - that’s the point.
Ed: I missed “It's only definition is key/value pair” part. No, that’s called key-value list or table. Hash table uses hashes of keys to partition itself into quick lookup segments - that’s the point.
> A hash table does not need to have a collision resolution strategy.
A hash table absolutely needs a collision resolution strategy, the collision in question being different keys having the same hash.
> C# linq .Distinct() does not do that, it only checks on the key.
…?
There's nothing other than a key, Distinct stores items from the source iterator into a set.
A hash table absolutely needs a collision resolution strategy, the collision in question being different keys having the same hash.
> C# linq .Distinct() does not do that, it only checks on the key.
…?
There's nothing other than a key, Distinct stores items from the source iterator into a set.
If you sort objects as you insert them into the membership list of the bloom filter, it's O(n log n) for a comparison based sort and O(n) for a top down discriminating sort. However, if you sort the list, then you don't need the bloom filter anymore.
I'm not sure if this actually would be faster in practice though. It will have heavy, heavy constants if your keys are not trivial.
I'm not sure if this actually would be faster in practice though. It will have heavy, heavy constants if your keys are not trivial.
Why would sorting objects matter when inserting them into the Bloom filter? The filter is independent of insertion order.
The notion of O(n) for a "top down discriminating sort" is outrageous and needs serious justification!
The notion of O(n) for a "top down discriminating sort" is outrageous and needs serious justification!
They posted sources there: https://news.ycombinator.com/item?id=19642485
They also linked to Data.Discrimination, which assets to provide O(n) `nub` (aka deduplicate): http://hackage.haskell.org/package/discrimination-0.3/docs/D...
They also linked to Data.Discrimination, which assets to provide O(n) `nub` (aka deduplicate): http://hackage.haskell.org/package/discrimination-0.3/docs/D...
As I implied, I think the bloom filter is somewhat superfluous to any solution to this problem.
It is 20 year old computer science often discussed in upper division compsci courses.
Something similar(?) would be to use a Go map to keep track of which items have already been seen. It would only need one pass through the array, with some map hashing overhead.
I gave this a shot in Perl 6 as can be found at https://gist.github.com/8a58c3af3520e127fe7852d834e5e0fa
I build a very simple^1 non-balancing binary tree and skip any insertation that would reproduce a duplication. Since the tree is not balanced, the order of insertation is preserved. Search time goes up without a good balance but the tree will have the same amount of nodes than unique elements in the original array. Each element is 6 machine words plus some gc overhead. If it's faster or slower then a hash table depends on the ratio between elements in the array and the number of duplicates.
1) Perl 6 got a general compare operator that works well with a wide range of types. So I don't have to care about types at all. If I would have to care I could monkeytype the operator candidates for custom types into the language.
I build a very simple^1 non-balancing binary tree and skip any insertation that would reproduce a duplication. Since the tree is not balanced, the order of insertation is preserved. Search time goes up without a good balance but the tree will have the same amount of nodes than unique elements in the original array. Each element is 6 machine words plus some gc overhead. If it's faster or slower then a hash table depends on the ratio between elements in the array and the number of duplicates.
1) Perl 6 got a general compare operator that works well with a wide range of types. So I don't have to care about types at all. If I would have to care I could monkeytype the operator candidates for custom types into the language.
Default &transform function should be *.fc
The one-liner solution is: @data.unique(as => &fc)
The one-liner solution is: @data.unique(as => &fc)
My first thought was using a map to store what's been seen and run through the list keeping copying the values that haven't been seen to a new list in order or just marking them as dupes in place with the empty string.
This seems to be the "alt" case and is dismissed by the author but would like to hear a fuller explaination of why this is a problem?
This seems to be the "alt" case and is dismissed by the author but would like to hear a fuller explaination of why this is a problem?
Too slow, too much hashing, too many copies.
It will probably be faster than the code in the article.
How?
It requires a single pass through the array, whereas the article suggests different approaches that all go through the array multiple times (or even O(n^2)). For small lists this is probably ok, but for big lists it is a very slow approach.
Edit: I would probably use a bloom filter for this.
Edit: I would probably use a bloom filter for this.
It requires a single linear pass instead of a convoluted sort.
... what sort? Are talking about the same thing here?
The code in the article has a sort in it.
Why would that be "more copies" than building up a hash table is what I don't get.
It requires many passes through the list, and even O(LogN) is probably enough to make it slower than a hash based O(n) approach depending on list size. Hashing is fast. If space is an issue, just use an appropriately sized bloom filter.
No I think it would be actually faster and simpler.
That's not really a fuller explaination.
What more is there to explain? How is it not immediately obvious that the GP's approach is inferior the the OP's?
It really is not obvious how OP's approach is faster than GP's approach.
OP's approach is by sorting which has complexity of O(m * N * logN) where m is the average key length and N is the size of the array. GP's approach with hash lookup has a complexity of O(m * N) where m is the average key length and N is the size of the array. The extra logN term makes OP's approach slower.
OP's approach is by sorting which has complexity of O(m * N * logN) where m is the average key length and N is the size of the array. GP's approach with hash lookup has a complexity of O(m * N) where m is the average key length and N is the size of the array. The extra logN term makes OP's approach slower.
Of course, for low values of N the constants dropped from the big-O notation start to matter. For very small values of N and a random-access input, even an O(N^2) approach may be optimal (for each input element, check for equality against previous elements of the input, output if no hit).
Well, when N is small, any complexity analysis is moot.
Yes, but it's easy to forget and still apply it blindly in regimes where it's not really applicable anymore.
Many hash tables use tree structures rather than actual key hashing because it turns out that this is usually faster on modern machines. So many hash tables are technically O(n log n) for some high log factor like 32.
I've posted what I think is the optimal solution and the research behind it above, if you're curious how to hit O(n) time without brutal constants.
I've posted what I think is the optimal solution and the research behind it above, if you're curious how to hit O(n) time without brutal constants.
Since the array size is known ahead of time, it's easy to initialize a hash table with an optimal capacity. No need to use fancy tree structure.
The size of the table isn't the trick. It's the perfect hash function that you want. If you have that then you've already solved the problem at hand.
From TFA: "These examples are written in neutral pseudocode that should be adaptable to most any imperative language."
False. The examples are written in Go, a generally easy to read language. Maybe the author thought it is a funny joke. Low bar :)
False. The examples are written in Go, a generally easy to read language. Maybe the author thought it is a funny joke. Low bar :)
> The examples are written in Go, a generally easy to read language.
But not necessarily so, #3 and #4 are just godawful.
edit: and as you point out below, Go's sorting interface is completely alien and doesn't easily translate to any other language.
But not necessarily so, #3 and #4 are just godawful.
edit: and as you point out below, Go's sorting interface is completely alien and doesn't easily translate to any other language.
Agreed, the sort interface in go is one of the worst parts, and doesn't translate to any other language I'm familiar with. The article was mildly entertaining but by the end left much to be desired.
Shoulda just gone with python, rust, c, crystal lang.. anything else for sorting!
Shoulda just gone with python, rust, c, crystal lang.. anything else for sorting!
[deleted]
[deleted]
Came here to say the same thing. xD
Why don't you just use a set?
Constructing sets has a running time, too. All you're really doing when you build a set is sorting.
That's not true for any reasonable set implementation. Sorting is unnecessarily time-intensive for maintaining distinctness. Hashing is sufficient.
Which set implementation are you referring to?
And also remember the context here: you're removing duplicate value's from an array. So you're inserting N items into a set. If the set insertion or enumeration involves even a O(log(n)) operation, you're at nlogn.
And also remember the context here: you're removing duplicate value's from an array. So you're inserting N items into a set. If the set insertion or enumeration involves even a O(log(n)) operation, you're at nlogn.
A set could literally be:
type HashSet<K> = HashMap<K, ()>;
In which case it has all the properties of a hashmap except it doesn't use values. That's what we need for this problem.
type HashSet<K> = HashMap<K, ()>;
In which case it has all the properties of a hashmap except it doesn't use values. That's what we need for this problem.
A hashset has O(1) membership testing and amortized O(1) element insertion.
But it requires a perfect hash. You need to guarantee over any potential input that you don't have collisions.
How do you do that over all inputs? If there is a generalized non-probabilistic perfect hash function I am unaware of it and I'd like to be aware of it.
How do you do that over all inputs? If there is a generalized non-probabilistic perfect hash function I am unaware of it and I'd like to be aware of it.
No, it doesn't require a perfect hash. There are collision mitigations. In practice there several that can get to O(1). I'm not sure if there is a way to achieve O(1) in the worst case. But the worst case can be made arbitrarily unlikely, even against adversarial inputs.
> I'm not sure if there is a way to achieve O(1) in the worst case.
Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like saying, "It is blue except when you look at it."
But you don't need these mitigations (most of which are O(log n)) because you never had the hash table. You should look at American Flag sort, because morally it's actually doing something that closely approximates what you're thinking about. That's why I brought it up elsewhere in the thread.
Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like saying, "It is blue except when you look at it."
But you don't need these mitigations (most of which are O(log n)) because you never had the hash table. You should look at American Flag sort, because morally it's actually doing something that closely approximates what you're thinking about. That's why I brought it up elsewhere in the thread.
It's O(1) in the sense that git works. Git uses "commit hashes". If these collide, something would break, on par with the universe stopping working, I presume. But I'm sure, since this never actually happens in practice.
https://arstechnica.com/information-technology/2017/02/water...
It was a bad design to rely on hashing algorithms to never collide. But it's worth noting that even SHA1 is much more robust than most hash table algorithms, which are meant to run even faster.
It was a bad design to rely on hashing algorithms to never collide. But it's worth noting that even SHA1 is much more robust than most hash table algorithms, which are meant to run even faster.
You don't even need the amortized insertion. You know the max set size from the original list of items.
But you don't get to pick the input type. What's your adaptive, non-probabilistic perfect hash function for all data types?
I'm only aware of partial solutions to that problem, of which top down Radix sort is in fact one. But once you do that you don't need the table to solve the problem anyways, you've already got your discrimination function and you'd just pass that over the data.
I cannot see why the tabular part of the hash table proposed solution is anything more than cargo culting.
I'm only aware of partial solutions to that problem, of which top down Radix sort is in fact one. But once you do that you don't need the table to solve the problem anyways, you've already got your discrimination function and you'd just pass that over the data.
I cannot see why the tabular part of the hash table proposed solution is anything more than cargo culting.
Also, sorting is O(n), which is exactly what your perfect hash table would be, recursive.
The problem with deduplicating the data can be changed into another problem: ensuring we won't add the data if it would be duplicated.
So instead of trying to deduplicate the array from author's example, I'd change the 'add()' method so that it searches through the whole set and doesn't add the data if it's already added.
So now it doesn't require deduplication code at all.
So instead of trying to deduplicate the array from author's example, I'd change the 'add()' method so that it searches through the whole set and doesn't add the data if it's already added.
So now it doesn't require deduplication code at all.
That's what I though as well. In which case it's better to just keep it in a set-like structure initially, or just dump your entire array into a set afterwards. That's linear time, which is loads better than any of the solutions presented.
I can't help but think that deduplicating once after you've got your array ready to process is better than checking each time when you add if the value is already there.
The typical way to solve this problem would be to keep the data stored in a normalized relational database. There would be a Customer table and a Visits table. Since the data is normalized, the Customer table would contain only one entry per customer. There would be no need to dedupe the data if it is kept in this format.
If moving the data into a normalized relational database is not an option, the next best option that I can think of is to use a hash table (as mentioned elsewhere in the HN comments). However, I can't imagine working on a system where it would make sense to write a custom solution for each type of data query (unless I was working on a database system).
If moving the data into a normalized relational database is not an option, the next best option that I can think of is to use a hash table (as mentioned elsewhere in the HN comments). However, I can't imagine working on a system where it would make sense to write a custom solution for each type of data query (unless I was working on a database system).
three and four might be close to the
https://en.wikipedia.org/wiki/Schwartzian_transform
but I like the Schwartzian better :-)
https://en.wikipedia.org/wiki/Schwartzian_transform
but I like the Schwartzian better :-)
Learning about the Schwartzian transform was one of life's memorable "ah hah" moments for me. There's a whole set of higher-order layers to this programming thing!
As others have said, language choice matters.
As others have said, language choice matters.
An interesting question is how can you parallelize it? Suppose the data is huge, but you have many available threads, or machines..
Suppose there are N nodes, each of which owns part of the array. So one way is for each node to broadcast each entry to all of the other nodes. As each node receives a broadcast, it checks its array for duplicates, and deletes them.
Suppose there are N nodes, each of which owns part of the array. So one way is for each node to broadcast each entry to all of the other nodes. As each node receives a broadcast, it checks its array for duplicates, and deletes them.
[deleted]
The only thing this post did for me was entrench my thought that I'd rather write Rust over Go.
As ugly as Rust can be to look at, I'd rather solve this in 5 lines of Rust that make sense than read through any of those Go solutions.
As ugly as Rust can be to look at, I'd rather solve this in 5 lines of Rust that make sense than read through any of those Go solutions.
[deleted]
Isn’t a loop k from 1 to n, with an inner loop k to n, actually order n! (The article says O n^2) ?
Adding up 1+2+...+n equals to n(n-1)/2, which when converted to an order becomes O(n^2).
An outer loop [1, n] and inner loop [k, n] is cheaper than an outer loop [1, n] and inner loop [1, n], and this second pair of loops runs in O(n^2) time.
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).