5 ms·
Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot
- mseebach 17y agoThat is an incredibly long essay to describe a very simple problem. Don't randomize an array the way Microsoft does on browserchoice, because it's not random.
- cschneid 17y agoMore subtly, don't ignore preconditions of methods. The custom sort method needs to implement several invariants, which the Math.random() approach ignores. This confuses the hell out of the sort algorithm (in turn, leading to non-random order)
- marze 17y agoIt doesn't seem unreasonable there might be a bias to the 5th position, it would be the position you just finished paying attention to before clicking if your scan from left to right.
- awa 17y agoIts strange that MS got this wrong as the shuffling questions is quite common in the Microsoft interview (as in many other). Though I do wonder if it makes any difference, may be they are taking this as an opportunity to do some research testing, my personal opinion would be that the browser in the middle position might have a slight upper hand than others.
- Fixnum 17y agoPerhaps this is Microsoft, or someone who works there, thumbing their nose(s) at the EU - after all, what monopolistic corporation wouldn't be bitter at not having been able to buy out such an influential quasi-government organization [edit: and, worse, be forced to advertise on behalf of one's competitors]? Don't get me wrong: I'm no fan of MS or IE. But I can see why they might deliberately fail to implement this correctly. [edit: ...]
- awa 17y agoAgain, I see no benefit to MS or harm to EU for using the broken algorithm... It sounds childish that the broken algo is a win against EU of some sort
- illumin8 17y agoI don't think it's intentional, unless Microsoft intended to give Google Chrome prime placement (more likely to be in the first 3). More likely this is just sloppy coding that wasn't QA'd properly.
- memoryfault 17y agoI doubt they put a dev on something like this...probably a 3rd party vendor or intern.
- deleted 17y ago[deleted]
- glymor 17y agoTurning compare into a coin flip is a fun way to illuminate the underlying algorithm. IE is said to use a heap/tree related sort[1]. The first thing a heapsort does is swap the last entry with the the front (where the front may have been swapped in the heapify step[2]). Thereafter it leaves the last entry alone. Since the first entry in the unshuffled array is "Internet Explorer" if it survives the initial comparison it will always occupy the last (5th) place. The other algorithms don't have a case with only one compare which is why they have more complicated distributions. [1] - http://www.smallapple.net/rnd/art/how_does_your_browser_sort.html http://www.smallapple.net/rnd/art/how_does_your_browser_sort... [2] - http://en.wikipedia.org/wiki/Heapsort http://en.wikipedia.org/wiki/Heapsort
- memoryfault 17y agoIs this even what is shipping with Win7 EU? I would assume that the real browser choice screen is not in a browser window, and that this website was created quickly just to give people an idea of what it might look like. Do we even know who actually wrote the code?
- jasonlotito 17y agoConsidering IE mostly shows up in the 5th position according to this article, who cares? Does it really matter? Mountain out of a mole hill.
- pohl 17y agoDoesn't that depend on which positions are likely to be chosen by people? On what basis should we assume the 5th position is not favored?
- jasonlotito 17y agoYeah, I figured someone would bring that up. First, I could ask the reverse question asking why you assume the 5th position is favored. Next, the requirements didn't dictate a study on the positions. Finally, it avoids the real question: Does it really matter? The placement is random (you can't predict the order reliably before you launch the page), and the options are present. Does it really matter? No, even with understanding your point, and even thinking that it's an interesting thought that I'm sure we'll see answered.
- pohl 17y agoFirst, I could ask the reverse question asking why you assume the 5th position is favored. Does questioning someone's assumption necessarily imply that one is making the converse assumption? Does it really matter? I think that's an open question. Note that your definition of randomness is a bit off. The linked article shows that one can predict the occupant of the 5th position greater than 1/5th of the time.
- snprbob86 17y agosigh That's really quite embarrassing. You can see the source code here: http://www.browserchoice.eu/resources/scripts/page.js http://www.browserchoice.eu/resources/scripts/page.js The bug is at the very bottom of the file.
- andrewcooke 17y agothis was explained in the techcrunch comments at the time, wasn't it? also here - http://news.ycombinator.com/item?id=1145073 http://news.ycombinator.com/item?id=1145073
- kevinh 17y agoSo in essence, Microsoft just handed this off to one of their junior programmers and he wasn't aware of how to do random correctly. I don't see this being a result of Microsoft's malevolence, merely a programmer's ignorance. I doubt that Microsoft would do something that would be caught while fighting anti-trust charges.
- CoreDumpling 17y agoIt might be an "oops" from a single programmer, but I thought a high-profile site like this would at least go through some basic code review. The bug isn't that subtle, either.
- eli 17y agoFor the ui JavaScript? Certainly none of the places I've worked subject that to real code review.
- mbrubeck 17y agoI love the (distressingly common) attitude that the only code exempt from review is the layer that interacts with the user, which can completely obscure or invalidate the correct functioning of all the other layers.
- icefox 17y agoWhy doesn't your javascript code go through code review?
- eli 17y agoI'm not debating that it should (certainly if it's javascript that I'm writing), I've just literally never seen that happen.
- nomoresecrets 17y agoThe worst part about the implementation is that the browser icons often appear unsorted initially, and then the sort kicks in 0-5 seconds later, and they all shuffle. This has caught me out at least twice by clicking on a browser icon to choose it, then the order changes after I clicked and the wrong browser installer is launched.