Removing Array Duplicates
flak.tedunangst.com
flak.tedunangst.com
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).
Possibly the high constant cost, making them less than optimal for short sequences?
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....
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.
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.
Can you give me an example, I'm curious to know :)
_, ok := m[thing_to_be_found]
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 ;-)
found[key] = struct{}{}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.
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.
1+2+4+...+2^k = O(2^k)See https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...
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.
int hash(Object anything) { return 3; }
In practice, I think more types are hashable than are comparable.
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).
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).
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.
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.
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.
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.
The read side barely matters for the use case we're discussing.
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.
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.
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.
How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.
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?
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.)
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.
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)) 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";
};
}You can just return
seen.insert(lower).second
as insert function return a pair<iterator, bool>
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.
filter(|string| {set.insert(string)}
as insert return a bool.
* 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
banana 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);
}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();
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);
}
let dedup = strings.into_iter().map(|s| s.to_lowercase()).collect::<HashSet<_>>().into_iter().collect::<Vec<_>>(); set.insert(string.to_lowercase())
https://play.rust-lang.org/?version=stable&mode=debug&editio...
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...
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.
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 thought go had much bigger standard library. Go has archive, compression, crypto, database, encoding, hash, html, and net etc.
Learn from your mistakes.
seen := make(map[string]bool)
for n, s := range array {
if seen[strings.ToLower(s)] {
array[n] = ""
} else {
seen[strings.ToLower(s)] = true
}
} 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
}
}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... :)
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.
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 :)
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.
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...
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]]It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.
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.
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.
Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.
def distinct(l):
seen = set()
for s in l:
if s.lower() not in seen:
yield s
seen.add(s.lower()) unique_array = list(set(non_unique_array))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.
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.
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).
It just looks like the compacting step, creating the final array without the empty strings, has been omitted.
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.
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)
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.
Yes, and NonZeroU8 for Option<NonZeroU8> and friends:
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)
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 "".
There are slices in go which should be used in this case.
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.
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'.)
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)
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.
The notion of O(n) for a "top down discriminating sort" is outrageous and needs serious justification!
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...
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.
C# linq .Distinct() does not do that, it only checks on the key.
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.
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.
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.
The one-liner solution is: @data.unique(as => &fc)
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?
Edit: I would probably use a bloom filter for this.
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.
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.
False. The examples are written in Go, a generally easy to read language. Maybe the author thought it is a funny joke. Low bar :)
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.
Shoulda just gone with python, rust, c, crystal lang.. anything else for sorting!
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.
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.
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.
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 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.
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.
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.
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).
https://en.wikipedia.org/wiki/Schwartzian_transform
but I like the Schwartzian better :-)
As others have said, language choice matters.
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.
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.