3 ms·
That's a big red flag, at least in a Google setting. The reason is because when your dataset is in the petabytes, any algorithm bigger than O(N log N) is not g
by nostrademons 10y ago
That's a big red flag, at least in a Google setting.
The reason is because when your dataset is in the petabytes, any algorithm bigger than O(N log N) is not going to terminate. You're not going to get any answer at all; your MapReduce is going to sit there burning CPU time for a day, and then you'll kill it, and you won't have any idea what went wrong. (This is learned from experience, if you couldn't tell.)
In a startup context, I'd certainly agree with you - that's exactly the approach I'm taking with my startup, where I'm doing a lot of the debugging and code-wrangling on my local laptop after verifying that the data I want exists and calculating its size with a couple cloud-computing passes. It can sometimes be useful to prototype & iterate with a small subset of the data until you've got the algorithms down.
But many of the algorithms Google cares about don't give any useful results on small data sets. I remember running a few collaborative-filtering algorithms and finding that they gave zero answers because within my small sample of 0.01% of the total data, nobody liked anything else that anybody else did.
- alexbecker 10y agoIn my experience as a Google engineer, this is mostly false. None of the work I or any of the people I know well at Google is on petabyte datasets; most people just aren't on the hot path of indexing/websearch/youtube. In fact almost none of the stuff I was asked about in my interview has been relevant to my work. I have thought about complex algorithms two or three times in the past year.
- ljw1001 10y agoNot only that, but (in my experience as a Google engineer), factors relating to the location of data (distribution and disk vs ram, etc.) often greatly outway algorithmic performance. Constant factors often dominate variable factors.
- lomnakkus 10y agoExactamundo! Cache/memory/disk locality dominates almost all other factors[1] unless you're doing something very special. (Speaking as a non-Google person who also likes to think that he knows what he's talking about.) [1] Well, it's really the amazing amount of throughput that modern architectures can achieve. Latency hasn't improved quite as much given the inescapable limitation of the speed of light.
- nostrademons 10y agoWhat department? I was in Search and used that knowledge all the time, and also did rotations on GWS, Google+, and GFiber. Certainly I used less of that knowledge for GWS (where everything you need is in-process) and for GFiber (where I was working on marketing & customer signup - the job req for this was actually different, and both interviews & job duties were much more like a traditional SWE job in other companies). But even Google+ needed a lot of algorithmic complexity knowledge; G+'s scaling needs are similar to Twitter's, and we know how that went. Perhaps it has changed as well; when I left (2014) they had just started encouraging engineers to focus on one particular task, with the architecture already defined, while when I started (2009) there were still a number of problems of the form "here's a feature we want to add; here's the data we have available; how can we build it?"
- alexbecker 10y agoI'm on Ads and Commerce front-end, and I also know a number of people on Android. These of course are mostly constrained by users' devices, so don't have the scale your talking about. But I also think the trend you're talking about of smaller roles has been continuing and has a lot to do with it as well.
- vvanders 10y agoEveryone loves to put Big-O up on a pedestal, however many times the constant costs can outweigh the rest of the algorithm. Cache access times in particular can be brutal for non-linear access patterns.