[Jprogramming] order

[Raul Miller]

On Sat, Apr 9, 2022 at 5:27 AM Elijah Stone <elronnd at elronnd.net> wrote:
> Hashing is O(1) (or, if you prefer, O(#y) for ~.y, same as sorting).  A
> sufficiently smart(tm) hash function will avoid inordinate collision
> rates, so I am not sure what worst case behaviour you are referring to.

Collision rates are indeed an important constraint.

> If you are able to share your 1e8-sized dataset where sorting before
> removing duplicates was faster than using ~., that would be great.  Maybe
> I can make it faster :)

That was an intermediate result from almost ten years ago.

Anyways, it's worth spending a little time thinking about worst case
performance.

Thanks,

-- 
Raul