Re:Ask HN: When was the last time you used big-o in a web app?
by ww520 on Tuesday August 02, 2011 @01:45PM
(#2837993)
The first problem sounds like the join operation in RDBMS. It might be useful to look into the various join algorithms as there're extensive research in that area.
Re:Ask HN: When was the last time you used big-o in a web app?
by ColinWright on Tuesday August 02, 2011 @01:56PM
(#2838051)
You're right, it sounds like that. But it wasn't. I can't go into more detail, but I and my colleagues have some experience in identifying things that are best simply handed off to a "proper" database. This wasn't one of them.
Re:Ask HN: When was the last time you used big-o in a web app?
by methodin on Tuesday August 02, 2011 @11:19AM
(#2837411)
Interesting. So your use of big-o was primarily for an algorithm that ran on data after it was stored and/or used in real-time when fetching data? I tend to agree. Either I tend to do very simple input/output pages or very complex modeling with relationships between data. I would imagine the latter leads to more compelling products.
I can't tell you what they are, because they are all projects that might soon be opened, and while they're not exactly in stealth mode, they are good ideas that I can only work on slowly. I need to get enough of an advantage to be able to stay ahead of those with more web implementation experience.
However, one involves analysing the cross-connections between hundreds of users, and hundreds of small units of data they each have. The naive algorithm is O(n^3 m^2) and is too slow for more than 30 users or 100 units of data. The analysis showed that early, so the architecture of the system was changed to cause the data to "flow" around the system and agregate closer to where it was needed.
Another application uses proximity detection on potentially thousands of points. Again, the naive algorithm worked for small numbers of users (I use the term loosely - they're more "agents" than users), and again, big-O analysis showed the critical points in the system.
I'm sure that most web development consists of gluing libraries together, stuffing databases, and populating forms or similar. Interesting stuff that I do uses algorithmic analyses.