Jump to content

[CR] Random permutation


Recommended Posts

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.

Link to post
Share on other sites
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. :unsure:

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. :unsure:

Link to post
Share on other sites
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

Link to post
Share on other sites
Forgive me if I'm being dense here, but how is that different from doing this?

post-4344-1161628516.gif?width=400

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.

Link to post
Share on other sites
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

Link to post
Share on other sites
Forgive me if I'm being dense here, but how is that different from doing this?

post-4344-1161628516.gif?width=400

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

-D

Link to post
Share on other sites
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

Link to post
Share on other sites
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.
Link to post
Share on other sites
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.

Link to post
Share on other sites

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

Link to post
Share on other sites
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.

Link to post
Share on other sites
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.

Link to post
Share on other sites
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.

Link to post
Share on other sites
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.

Link to post
Share on other sites
...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

Link to post
Share on other sites
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

Link to post
Share on other sites
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.

Link to post
Share on other sites
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 :yes: ).

David

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.