5 ms·

If you don't use math, it's almost certain that you're writing inefficient code. There's no way to estimate big-O complexity of the procedures you're writing wi

by Grue3 9y ago

If you don't use math, it's almost certain that you're writing inefficient code. There's no way to estimate big-O complexity of the procedures you're writing without at least some math. Unfortunately these days it's considered ok to write chat applications that consume several gigabytes of RAM, so maybe nobody cares about efficient code anymore.

candiodari 9y ago
I see tons of people online writing algorithms in python and ruby, that will run against a few megabytes of data, and worry about getting the "big-O" of their algorithms right. Then I go ahead and show them that just by doing the same thing in C++ you get a 10x speedup if you know what you're doing, sometimes more. And then they say "but I'd never get an optimal algorithm done" (that C++ is typed actually makes this easier for me then python as soon as we get past the "trivial" complexity level, but to each his own I guess). So I say "Ok. No worries ! Let's make it inefficient !". And add an inner for loop where a hash lookup would have done it (for example). And lo and behold ! The C++ code still beats the crap out of their "optimal" python code. (this is somewhat of a cheat because the odds of making a random thing somewhat inefficient is very unlikely to be the critical point of that code, even if it's in the middle of the deepest loop). Then we replace their 100mb csv with a new 10mb memory-mappable data and they can't even measure anymore how fast the program is. As soon as we enter main, it just immediately terminates. Algorithms start to matter when your data, optimally stored, becomes >10x all the CPU cache combined, ignoring things like strings. That means 300-400 megabytes when stored fully binary. Ie. you DO NOT HAVE ANY SUCH DATA. Your company's yearly transaction log is less than this. Before that, forget about algorithm optimization, it will bring you nothing. TLDR: If you're not working in C++, and actually doing most of your development on data layout in memory and on disk, you don't care about performance. Math does not matter at all. Once a year I encounter a situation where math matters, and frankly I just usually find a PhD in that specific field and ask them (despite having a master degree in Math myself). You do not need math to program. The big secret is that for programming, there is only one thing that matters beyond basic programming skill. And that thing is domain knowledge of the problem. Exactly, I might add, what almost all programmers don't have.
- Grue3 9y ago
  No, algorithms always matter. Especially in web-development. Yes, Javascript is slow. But there's no need to make it even slower by writing O(n^2) code where O(n) suffices. You don't even need to reach large n's to feel the lag. I personally had to rewrite such code, which was causing horribly slow website performance. The big-O thing is not about C vs Python. A slow C program will lose to a Python program with a properly written algorithm any day of the week. Just because of how the math works out. The speedup of using C is linear (in practice, worse than linear). Suppose the O(n^2) C program executes each instruction 1000 times faster that the corresponding O(n) Python program. Then you only need n to start reaching thousands to blow the C program out of the water. Meanwhile, O(n^2) Python program would be a thousand times slower than that. And to me, that's unacceptable.
  - candiodari 9y ago
    Web development is about displaying ONE PAGE of data. 20 items. 40 items. 100 items. No more. A far cry from the thousands of items you say it requires (I'd argue that it's a lot more). And just so we're clear a supposed O(n^5) algorithm with n constant (like on paginated web pages), is really O(1). The thing about O(n) algorithms versus O(n^2) algorithms is that very often rewriting an O(n^2) algorithm into an O(n) algorithm involves splitting the loops, and using way more memory. And that's assuming you do it correctly. Mostly people don't. Example, your basic optimization of a double for loop turns into: # (1) x = {} for e in lst: x[e.field] = e for e in lst: e2 = x[e.value] # do something with it Is that x[e.field] is an allocation and takes O(n) time. So this is an O(n^2) loop, and you have saved nothing over this, even in theory # (2) for e in lst: for e2 in lst: if e2.field == e.value: # inner loop So in this obvious case it takes infinite items in theory. Even that is a wrong prediction. (2) will also behave very differently depending on whether the VM is just starting up or has been running for a while. So in practice here's what's going to be faster: n < 10000 or so: (2) (the actual number depends on the CPU, but it'll easily be 500 even on the most pathetic atom or even mobile processor) n > 10000 and total size < system memory / 2.5 or so: (1) Why, in the beginning not doing the setup is just faster by itself. This lasts a long time because when the inner loop executes in cache and the hashtable copy does not fit in cache the loop is 100 times faster (on top of that ~100 times C acceleration). This means the loop stays fast for a long time. Needless to say, this means that for anything you should do client-side the double loop will be the faster option, even on the slowest mobile cpu any of your customers might use. At some point the Hash table will start winning. Until it causes virtual memory activity during the lookups. At which point, it's memory usage makes it useless. I'll see about actually running this test with an actual example program. Hence, it's good to keep Rob Pike's rules of programming into account: http://users.ece.utexas.edu/~adnan/pike.html http://users.ece.utexas.edu/~adnan/pike.html Rule 2. Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest. Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)

by Grue3 9y ago

candiodari 9y ago

I see tons of people online writing algorithms in python and ruby, that will run against a few megabytes of data, and worry about getting the "big-O" of their algorithms right. Then I go ahead and show them that just by doing the same thing in C++ you get a 10x speedup if you know what you're doing, sometimes more. And then they say "but I'd never get an optimal algorithm done" (that C++ is typed actually makes this easier for me then python as soon as we get past the "trivial" complexity level, but to each his own I guess). So I say "Ok. No worries ! Let's make it inefficient !". And add an inner for loop where a hash lookup would have done it (for example). And lo and behold ! The C++ code still beats the crap out of their "optimal" python code. (this is somewhat of a cheat because the odds of making a random thing somewhat inefficient is very unlikely to be the critical point of that code, even if it's in the middle of the deepest loop). Then we replace their 100mb csv with a new 10mb memory-mappable data and they can't even measure anymore how fast the program is. As soon as we enter main, it just immediately terminates. Algorithms start to matter when your data, optimally stored, becomes >10x all the CPU cache combined, ignoring things like strings. That means 300-400 megabytes when stored fully binary. Ie. you DO NOT HAVE ANY SUCH DATA. Your company's yearly transaction log is less than this. Before that, forget about algorithm optimization, it will bring you nothing. TLDR: If you're not working in C++, and actually doing most of your development on data layout in memory and on disk, you don't care about performance. Math does not matter at all. Once a year I encounter a situation where math matters, and frankly I just usually find a PhD in that specific field and ask them (despite having a master degree in Math myself). You do not need math to program. The big secret is that for programming, there is only one thing that matters beyond basic programming skill. And that thing is domain knowledge of the problem. Exactly, I might add, what almost all programmers don't have.

Grue3 9y ago
No, algorithms always matter. Especially in web-development. Yes, Javascript is slow. But there's no need to make it even slower by writing O(n^2) code where O(n) suffices. You don't even need to reach large n's to feel the lag. I personally had to rewrite such code, which was causing horribly slow website performance. The big-O thing is not about C vs Python. A slow C program will lose to a Python program with a properly written algorithm any day of the week. Just because of how the math works out. The speedup of using C is linear (in practice, worse than linear). Suppose the O(n^2) C program executes each instruction 1000 times faster that the corresponding O(n) Python program. Then you only need n to start reaching thousands to blow the C program out of the water. Meanwhile, O(n^2) Python program would be a thousand times slower than that. And to me, that's unacceptable.
- candiodari 9y ago
  Web development is about displaying ONE PAGE of data. 20 items. 40 items. 100 items. No more. A far cry from the thousands of items you say it requires (I'd argue that it's a lot more). And just so we're clear a supposed O(n^5) algorithm with n constant (like on paginated web pages), is really O(1). The thing about O(n) algorithms versus O(n^2) algorithms is that very often rewriting an O(n^2) algorithm into an O(n) algorithm involves splitting the loops, and using way more memory. And that's assuming you do it correctly. Mostly people don't. Example, your basic optimization of a double for loop turns into: # (1) x = {} for e in lst: x[e.field] = e for e in lst: e2 = x[e.value] # do something with it Is that x[e.field] is an allocation and takes O(n) time. So this is an O(n^2) loop, and you have saved nothing over this, even in theory # (2) for e in lst: for e2 in lst: if e2.field == e.value: # inner loop So in this obvious case it takes infinite items in theory. Even that is a wrong prediction. (2) will also behave very differently depending on whether the VM is just starting up or has been running for a while. So in practice here's what's going to be faster: n < 10000 or so: (2) (the actual number depends on the CPU, but it'll easily be 500 even on the most pathetic atom or even mobile processor) n > 10000 and total size < system memory / 2.5 or so: (1) Why, in the beginning not doing the setup is just faster by itself. This lasts a long time because when the inner loop executes in cache and the hashtable copy does not fit in cache the loop is 100 times faster (on top of that ~100 times C acceleration). This means the loop stays fast for a long time. Needless to say, this means that for anything you should do client-side the double loop will be the faster option, even on the slowest mobile cpu any of your customers might use. At some point the Hash table will start winning. Until it causes virtual memory activity during the lookups. At which point, it's memory usage makes it useless. I'll see about actually running this test with an actual example program. Hence, it's good to keep Rob Pike's rules of programming into account: http://users.ece.utexas.edu/~adnan/pike.html http://users.ece.utexas.edu/~adnan/pike.html Rule 2. Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest. Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)