4 ms·
Another alternative: only loop looking for duplicates when a Bloom filter (https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter
by Someone 8y ago
Another alternative: only loop looking for duplicates when a Bloom filter (https://en.wikipedia.org/wiki/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)
- KirinDave 8y agoIf 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.
- millstone 8y agoWhy 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!
- masklinn 8y agoThey posted sources there: https://news.ycombinator.com/item?id=19642485 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/Data-Discrimination.html#v:nub http://hackage.haskell.org/package/discrimination-0.3/docs/D...
- KirinDave 8y agoAs I implied, I think the bloom filter is somewhat superfluous to any solution to this problem.
- KirinDave 8y agoIt is 20 year old computer science often discussed in upper division compsci courses.
- masklinn 8y agoThat'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.
- hvidgaard 8y agoIt 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.
- wruza 8y agoHash 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.
- hvidgaard 8y agoA 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.
- masklinn 8y ago> 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.
- wruza 8y ago
- incompatible 8y agoSomething 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.