Hacker News Reader

Comment by cogman10 | Hacker News Reader

Lol, yeah I get this quoted sometimes merely for suggesting the right data structure to use.

"Use a set instead of a list, it's faster". "that's premature optimization!"

Usually this criticism doesn't even hold water if you put performance aside, since a set will often have nicer ergonomics if you find yourself reaching for it. I see far too much code that is like items.remove((item) => item == value) and if you're using the proper datastructure you don't have to handroll your implementations each time, because they are provided by default.

The real premature optimization is using List instead of Set for guaranteed small sizes, since List is going to outperform Set in those cases.

That depends on how list and set are implemented.

Premature pessimization.

Except in your example I’ve had numerous cases where bugs have been introduced because the developer’s primary thinking to pick a set was “fast” and “no duplicates”, only to later realize that order of items is important. And looking back at their choice, dealing with 5-20 items, using a list and checking contains() not only had no performance impact but better reflects the intent of “no duplicates”. Instead the set is left in place and the dev fixing it usually copies the results in a list to be sorted the same order prior to being in the set...

I've never seen this example. There are set implementations which maintain order, but in my experience it's fairly rare to both need "no duplicates" and "items inserted maintain order".

It's fairly easy to remove the set and replace it with something else if this does come up.

Maybe I’m misunderstanding, but isn’t it pretty common to e.g. have a list of non-duplicate items on screen which have a specific order they’re supposed to be displayed in which can be changed as a result of user actions (like adding new items or editing existing ones)?

Maybe? Perhaps that's just a part of my daily dev that is lacking. I generally work on the backend and not the frontend. I could envision how keeping stuff in the same order on a UX would be important.

Doesn't seem like it'd be the general case though. And it seems like it'd be fairly obvious when something like this applies.

Hash tables contain a list internally and sets are hash tables with just the keys in them so they are already lists. With a level of indirection, it's easy to make them insertion ordered just like normal lists. Just make the hash table a map of keys to list indexes. That way the table can be rehashed freely while the internal list remains ordered.

Reply on news.ycombinator.com