4 ms·
Worrying about performance of small collections is premature optimization. Using maps or sets nowadays is mostly for clarity, as they are used to solve certain
by krzat 6y ago
Worrying about performance of small collections is premature optimization.
Using maps or sets nowadays is mostly for clarity, as they are used to solve certain kind of problems.
- dragontamer 6y agoI agree with you. But what you're talking about is completely different from what I was responding to originally. If you need a set, use a set. But don't assume that its faster than a std::vector. Even then, std::vector has set-like operations through binary_search or std::make_heap in C++, so it really isn't that hard using a sorted (or make_heap'd) std::vector in practice. -------- Even if you don't plan on doing optimization work, its important to have a proper understanding of a modern CPU. The effects of L1 and prefetching are non-trivial, and make simple arrays and std::vectors extremely fast data structures, far faster than compared to 80s or 90s computers anyway. A lot of optimization advice from the past has become outdated because of the evolution of CPUs. So its important to bring up these changes in discussion, from time to time, to remind others to restudy computers. Things change.
- avasthe 6y ago> sorted std::vector But inserting into sorted std::vector is o(n log n) in worst case right? (As you have to binary search the position and move other elements). But a hash set with linear probing can give O(1) (amortized) access, while usually maintaining an invariant like total_size > 2*n. I don't think that would be such an impact on cache locality. Linear probing doesn't require linked lists. Of course this is given that you have a data structure in standard library. But at this point I think hash sets are pretty standard.
- dragontamer 6y agoYeah, linear probing helps hash-sets a lot on modern CPUs. Perhaps linear probing is a better example of how BigO analysis can go wrong on modern architectures. Inserting into a hashset with linear-probing is O(n) worst-case, while inserting into a linked list is always O(1) (best case, worst case, and average case). And yet, linear probing seems to work out best in practice (with a bit of rigging. The total_size > 2*n invariant is one, but so does Robin-hood hashing if you want to keep the table small) Linear probing vs Linked List implementations of hash-sets seems to be a more clear example of an O(1) vs O(n) anomaly, where the O(n) example is superior.
- avasthe 6y agoI don't think it is the same thing. Inserting into linked list assumes you have found the node to insert in. I don't remember exact details but in hash set with linear probing, the worst case happens quite rarely given the hash function is good one (which are quite sophisticated these days). It is O(1) amortized. The same applies for hash table with chaining too, that all of your keys may go to same bucket given a sufficiently bad hash function. Given the other choices, like (as far as I know) SkipList based or tree based variants, hash sets are obvious choice.
- dragontamer 6y agoI mean "Hash-set with Linked List" vs "Hash-set with linear probing". I realize I was getting lazy with my typing, so lemme try to be more clear this time. Hash-set with Linked List is O(1) all cases. Hash-set with linear-probing is O(n) worst-case insertion. But happens to be faster in practice with circa 2020-style CPUs (especially with Robin Hood insertion) Assume the load-factor to be 90%+, so that we actually get a reasonable difference between the two strategies. We have a situation where O(n) is better than O(1).
- account42 6y ago> Even then, std::vector has set-like operations through binary_search or std::make_heap in C++, so it really isn't that hard using a sorted (or make_heap'd) std::vector in practice. Except std::vector does not enforce the sorted or heap constraints when adding or removing elements so eventually someone working on your code will break them.
- dragontamer 6y agoMake a wrapper class that enforces the invariant.