Is there an efficient, idiomatic way to remove duplicates in a slice?If possible, I do want to retain the original order of items.
Is there an efficient, idiomatic way to remove duplicates in a slice?If possible, I do want to retain the original order of items.
Do we know anything about the structure of the slice?
It is inherent in the general notion that there must be a comparison of a new item with existing ones to establish uniqueness. Even so, knowledge about the structure of the input can make this comparison easier.
If the input is already ordered, then testing against the prior element is a test against all elements.
If the input is integers in a small range then a bit mask presence test is good.
If avoiding allocation is important one could sort the list O(n log n) and then scan it O(n)
The hash (map/dictionary) approach is good, general, and slightly more space efficient with a slice of struct{} since presence testing is all that is necessary.
An O(n) scan to build a histogram would let you know about ranges and potential sections for subsequent processing.
Many well-known approaches.
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Ø there is good gist.
Ø this algorithm 10x faster …
I don’t believe it is faster as the slice size increases. What you propose is O(N**2) vs O(N). Try a test with a slice 10 or 100 times the size.
John
John Souvestre - New Orleans LA
--