13 ms·
Removing Array Duplicates
- djpilot 8y agoFrom 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 :)
- nightraven97 8y agoCame here to say the same thing. xD
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- masklinn 8y ago> 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.
- djpilot 8y agoAgreed, 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!
- KirinDave 8y agoThis 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/Data-Discrimination.html#v:nub 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.
- viraptor 8y agoDo you have some good description / paper for that algorithm? The code is not super clear.
- KirinDave 8y agoIf 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.pdf https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p... [1]: https://www.youtube.com/watch?v=pOKy3RZbSws https://www.youtube.com/watch?v=pOKy3RZbSws
- viraptor 8y agoI feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
- twanvl 8y agoThis 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): class Ord a where compare :: a -> a -> Ordering class Bucketable a where splitIntoBuckets :: (b -> a) -> [b] -> [[b]]
- Someone 8y agoAnother 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.
- 8y ago
- alkonaut 8y agoThe 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).
- incompatible 8y ago"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.
- desdiv 8y agoHis 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.
- Someone 8y agoThat 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)
- jerf 8y ago
- rurban 8y agoAt 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)
- viraptor 8y ago> 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 "".
- hellllllllooo 8y agoMy 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?
- kccqzy 8y agoUsually a fine approach would be to construct a hash table as we walk the array, and if the element is not seen put it in the hash table, otherwise "remove" it by setting it to the empty string. If the hash table implementation is good, we can pretty much find out whether an entry has been seen before in O(1) time, making the whole process O(n). That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array. You don't generally have to copy the original values (usually you just copy a pointer).
- masklinn 8y ago> That's what the author called "alt" and I don't understand why the author objects to it. The memory needed is usually proportional to the number of distinct elements in the original array. Possibly the high constant cost, making them less than optimal for short sequences?
- theclaw 8y agoIf I recall correctly this is exactly what .net’s ‘Distinct()’ LINQ extension method does.
- masklinn 8y agoYes: https://github.com/dotnet/corefx/blob/8750960d3fafa46a9b838c351e995a01fa8b599f/src/System.Linq/src/System/Linq/Distinct.cs https://github.com/dotnet/corefx/blob/8750960d3fafa46a9b838c...
- deleted 8y ago[deleted]
- neel_k 8y ago> That's what the author called "alt" and I don't understand why the author objects to it. His "neutral pseudocode" is Go, which lacks good support for parameterized types. As a result there would be quite a bit of boilerplate code in doing things this way. This is also why the author remarks "For trivial examples this works well, but for more complicated types with complex keys, it may require creating new types." This post is a nice example of why it is important to eliminate friction from a a language if you want to get people to use a particular feature. However, the goal of removing friction interacts poorly with an observation Bjarne Stroustrup once made, that: * For new features, people insist on LOUD explicit syntax. * For established features, people want terse notation. That is, when a feature is new to a programmer, they want it to be loud to remind them that something unexpected is happening, and once it is known to them they want it to disappear so they can focus on their problem -- and if it doesn't disappear, the solution using it will be so noisy they won't do it that way. I expect the ultimate solution to this problem involves IDE design, rather than language design....
- efitz 8y agoIsn’t a loop k from 1 to n, with an inner loop k to n, actually order n! (The article says O n^2) ?
- ishitatsuyuki 8y agoAdding up 1+2+...+n equals to n(n-1)/2, which when converted to an order becomes O(n^2).
- joppy 8y agoAn 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.
- moab 8y agoSemisorting, 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 https://people.csail.mit.edu/jshun/semisort.pdf
- emmelaich 8y agothree and four might be close to the https://en.wikipedia.org/wiki/Schwartzian_transform https://en.wikipedia.org/wiki/Schwartzian_transform but I like the Schwartzian better :-)
- kwindla 8y agoLearning 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.
- saagarjha 8y agoThe 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.
- Nimelrian 8y agoYup, 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"; }; }
- johannkokos 8y agoif (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>
- Nimelrian 8y agoAnd today I learned something new. Been a long time since I wrote my last lines of C++ anyway.
- rndgermandude 8y agoBonus points for using emplace() instead of insert
- hwj 8y agoBecause the 'neutral pseudocode' was actually valid Go code I just benchmarked it: BenchmarkDedupe1-4 3000000 521 ns/op BenchmarkDedupe2-4 5000000 275 ns/op BenchmarkDedupe3-4 500000 3337 ns/op BenchmarkAlt-4 1000000 3174 ns/op Source: https://gitlab.com/hwj/rad https://gitlab.com/hwj/rad (The 'alt' implementation is my own and maybe not what the author had in mind with 'a searchable data structure to record seen entries'.)
- dan-robertson 8y agoBenchmark 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.
- masklinn 8y agoTo actually be useful, the benchmark should provide variations in total sequence size and frequency of duplicates.
- deleted 8y ago[deleted]
- gfldex 8y agoI gave this a shot in Perl 6 as can be found at https://gist.github.com/8a58c3af3520e127fe7852d834e5e0fa 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.
- 0rac1e 8y agoDefault &transform function should be *.fc The one-liner solution is: @data.unique(as => &fc)
- self_awareness 8y agoThe 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.
- bryanrasmussen 8y agoI 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.
- Adamantcheese 8y agoThat'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.
- leshow 8y agoWhy don't you just use a set?
- KirinDave 8y agoConstructing sets has a running time, too. All you're really doing when you build a set is sorting.
- recursive 8y agoThat's not true for any reasonable set implementation. Sorting is unnecessarily time-intensive for maintaining distinctness. Hashing is sufficient.
- KirinDave 8y agoWhich 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.
- recursive 8y agoA hashset has O(1) membership testing and amortized O(1) element insertion.
- haxton 8y agoYou don't even need the amortized insertion. You know the max set size from the original list of items.
- KirinDave 8y agoBut 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.
- _zachs 8y agoThe 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.
- hnruss 8y agoThe 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).
- jhallenworld 8y agoAn 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.
- deleted 8y ago[deleted]