4 ms·

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(

by 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

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