6 ms·

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^

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.

deleted 6y ago
[deleted]
fabian2k 6y ago
I would not read these rules as anything like suggesting to write O(n^2) code. I think at best I'd read them as favoring O(n) instead of (1) for small n, but I really think that "fancy" algorithms in this case doesn't mean obvious optimizations like this. If you can't guarantee n is small, I think it is entirely sensible to use a dictionary/hash table instead of looping over an array or list. As long as n is small the overhead is probably irrelevant, and it'll prevent surprises if n gets large as you said. And if the difference actually matters, you get back to rule 1 and 2 and measure first anyway.
mav3rick 6y ago
Using array based data structures also get you more cache hits. For smaller data sets, this may well be faster than a fancy algorithm.
- bluGill 6y ago
  This is true only if you are iterating over the entire array often. If you only rarely need to access one data member the array will not be in cache and so you have less to load from memory. Depending on how your data is structured the array may or may not save time even in small sizes.
  - mav3rick 6y ago
    Of course temporal and spatial locality are important.
  - cma 6y ago
    Prefetching still may make it way faster.
coliveira 6y ago
It depends. If you don't need to worry about performance, then it will work. But in some performance-dependent situations, the brute force algorithm will win over the hash table, and the only way to know is measuring which one is better.
fasterpython 6y ago
If it's fairly easy, then I think it still fits the spirit of the rules. KISS and all. On the other hand, the idea that one might be setting traps is slightly weird... if you _know_ 90% that n will be large then pick an algorithm that's efficient (and since it's easy to implement, it's a win-win). If n is always going to be small, then does the choice really matter?
- naet 6y ago
  If N is known small you should favor simplicity and readability over complex optimization.
dimitrios1 6y ago
Yes. If you don't measure, you will never know when the time complexity moves in your favor due to the constant, and other factors. For example, quicksort moves to a O(n^2) algorithm (insertion sort) for the last few iterations of a branch of work(typically n=1000) because this reduces the total sort time.
dragontamer 6y ago
> 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 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)
- zabzonk 6y ago
  Also, creating a hash isn't free. And often ordering is required.
  - dragontamer 6y ago
    > Also, creating a hash isn't free. Hmmm... I argue that the hash is nearly free actually. An unordered_map traversal is probably DDR4 latency bound. That's ~50-nanoseconds (200 clock ticks) per access. What's the CPU going to do in that time? Well, spending 10 to 20 clock ticks on a typical hash algorithm is fine. Then it will wait the other 180 clock ticks for RAM. If you got hyperthreading, maybe the CPU will go to another thread and do meaningful work while waiting for RAM... but... I think you get the gist. Even IF the hash were free, the CPU is waiting for RAM anyway. So you got plenty of time to make that hash worthwhile. Even an integer division/modulo operator (worst case ~80 clock ticks) can fit in there while waiting for RAM, with plenty of room to spare. I guess if everything was in L1 cache, the story is a bit different. A lot of "depends", depends on the data, the access frequency, etc. etc.
- 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 ago
mywittyname 6y ago
Keep in mind that a lot of this was written during an era where even modestly complex data structures/algorithms had to be rolled by hand. 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.
yashap 6y ago
I think, in most cases, if you have n items in memory, and you want to find m of them by id, or some such thing, your default should be to represent the n items as a hashmap, not a list, and look them up from the hashmap. There will be cases where this isn’t the right choice, but it’s a good default. And it’s almost always virtually no extra complexity to represent them this way, i.e. often something as simple as: myMap = myList.groupBy(_.id) 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.
BurningFrog 6y ago
Yeah, I do well writing dumb inefficient code as default, and optimizing it when needed, which is almost never. 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.
dtech 6y ago
Use whatever makes for clearer code, unless you are certain it's the bottleneck.
bluGill 6y ago
That depends. If you are writing the code yourself then the maintenance costs of everyone else after you trying to understand it makes it wrong. However most programming languages have generic programing features such that you can just use an algorithm and so you aren't writing either the algorithm. In that case the code for the fast hash is equal to the O(n^2) code and so of course you select the faster one as a application of don't prematurely pessimise your code rule. If your programing language doesn't already have built in generic algorihtms for your data, then you are using the wrong language (unless your job is to write the generic algorithms for the language in which case this doesn't apply because you can assume your algorithm will be used in a performance critical part at some time)
cma 6y ago
What about when n is small but you do it m times and m is large.
zelly 6y ago
Refer to the rule about measuring first. It's a pessimisation because N may not even be large enough to overcome the slowdown from a hash table's cache misses. You can always profile and fix it later.
- account42 6y ago
  You can never profile with all data your users are going to feed the program.

deleted 6y ago

[deleted]

fabian2k 6y ago

I would not read these rules as anything like suggesting to write O(n^2) code. I think at best I'd read them as favoring O(n) instead of (1) for small n, but I really think that "fancy" algorithms in this case doesn't mean obvious optimizations like this. If you can't guarantee n is small, I think it is entirely sensible to use a dictionary/hash table instead of looping over an array or list. As long as n is small the overhead is probably irrelevant, and it'll prevent surprises if n gets large as you said. And if the difference actually matters, you get back to rule 1 and 2 and measure first anyway.

mav3rick 6y ago

Using array based data structures also get you more cache hits. For smaller data sets, this may well be faster than a fancy algorithm.

bluGill 6y ago
This is true only if you are iterating over the entire array often. If you only rarely need to access one data member the array will not be in cache and so you have less to load from memory. Depending on how your data is structured the array may or may not save time even in small sizes.
- mav3rick 6y ago
  Of course temporal and spatial locality are important.
- cma 6y ago
  Prefetching still may make it way faster.

coliveira 6y ago

It depends. If you don't need to worry about performance, then it will work. But in some performance-dependent situations, the brute force algorithm will win over the hash table, and the only way to know is measuring which one is better.

fasterpython 6y ago

If it's fairly easy, then I think it still fits the spirit of the rules. KISS and all. On the other hand, the idea that one might be setting traps is slightly weird... if you _know_ 90% that n will be large then pick an algorithm that's efficient (and since it's easy to implement, it's a win-win). If n is always going to be small, then does the choice really matter?

naet 6y ago
If N is known small you should favor simplicity and readability over complex optimization.

dimitrios1 6y ago

Yes. If you don't measure, you will never know when the time complexity moves in your favor due to the constant, and other factors. For example, quicksort moves to a O(n^2) algorithm (insertion sort) for the last few iterations of a branch of work(typically n=1000) because this reduces the total sort time.

dragontamer 6y ago

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

zabzonk 6y ago
Also, creating a hash isn't free. And often ordering is required.
- dragontamer 6y ago
  > Also, creating a hash isn't free. Hmmm... I argue that the hash is nearly free actually. An unordered_map traversal is probably DDR4 latency bound. That's ~50-nanoseconds (200 clock ticks) per access. What's the CPU going to do in that time? Well, spending 10 to 20 clock ticks on a typical hash algorithm is fine. Then it will wait the other 180 clock ticks for RAM. If you got hyperthreading, maybe the CPU will go to another thread and do meaningful work while waiting for RAM... but... I think you get the gist. Even IF the hash were free, the CPU is waiting for RAM anyway. So you got plenty of time to make that hash worthwhile. Even an integer division/modulo operator (worst case ~80 clock ticks) can fit in there while waiting for RAM, with plenty of room to spare. I guess if everything was in L1 cache, the story is a bit different. A lot of "depends", depends on the data, the access frequency, etc. etc.
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 ago

mywittyname 6y ago

Keep in mind that a lot of this was written during an era where even modestly complex data structures/algorithms had to be rolled by hand. 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.

yashap 6y ago

I think, in most cases, if you have n items in memory, and you want to find m of them by id, or some such thing, your default should be to represent the n items as a hashmap, not a list, and look them up from the hashmap. There will be cases where this isn’t the right choice, but it’s a good default. And it’s almost always virtually no extra complexity to represent them this way, i.e. often something as simple as: myMap = myList.groupBy(_.id) 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.

BurningFrog 6y ago

Yeah, I do well writing dumb inefficient code as default, and optimizing it when needed, which is almost never. 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.

dtech 6y ago

Use whatever makes for clearer code, unless you are certain it's the bottleneck.

bluGill 6y ago

That depends. If you are writing the code yourself then the maintenance costs of everyone else after you trying to understand it makes it wrong. However most programming languages have generic programing features such that you can just use an algorithm and so you aren't writing either the algorithm. In that case the code for the fast hash is equal to the O(n^2) code and so of course you select the faster one as a application of don't prematurely pessimise your code rule. If your programing language doesn't already have built in generic algorihtms for your data, then you are using the wrong language (unless your job is to write the generic algorithms for the language in which case this doesn't apply because you can assume your algorithm will be used in a performance critical part at some time)

cma 6y ago

What about when n is small but you do it m times and m is large.

zelly 6y ago

Refer to the rule about measuring first. It's a pessimisation because N may not even be large enough to overcome the slowdown from a hash table's cache misses. You can always profile and fix it later.

account42 6y ago
You can never profile with all data your users are going to feed the program.