gobeirne Posted April 19, 2006 Report Share Posted April 19, 2006 Hello all, I was wondering if anyone knows the most efficient method of randomising a 1-D array? I've attached the solution that I came up with, but there has to be a better way, surely! Download File:post-3796-1145484802.vi Many thanks, Dr Greg O'Beirne Christchurch, NZ Quote Link to comment
Yair Posted April 20, 2006 Report Share Posted April 20, 2006 Efficient how? Memory? Speed? I don't think there is any way to do this without using 2 array buffers (one for the input and one for the output), which is what you're doing. I think LV might be clever enough in its newer versions to detect that you're not actually doing anything with the top array and will probably reuse its buffer. Other than this method (which should only be a problem when handling large arrays), the only viable method I can think of would be passing the array to a DLL with an efficient C algorithm, but I'm not sure the overhead will justify it. Quote Link to comment
Kurt Friday Posted April 20, 2006 Report Share Posted April 20, 2006 Hi Greg Perhaps a better way may be to shuffle your array. Download File:post-1058-1145521987.vi Quote Link to comment
Kurt Friday Posted April 20, 2006 Report Share Posted April 20, 2006 An even more efficient method of the shuffle, just randomly select two elements and swap their locations. Download File:post-1058-1145537823.vi Quote Link to comment
Yair Posted April 20, 2006 Report Share Posted April 20, 2006 An even more efficient method of the shuffle, just randomly select two elements and swap their locations. Nice. I actually figured out the shuffle way as well, but the main problem with both methods is that they're only "quasi random" (they have an inherent order) and a cryptographer friend of mine told me once that these kinds of methods are not considered good enough for cryptography. For other purposes, however, they should be good enough (especially if memory allocation is in mind) and I will try to remember the second one. Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 ...the main problem with both methods is that they're only "quasi random"... <Physicist Hat> All "random" patterns are quasi-random: there's no such thing as completely random, only degrees of quasi-random... </Physicist Hat> Quote Link to comment
Guenther Posted April 20, 2006 Report Share Posted April 20, 2006 Here is another one: Bundle your array elements with a random number as first element, sort the resulting cluster array, and then throw away the random number. Quote Link to comment
Yair Posted April 20, 2006 Report Share Posted April 20, 2006 <Physicist Hat>All "random" patterns are quasi-random: there's no such thing as completely random, only degrees of quasi-random... </Physicist Hat> I know, only in this case, using the third method in 7.0 with an array of 10,000 elements leaves 1300-1400 of the elements in their original locations, which is a rather large margin of error (13 percent). Since this method is based on the random number generator and the number is around this range every time I run the VI it seems reasonable to assume that this is a property of the random number generation which is reflected through using this method. The method suggested by Guenther is fast, random and elegant and appears to be the best solution. Download File:post-1431-1145547234.vi Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 I know, only in this case, using the third method in 7.0 with an array of 10,000 elements leaves 1300-1400 of the elements in their original locations, which is a rather large margin of error (13 percent). That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc... I wouldn't call this a "margin of error" - just because a number remains in its' original location doesn't mean that it's an error at all. It's more of a ratio of the quasi-random nature of the process relative to a true random process, which by its' very nature doesn't exist, and you can't test for it anyway That said, I like the "cluster random" method of assigning a quasi-random number with each of those in your sample set - at least this means that the position of your samples has less (sort of) effect on where they'll end up - I think this is probably as good as you'll get. Quote Link to comment
jpdrolet Posted April 20, 2006 Report Share Posted April 20, 2006 That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc... I wouldn't call this a "margin of error" - just because a number remains in its' original location doesn't mean that it's an error at all. It's more of a ratio of the quasi-random nature of the process relative to a true random process, which by its' very nature doesn't exist, and you can't test for it anyway That said, I like the "cluster random" method of assigning a quasi-random number with each of those in your sample set - at least this means that the position of your samples has less (sort of) effect on where they'll end up - I think this is probably as good as you'll get. Well if I measure the Cosmic Background Radiation and shuflle that with the particle count/s of a radioactive substance and XOR with alfa's posts, I'll get data with no discernable pattern for sure... :laugh: Quote Link to comment
Yair Posted April 20, 2006 Report Share Posted April 20, 2006 That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc... Yes, but why is it always around 13.5% which aren't moved? I assume this is because of some property of the random number generator which I don't feel like testing at the moment.I wouldn't call this a "margin of error" Neither would I. Oh... I already did... However, since time is bidirectional (or is it quasi-directional? ), let's pretend I didn't do that yet. Quote Link to comment
Guillaume Lessard Posted April 20, 2006 Report Share Posted April 20, 2006 An even more efficient method of the shuffle, just randomly select two elements and swap their locations. If you randomly select only one of the two elements, everything will be fine. 1. Select first element with the loop counter 2. Select second element randomly 3. Swap them. Works with no extra buffer allocation! Download File:post-3022-1145556103.vi I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it... Guillaume Lessard P.S. this tends to be the algorithm you find upon googling "array shuffle"... Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 I'll get data with no discernable pattern for sure... Depends on you definition of "descernable" However, since time is bidirectional (or is it quasi-directional? ), let's pretend I didn't do that yet. Didn't do what? I didn't see anything Quote Link to comment
Chris Davis Posted April 20, 2006 Report Share Posted April 20, 2006 Depends on you definition of "descernable" Didn't do what? I didn't see anything Since this post mentions alfa, shouldn't we begin discussing beer? :thumbup: Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it... :thumbup: Very nice! Yep - this is an excellent solution, statistically equivalent to the pervious solution, faster and more memory efficient too! crelf says "Five :star:s - A must see!" ...shouldn't we begin discussing beer? :thumbup: Well done - you've invoked Kring's Law - you win! Quote Link to comment
Guillaume Lessard Posted April 20, 2006 Report Share Posted April 20, 2006 :thumbup: Very nice! Yep - this is an excellent solution, statistically equivalent to the pervious solution, faster and more memory efficient too! I couldn't help wondering if the two really are statistically equivalent. They happen to be the two shuffling algorithms popularized by Knuth. See this. I'm perfectly willing to take Knuth's word on algorithm correctness! Guillaume Lessard Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 I'm perfectly willing to take Knuth's word on algorithm correctness! Indeed! There's some theory that may be of interest here. Quote Link to comment
jpdrolet Posted April 20, 2006 Report Share Posted April 20, 2006 If you randomly select only one of the two elements, everything will be fine.1. Select first element with the loop counter 2. Select second element randomly 3. Swap them. Works with no extra buffer allocation! Download File:post-3022-1145556103.vi I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it... Guillaume Lessard P.S. this tends to be the algorithm you find upon googling "array shuffle"... I think that this shuffling is biased. There is a random number generation between 0 and N-1 but because of rounding the elements 0 and N-1 have half the probability to be picked than other numbers. It should be a random number between 0 and N then floored to integer. The index N won't be picked because the random number function is always lower than 1.0 Edit: it is based on the picture posted, I can't see Guillaume Leassard's VI since it is in 8.0 Quote Link to comment
Phillip Brooks Posted April 20, 2006 Report Share Posted April 20, 2006 While looking up an old friend, I came across this link. I'm not sure if it is the same Les Peters, but he did work with LabVIEW and RF communcations. One of the problems I have been faced with in developing a CM automated test solution has been the creation of an encryption quality random number. This random number is used as a seed for generating a secure ID string which is then programmed into each modem. A colleague of mine having found your web site http://www.aw-el.com, suggested I look into your Radiation Monitors as one of its features was the generation of random numbers. After reading all the information on your website and talking with you about my specific application I purchased one of your model #RM-60 Radiation Monitors. I must say at first my colleagues and I were a little skeptical having little experience with Radiation Monitors. But after some investigation we realized that the decay of radioactive matter being unpredictable actually provided a very good means to generate an extremely random number. Your original "AW-RAND.EXE" software supplied with the monitor while displaying the data on my PCs monitor did not allow us to port the data to a text file. After having discussed this problem with you, you quickly made a change to your source code sending the generated data to a text file. You then E-mailed the new code to me within several hours, now that's service ! While this solved one issue generation of random numbers was slow using background radiation. Your suggestion of using the AM241 element out of an inexpensive ionization type of smoke alarm solved that problem, now numbers are generated very quickly. My test software is written in a graphical programming language called LABVIEW and integrating your "AW-RAND.EXE" required the creation of a driver. This driver allows execution of your "AW-RAND.EXE" code using the supported arguments on the same command line. The driver was designed using the LABVIEW 5.0 Full development for WINDOWS 95/NT. I have attached a copy of this driver so that some of your other customers can use it. I feel it is the least I can do with all the help that you have given me. http://www.aw-el.com/random.htm Quote Link to comment
Guillaume Lessard Posted April 20, 2006 Report Share Posted April 20, 2006 I think that this shuffling is biased. There is a random number generation between 0 and N-1 but because of rounding the elements 0 and N-1 have half the probability to be picked than other numbers. It should be a random number between 0 and N then floored to integer. The index N won't be picked because the random number function is always lower than 1.0Edit: it is based on the picture posted, I can't see Guillaume Leassard's VI since it is in 8.0 Sorry about the lack of picture. I didn't really try to post a screen shot at first. GL Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is... Quote Link to comment
jpdrolet Posted April 20, 2006 Report Share Posted April 20, 2006 Sorry about the lack of picture. I didn't really try to post a screen shot at first. GL Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is... Look at this NI Forum thread. There is a tool to save a picture of the diagram and copy its path to the clipboard, ready to paste in the File Attachment field. Check also for the hack needed to make it work in LV8. :thumbup: In the VI you could expand Replace Array Subset to two inputs instead of using two nodes. Quote Link to comment
gobeirne Posted April 20, 2006 Author Report Share Posted April 20, 2006 Thanks very much to everyone who has replied in this thread! The proposed solutions (particularly Guillaume's) are superb and particularly elegant - cheers!! Greg. Quote Link to comment
Guillaume Lessard Posted April 20, 2006 Report Share Posted April 20, 2006 Look at this NI Forum thread. There is a tool to save a picture of the diagram and copy its path to the clipboard, ready to paste in the File Attachment field. Check also for the hack needed to make it work in LV8. :thumbup: Thanks JP!! Now, at the risk of beating a nearly-dead horse to a shapeless pulp, I realized that the diagram I posted earlier does, in fact, produce a biased result. Upon carefully reading Knuth's shuffling algorithm, I realized that the correct diagram is: Thou shall shuffle each cell only once. Now we can all go have :beer:, because the code is both correct and efficient. GL Quote Link to comment
crelf Posted April 20, 2006 Report Share Posted April 20, 2006 Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is... Windows: click on the window that you want an image of and press Alt+PrintScrn - this'll put a screen shot of the selected window on to your clipboard and then you can paste it into your favorite image editing / saving tool. Quote Link to comment
gobeirne Posted April 20, 2006 Author Report Share Posted April 20, 2006 Now we can all go have :beer:, because the code is both correct and efficient.GL Cheers Guillaume! G. Quote Link to comment
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.