10-21-2011 10:44 AM - edited 10-21-2011 10:48 AM
I need to determine if any one array element is equal to any other (except itself, of course) within the same array. Attached is my current way. Is there something more efficient? In my software it's only a few elements so efficiency is not a big deal. More just curious for future reference.
Edit: forgot to disconnect from typedef.
10-21-2011 10:56 AM - edited 10-21-2011 10:57 AM
Just fake some huge data structures and do some benchmarking, then try some alternative methods. 😄
I think a ">=0" would be suficient after search, you don't need to compare two numbers. (You don't care about the positions, just if there is a match.)
(EDIT: Hey, you changed it from the previous attachment already! :D)
The effort depends on the positions. It is worst if only the last two elements are the same. There might be better ways, but I need to think about it.... Also make sure there is no extra buffer allocation for the input array since you are branching the wire before the loop. (The compiler might be smart enough not to make a copy.)
10-21-2011 11:04 AM
altenbach wrote:
The effort depends on the positions. It is worst if only the last two elements are the same. There might be better ways, but I need to think about it.... Also make sure there is no extra buffer allocation for the input array since you are branching the wire before the loop. (The compiler might be smart enough not to make a copy.)
With regards to the buffer allocation, would your recommendation be branch it in the loop with an index array off the loop counter? I guess I could use some of the LabVIEW tools to deteremine what's best in terms of buffering.
10-21-2011 11:20 AM
For reasonable size arrays I would try this as well:
10-21-2011 11:38 AM
10-21-2011 12:03 PM
You could try sorting the array first. You wouldn't have to search everytime. Just look at the next element to see if it matches. If you do, you need to keep looking until it doesn't if you're trying to remove the duplicates. Don't know if it would be better, though.
10-21-2011 12:13 PM
Matthew eloquently described the simple algorithm that my snippet uses. Sort followed by comparing each element to its neighbor (I use rotate array for this, not the most inplace, but simple).
If the array is very large (doesn't sound like it) you could spend a few minutes to shave a couple of msecs off the time by writing out the algorithm longhand and allowing the search to stop as soon as a duplicate is found (short circuiting). You could also explicitly index the array instead of using the rotate trick, again only necessary for huge arrays.
10-21-2011 12:22 PM
10-21-2011 02:06 PM - edited 10-21-2011 02:07 PM
@altenbach wrote:
I just looked at your data structures, and your elements are simple clusters of two booleans. If the array size is larger than 4, you are guaranteed to have duplicates. No code needed. 😄
HAHA, in fact, the actual array in software has, and will only have 3 clusters. Good catch though. Brings back my algebra II days and permutations/combinations! This is more just for my own knowledge in case for some reason I was using numerical, string, etc values in the future.