4 ms·
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
by hellllllllooo 7y ago
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?
- roel_v 7y agoToo slow, too much hashing, too many copies.
- bjoli 7y agoIt will probably be faster than the code in the article.
- roel_v 7y agoHow?
- saagarjha 7y agoIt requires a single linear pass instead of a convoluted sort.
- roel_v 7y ago... what sort? Are talking about the same thing here?
- saagarjha 7y agoThe code in the article has a sort in it.
- KirinDave 7y agoWhy would that be "more copies" than building up a hash table is what I don't get.
- bjoli 7y agoIt 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.
- bjoli 7y agoIt 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.
- hellllllllooo 7y agoThat's not really a fuller explaination.
- roel_v 7y agoWhat more is there to explain? How is it not immediately obvious that the GP's approach is inferior the the OP's?
- ww520 7y agoIt 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.
- magicalhippo 7y agoOf 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).
- ww520 7y agoWell, when N is small, any complexity analysis is moot.
- magicalhippo 7y agoYes, but it's easy to forget and still apply it blindly in regimes where it's not really applicable anymore.
- KirinDave 7y agoMany 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.
- fluffycat 7y agoNo I think it would be actually faster and simpler.