4 ms·
Wouldn't ordering basically improve lookup performance at the expense of insertion performance? If you don't order the elements, you can just smash the new entr
by Delk 5y ago
Wouldn't ordering basically improve lookup performance at the expense of insertion performance? If you don't order the elements, you can just smash the new entry at the end of the list and be done with it.
Of course that might still be a reasonable trade-off to make. Is there experimental (or experiential) support for getting significant improvements from ordering?
- ternaryoperator 5y agoMany (most?) hash tables are write-once, read-many (caches, databases, etc. among others) so optimizing for reading makes a lot of sense.
- hawk_ 5y agoordered insertion can happen in the "middle" of the list. unordered always has to reach the end (to ensure no duplicate) so it's worse for insertion as well.
- Delk 5y agoGood point. For some reason I didn't think about duplicate checking even though it's pretty obvious.