Re:Ask HN: When was the last time you used big-o in a web app?
by mindcrime on Tuesday August 02, 2011 @11:55AM
(#2837570)
Go into detail about the last time you've found it necessary to analyze a particular algorithm for either speed or memory using the typical tools taught by CS programs in your web application.
I agree with the folks who mentioned doing a sort of naive, intuitive "big O" analysis as you work, as opposed to a formal analysis. I was recently working on some social graph stuff, and I started down the path of doing an "all pairs shortest paths" determination with Floyd-Warshall (which is O(|V|^3) complexity).. needless to say, it only took a few minutes to realize that this won't work for any real world size datasets and would require a different approach. If nothing else, you quickly find that the naive approach doesn't work for any meaningful amount of data, as just building an adjacency matrix for a few hundred entries, if the datatype is an int (which is what I was using at the time) will blow past the heap size limit on a 32bit JVM.
I'm actually still researching and considering exactly what I'm going to do. I don't necessarily need every shortest path in the system, so the first cut at optimizing this will probably be to cook up something that only calculates a portion of the paths. Another approach might be to look into a parallelized algorithm that can do this on a cluster. Beyond that, I've been poking around trying to see if there's a way to apply a sort of incremental evaluation approach to the problem, where I build the initial matrix of path distances, and then incrementally recompute just the part I care about, when something changes.
Anyway, at the moment, this is the largest extent to which I've actually had to spend some time thinking about the kind of stuff that I studied in some of my CS classes... I've actually got all my algorithms books of the shelf, and digging in, as I research this. :-)
I agree with the folks who mentioned doing a sort of naive, intuitive "big O" analysis as you work, as opposed to a formal analysis. I was recently working on some social graph stuff, and I started down the path of doing an "all pairs shortest paths" determination with Floyd-Warshall (which is O(|V|^3) complexity).. needless to say, it only took a few minutes to realize that this won't work for any real world size datasets and would require a different approach. If nothing else, you quickly find that the naive approach doesn't work for any meaningful amount of data, as just building an adjacency matrix for a few hundred entries, if the datatype is an int (which is what I was using at the time) will blow past the heap size limit on a 32bit JVM.
I'm actually still researching and considering exactly what I'm going to do. I don't necessarily need every shortest path in the system, so the first cut at optimizing this will probably be to cook up something that only calculates a portion of the paths. Another approach might be to look into a parallelized algorithm that can do this on a cluster. Beyond that, I've been poking around trying to see if there's a way to apply a sort of incremental evaluation approach to the problem, where I build the initial matrix of path distances, and then incrementally recompute just the part I care about, when something changes.
Anyway, at the moment, this is the largest extent to which I've actually had to spend some time thinking about the kind of stuff that I studied in some of my CS classes... I've actually got all my algorithms books of the shelf, and digging in, as I research this. :-)