21–30 of 332 posts
"Write stupid code that uses smart objects" That's a good one. It's amazing how much complexity can be created by using the wrong abstractions.
I frequently find that, when refactoring especially, you find a lot of big ol' god objects that are incomprehensible. But when you break them down into 5-10 small objects, suddenly the operation they were trying to do makes perfect sense.
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Are you sure that std::unordered_map is faster than std::vector? Did you measure?
Every time you access an element in std::vector, you also access nearby ones (thanks to L1 cache, as well as CPU-prefetching of in-line data).
In contrast, your std::unordered_map or hash-table has almost no benefits to L1 cache. (It should be noted that linear-probing, despite being a O(N^2) version of hash-tables worst-case, is actually one of the better performers due to L1 cache + prefetching)
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
The philosophy is really to not waste time implementing optimizations that may not be necessary. Naturally you should reach for the best tool you have in your tool box. So if you language of choice has a hashmap that can be used with no additional work, go for it. But don't wait two days rolling your own red-black tree because it might be better.
It turns out rule 5 (Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident) is both true but also hard. Eric Evans' Domain Driven Design is a good book on the topic.
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Don’t write complex optimizations until you know you need them, but I think defaulting to code with good O(N) complexity, where it’s simple to do so, is a good default.
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
If I know beforehand we'll handle a lot of data, I can pick something fast and complex to begin with, but that effort is probably mostly a waste.
> "write stupid code that uses smart objects". Writing stupid code is actually really difficult. For me, it takes a little bit of iterating before I know just the right place to insert stupid.
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Using array based data structures also get you more cache hits. For smaller data sets, this may well be faster than a fancy algorithm.
Rule 5 seems to mirror one of my favorite insights from Alexander Stepanov: > In 1976, still back in the USSR, I got a very serious case of food poisoning from eating raw fish. While in the hospital, in the state of delirium, I suddenly realized that the ability to add numbers in parallel depends on the fact that addition is associative. (So, putting it simply, STL is the result of a bacterial infection.) In other wo…