3 ms·

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 opti

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!"

saagarjha 3y ago
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.
_dain_ 3y ago
Premature pessimization.
The_Colonel 3y ago
The real premature optimization is using List instead of Set for guaranteed small sizes, since List is going to outperform Set in those cases.
- marcellus23 3y ago
  That depends on how list and set are implemented.
neandrake 3y ago
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...
- cogman10 3y ago
  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.
  - jwells89 3y ago
    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)?
    - cogman10 3y ago
      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.
- matheusmoreira 3y ago
  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.

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!"

saagarjha 3y ago

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.

_dain_ 3y ago

Premature pessimization.

The_Colonel 3y ago

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

marcellus23 3y ago
That depends on how list and set are implemented.

neandrake 3y ago

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...

cogman10 3y ago
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.
- jwells89 3y ago
  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)?
  - cogman10 3y ago
    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.
matheusmoreira 3y ago
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.