3 ms·
> Avoid O(n), try O(1) Be careful with this, as dictionaries are not really O(1), in the worst case, it can be actually O(n). When your code heavily evolves a
by TN1ck 9y ago
> Avoid O(n), try O(1)
Be careful with this, as dictionaries are not really O(1), in the worst case, it can be actually O(n). When your code heavily evolves around the 'fact' that it's O(1) try to make a version with a simple array iteration and compare which is faster.
- BillinghamJ 9y agoI believe a good rule of thumb is that looping over an array will generally be faster than using a hash map until you have around ~1,000 items. Very approximate and dependent on the case obviously, but I always find it surprising how far you can go with just a simple array.
- zaarn 9y agoFrom experience I would say it's closer to 100 items, though this is using Go as benchmark. 100 items is also what I would expect considering CPU caches. From 100 to 1000 items the array performance is not massively worse and shouldn't matter much but a dictionary can beat it (by a tiny bit). If you're over 1000 definitely use a dictionary or tree.