PS 2: I think the correct way to write the function that returns a number in the range -1 / 1 is:
Math.floor(Math.random * 3) - 1 In this case, you could indeed use int() instead of a static Math method, so I guess I was wrong about your function needing a Math.round call. 2010/5/9 Juan Pablo Califano <[email protected]> > Steven, sorry to contradict you, but although your code is simple and sort > of works, there a couple of problems with it. > > First, the sorting function is wrong. A sorting function is supposed to > return -1,0 or 1. But it only returns -1 or 0. > > The problem is you are coercing the result to int. You should use > Math.round instead. > > int(Math.random() * 2) will return 1 or 0, never 2, because the biggest > value Math.random will return will be close to 1, but never will be 1. So, > if Math.random returns say, 0.9, after you multiply you get 1.8; since > you're using int(), decimals will just be discarded (instead of rounded) and > the result will be 1. There's no way you'll get 2, only 1 or 0. Then you > substract 1, so your sorting function will return either -1 or 0. > > Second, you don't need to sort the whole list. It's much more work than > it's needed to shuffle the array. While the Fisher-Yates algorithm is > linear, the sort is not. That is, if you have 40 items, you know the > Fisher-Yates will "visit" each list slot only once. That's not the case with > the sort method. It grows exponentially. Well, maybe not exactly > exponential, I'm not possitive, but it's not linear anyway, as this code > shows: > > var list:Array = []; > var numItems:int = 40; > for(var i:int = 0; i < numItems; i++) { > list[i] = i; > } > > var calls:int = 0; > function randomize(a:int, b:int):int > { > calls++; > return int(Math.random() * 2) - 1; > } > > list.sort(randomize); > trace("calls:" + calls); > > Change numItems and you'll see what I mean. Bottom line, you're doing more > work than you need: you're calling a function instead of doing your > comparison inline and you are calling Math.random more than it's actually > needed to sort the list. > > Third, the sorting algorithm works under the assumption that given two > objects they allways sort the same: either the first one is less than, equal > or greater than the second. That doesn't hold true if your sorting function > returns a random result. And I think maybe that's why the number of calls > that the above code prints vary even when you have the same number of items. > > Cheers > Juan Pablo Califano > > PS. I also used the method you describe (for years) until I read about its > problems, so I thought maybe this is a good opportunity to pass this info > on. To be honest, though, I don't think it will be a problem > preformance-wise unless you have a rather big array. > > 2010/5/9 Steven Sacks <[email protected]> > > Here's a very clean, fast and simple way to randomize an array. >> >> array.sort(randomizeFunction); >> >> function randomize(a:int, b:int):int >> { >> return int(Math.random() * 2) - 1; >> } >> >> If you're not happy with Math.random()'s randomness, there are plenty of >> other random number generators out there, such as: >> >> >> http://lab.polygonal.de/2007/04/21/a-good-pseudo-random-number-generator-prng/ >> >> And Grant Skinner's Rndm: >> http://www.gskinner.com/blog/archives/2008/01/source_code_see.html >> >> _______________________________________________ >> Flashcoders mailing list >> [email protected] >> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >> > > _______________________________________________ Flashcoders mailing list [email protected] http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
