[CR] Random permutation

[syrus]

File Name: Random permutation

File Submitter: syrus

File Submitted: 20 Oct 2006

File Updated: 23 Oct 2006

File Category: General

This SubVI takes a positive I32 integer n as input and generates a uniformly random array of the integers from 0 to n-1 as output. It is equivalent in function to the

[Aristos Queue]

This SubVI takes an assumed-to-be-positive I32 integer n as input

....

this SubVI does not perform any input validation or error checking.

Instead of "assumed to be positive I32", why not use an unsigned 32-bit? Then you don't have to worry about someone passing a negative.

[Michael Aivaliotis]

Instead of "assumed to be positive I32", why not use an unsigned 32-bit? Then you don't have to worry about someone passing a negative.

Sounds like a good reason for a 1.0.1 release.

[Mellroth]

...It is equivalent in function to the 'randperm' command in MATLAB...

I think that the randperm function in MATLAB generates numbers between 1 and N.

Maybe add an option to select if the sequence is zero indexed or not?

/J

[syrus]

Instead of "assumed to be positive I32", why not use an unsigned 32-bit? Then you don't have to worry about someone passing a negative.

In my applications, this function is used to generate an array of indices that, in turn, are used to randomize the order in which data is processed from another array. I believe that LabVIEW coerces array indices to I32, so I want to use I32 for the output array. A question then is whether to use U32 for the input which could theoretically cause a problem if the user decides to input a size larger than 2147483647. The answer to that question is no because a value of 2147483647 generates a "Memory Full" error in LabVIEW, so this issue is irrelevant until the 64-bit version of LabVIEW is released.

I think that the randperm function in MATLAB generates numbers between 1 and N.

Maybe add an option to select if the sequence is zero indexed or not?

/J

Yep. MATLAB does generate numbers between 1 and N because MATLAB indexes arrays starting with 1 instead of 0. I can add a recommended boolean input to switch the indexing to 1...N.

Another non-trivial improvement could be to make the VI polymorphic allowing any compatible integer type to be used for both input and output (I32, I64, U32, U64, I8, U16, etc.), but this VI is simple enough that the end user can modify the types and the range to match their application.

In my opinion, this VI is most useful to demonstrate an efficient way to randomize an array in-place in LabVIEW, a pattern that comes up once in a while.

I'm going to wait a while to allow further discussion before I incorporate changes.

[Gary Rubin]

Forgive me if I'm being dense here, but how is that different from doing this?

[Mellroth]

Yep. MATLAB does generate numbers between 1 and N because MATLAB indexes arrays starting with 1 instead of 0. I can add a recommended boolean input to switch the indexing to 1...N.

Sounds good, and it was a very nice implementation.

If you are going to do a change, it is enough to use one "index array" node plus one "replace array subset" node.

Then you could add a "convert to I32" before feeding the random number to the array functions, this way you will only have one conversion from DBL to I32. Just to make the code even cleaner (IMHO).

/J

[syrus]

Forgive me if I'm being dense here, but how is that different from doing this?

Your solution requires at least three times as much allocated memory. It might also be slower (which one might or might not care about). I've learned to optimize for memory allocation in LabVIEW to get maximum performance out of my applications.

[Gary Rubin]

Your solution requires at least three times as much allocated memory. It might also be slower (which one might or might not care about). I've learned to optimize for memory allocation in LabVIEW to get maximum performance out of my applications.

Hmmm... Any chance you could post your VI saved as 7.1?

Thanks,

Gary

[Darren]

Forgive me if I'm being dense here, but how is that different from doing this?

The difference that I can see is that the submitted code runs 3-4 times faster than the Sort 1D Array approach.

-D

[syrus]

Hmmm... Any chance you could post your VI saved as 7.1?

Thanks,

Gary

I'll try. I do still have 8.0.1 and 7.1 running on my primary workstation. I'll have to get back to this later--I've got a few errands and meetings coming up this afternoon. --Syrus

[Gary Rubin]

I'll try. I do still have 8.0.1 and 7.1 running on my primary workstation. I'll have to get back to this later--I've got a few errands and meetings coming up this afternoon. --Syrus

Thanks,

Gary

[syrus]

Hmmm... Any chance you could post your VI saved as 7.1?

Thanks,

Gary

Hi again Gary,

I can save as far back as 7.0 using "Save for previous..." under 7.1.1. I'm attaching all three versions of the 1.0.0 release to this message.

Download File:post-3106-1161639025.zipDownload File:post-3106-1161639046.zipDownload File:post-3106-1161639058.zip

[Michael Aivaliotis]

Hi again Gary,

I can save as far back as 7.0 using "Save for previous..." under 7.1.1. I'm attaching all three versions of the 1.0.0 release to this message.

Admin Note: For the next release, perhaps you can include the older labview versions in the zip file. Another option is to develop in LV7.0 or 7.1 and release it in that version only. People can then upconvert. Just some suggestions to streamline the process.

[Gary Rubin]

I can save as far back as 7.0 using "Save for previous..." under 7.1.1. I'm attaching all three versions of the 1.0.0 release to this message.

Thanks, I look forward to playing with it tomorrow.

Gary

[syrus]

Admin Note: For the next release, perhaps you can include the older labview versions in the zip file. Another option is to develop in LV7.0 or 7.1 and release it in that version only. People can then upconvert. Just some suggestions to streamline the process.

Thanks Michael. I'll improve my process as you suggest for the 1.0.1 release. --Syrus

Edit: I have uploaded a 1.1.0 release in response to the discussion today. I updated the minor version number because this is not a bugfix release. The following changes were made:

1.1.0:

Added input validation, error handling, and the option to use "MATLAB mode" and generate a permutation of the integers from 1 to n instead of 0 to n-1, where n is the value wired to the size input. Added a "convert to I32" before feeding the random index to the array functions to eliminate two coercion dots. Updated description to reflect these changes. Changed wiring pattern to 4-2-2-4 and changed icon to accomodate additional terminals.

[Gary Rubin]

Syrus,

There are a couple ways that it seems that you can squeeze out a few more microseconds. I ran some benchmarks for size=1000, and on my 2.4GHz P4, I was able to trim the execution time from ~0.76ms to ~0.70ms.

First, get rid of the coercion dots by converting those two coerced wires to dbl.

Second, I read somewhere (probably one of the Labview App notes, which I can no longer find), that case structures have a fair amount of overhead associated with them, so for simple things like your Matlab switch, it's better to use a Selector node.

Gary

[syrus]

Syrus,

There are a couple ways that it seems that you can squeeze out a few more microseconds. I ran some benchmarks for size=1000, and on my 2.4GHz P4, I was able to trim the execution time from ~0.76ms to ~0.70ms.

First, get rid of the coercion dots by converting those two coerced wires to dbl.

Second, I read somewhere (probably one of the Labview App notes, which I can no longer find), that case structures have a fair amount of overhead associated with them, so for simple things like your Matlab switch, it's better to use a Selector node.

Gary

Hi Gary,

When I decided to add the MATLAB switch, I was no longer woried about a few microseconds--users who are that pressed for performance can extract the portion of the diagram they need and remove all case structures. Regarding coercion dots, I don't believe replacing the automatic coercion with an explicit coercion should make a difference in performance (although I'm not disputing that it does in your version of LabVIEW).

Regarding the selector instead of case structure, I would like to know whether the selector computes all inputs before evaluation or if it smartly evaluates the condition first. It may indeed be smart, but it is not obvious from a dataflow point-of-view. I therefore would err on the side of code clarity to use the case structure instead of the selector.

When I decided to add error handling and input validation, it was because I realized that I had performed premature optimization.

[Gary Rubin]

Regarding the selector instead of case structure, I would like to know whether the selector computes all inputs before evaluation or if it smartly evaluates the condition first. It may indeed be smart, but it is not obvious from a dataflow point-of-view. I therefore would err on the side of code clarity to use the case structure instead of the selector.

I wish I could find that App Note...

My understanding was that Labview will evaluate both paths. It just happens that for simple things like incrementing vs. not incrementing, performing an unecessary addition is faster than the overhead associated with using a case structure to not performing the operation.

[syrus]

I wish I could find that App Note...

My understanding was that Labview will evaluate both paths. It just happens that for simple things like incrementing vs. not incrementing, performing an unecessary addition is faster than the overhead associated with using a case structure to not performing the operation.

In our VI, LabVIEW is modifying the whole array, not performing an addition on a scalar. And, since both branches must be preserved, LabVIEW will produce an extra copy of the array.

[Gary Rubin]

In our VI, LabVIEW is modifying the whole array, not performing an addition on a scalar. And, since both branches must be preserved, LabVIEW will produce an extra copy of the array.

Yeah, you're right. Now I really wish I could find whatever it was I had read to try to figure out what it was recommending.

[PJM_labview]

...Regarding coercion dots, I don't believe replacing the automatic coercion with an explicit coercion should make a difference in performance (although I'm not disputing that it does in your version of LabVIEW)...

It has been my experience that explicit coercion does improve performance.

PJM

[robijn]

The difference that I can see is that the submitted code runs 3-4 times faster than the Sort 1D Array approach.

-D

Hmm, only 1.6 times faster here, P4 1.7GHz, LV711

If you multiply the random number by 2^31-1 and store it as an I32 it is only 1.25 times faster.

The preallocation stuff is quite fast, and the speed of the sort function is amazing.

I like neat small diagrams more

Joris

[Kevin P]

It has been my experience that explicit coercion does improve performance.

Hmmm. The few times I was really trying to shave down the microseconds, I measured better speed with the coercion dot. As I recall, I was testing a histogram-like binning algorithm. The coercion in question was for an array index that was calculated in floating-point. For some reason, an explicit conversion to i32 ran very slightly, but quite consistently, slower than leaving the coercion dot.

Still, I almost always do my coercions explicitly anyway.

-Kevin P.

[JDave]

Hmmm. The few times I was really trying to shave down the microseconds, I measured better speed with the coercion dot. As I recall, I was testing a histogram-like binning algorithm. The coercion in question was for an array index that was calculated in floating-point. For some reason, an explicit conversion to i32 ran very slightly, but quite consistently, slower than leaving the coercion dot.

Still, I almost always do my coercions explicitly anyway.

I also benchmarked this some time ago and got varying results. Depending on the data I got better results with explicit or implicit coercion. However, the difference was minimal. So for most applications it would be better to do explicit coercion because it exposes what is happening a little more clearly (or more correctly if you fix any latent bugs ).

David