3 ms·
The more you "know" the less you have to go look for, and when you do have to go look for stuff on the Internet (since you're not omniscient) then you'll unders
by alexkus 14y ago
The more you "know" the less you have to go look for, and when you do have to go look for stuff on the Internet (since you're not omniscient) then you'll understand more of the pages you get back as results, and understand them faster since there's less groundwork you need to cover.
An understanding big-O notation is very important if you go searching for sorting algorithms and land on a page that has an overview of sorting functions but listing bogosort as O(n!) and insertion sort as O(n^2), both relatively easy to implement, and this relatively complicated iterative[1] quick sort that's listed as O(n log n). Without other clues someone might just implement the one that looks easiest, and it works fine on their test set of 20 elements, but blows up in the future as their application/site grows and slows to a crawl sorting through millions of rows with an insertion sort.
Or, one of the most recent questions in the Mathematics part of the exam made me snigger because someone I work with was asking what bignum library was easiest to use. Rather than just answering their question (I prefer GMP myself) I asked why; they wanted to do the equivalent of log( x^300 ) and so they needed to compute x^300 first and then take the log of it; floating-point was giving slightly inaccurate answers to what was expected when they took the log of the intermediate result. It was even worse when they tried to do log( x^9125 ) - or whatever exponent is used for daily interest on a 25 year mortgage to account for leap days.
To put it another way. Without the knowledge you end up googling, and implementing, the wrong thing. You may get the right answer/outcome in the end but it may be horribly inefficient. Or, worse, an inaccurate answer/outcome; and you may not even know.
Hammering the insertion sort analogy home; you can profile and optimise an insertion sort all you like, it's still never going to approach the speed of quicksort on mid-large datasets. Huge datasets are another matter, someone stuck with "quicksort is the best" is going to struggle when faced with hundreds of millions of rows and there are things less pessimal than quicksort.
Knowledge of processor architectures, caching and how hash tables are implemented means you know not to use a hash when a simple array will suffice; but I've seen this done plenty of times.
Etc, etc, etc.
Out of the 15 questions so far there's only been two or three that the knowledge of wouldn't have helped me at some point in my development over the last 15 years. Of those that haven't applied to me I can see why they would be important to other fields and other people.
It's one of the major reasons I decided to do a full Maths degree (part-time via correspondence) to complement the Comp Sci degree I got ~15 years ago. It's not just the obvious useful stuff like calculus, group and set theory, graphs and networks, etc. Whilst I thought that the mechanics part of the Maths degree wouldn't be very useful in my job I was surprised at how useful and ubiquitous [non-]homogenous second-order linear differential equations are in modeling things that are relevant to my job (populations -> user base, hysteresis, etc).
No doubt others find huge amounts of other knowledge in other subjects that is directly applicable to IT; psychology, education, design to name but a few.
The right choice of algorithm, and implementation, in a critical part of your code could mean the difference between having 64GB of memory per server or getting by with 16GB. It could mean 100 servers to manage your 1M users, or 10 servers; the difference between 100 servers and 10 servers to manage your 1M users could mean the difference between making a profit and making a loss. These could be the differences between your idea succeeding or disappearing.
1. Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getting blown on large datasets. I like it when people encounter this problem and find out that stacks are finitely sized and not as big as they'd hoped they would be. "But that means..." is a great thing to hear.
- irahul 14y ago> Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getting blown on large datasets. What language do you use which doesn't already have an optimized version of quicksort or equivalent?
- alexkus 14y agoThe usual suspects are recursive qsort() implementations inside libc on Solaris, HP-UX and AIX. They've got a lot better in the latest releases but our software is supported on the older platforms (as far back as Solaris 7 for example) so it has to be made to work on them. glibc has done it properly for years. So this is mainly software written in C/C++. Other languages do sorting in one of several ways:- 1) Just wrapper libc's qsort() and so suffer the same problem if that's susceptible. 2) Implement the naive recursive stack-gobbling quicksort in their own language as a module/package/import/library. 3) Implement their own sorting algorithm that avoids lots of recursive calls or does the tricks to pick suitable pivots, etc. It's #1 and #2 that tend to suffer from problems when sorting large datasets, or the pathalogical cases that pinpoint the absolute worst in the design of the algorithm.
- irahul 14y ago> The usual suspects are recursive qsort() implementations inside libc on Solaris, HP-UX and AIX. Oh, I am mainly familiar with GNU C library. Wasn't aware others were shipping recursive qsort implementation, especially considering that a non recursive qsort is an undergrad level exercise.
- nadam 14y agoI am not an expert of this, but: 1. I think the stack usage of Quicksort is O(log(n)). Which means it is impossible to blow up the stack unless your dataset is bigger than the number of atoms in the universe (but in that case how are you keeping it in memory?) 2. For example in Java when you call Arrays.sort() this is called: http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/classes/java/util/DualPivotQuicksort.java.html http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/c... (It apparently uses recursion) I know quicksort, but not on this level: these guys researched lots of different quicksort implementations and optmized the hell out of it. This implmenetation is way longer to begin with than my naive quicksort implementation would be and is called 'dual pivot quicksort', which I did not hear about until now, despite I know how the traditional quicksort works.