01-11-2024 05:10 PM
Hello LabVIEW World. I'm trying to figure out a more elegant and faster way to resolve the attached image. Yes what I have works, but when you have 500K elements and an unknown number of "Hole in Wall" elements, it could potentially take a while as deleting from arrays causes LabVIEW to recreate the array which can be a decent amount of processing time. So I thought maybe some of the more brilliant minds here would like to offer their input. (Context, the indices refer to a cloud of points that create a wall)
I had an idea of maybe rearranging the array so that any found element gets placed at the end of the Wall array and then I delete the length of the "Hole" from the end of the array. Might could be faster?
01-11-2024 05:32 PM
I've attached a VI that contains a bunch of Indices. On my machine, it took little over 50 seconds to complete this task with the data.
01-11-2024 06:00 PM
I'm out of time for today and threw this together- there's an off-by-one bug somewhere in there that I don't have time to fix, but hopefully this leads you down the right path.
This one completed the sorting in 0.149 seconds on my machine:
(Also, the usual caveats about proper benchmarking apply here... you'd need to disable debugging, run them each "fresh", etc but the point is this method should be considerably faster anyway.)
The issue is that in the original version you're having to look through the ENTIRE array each time you search for a point to remove. This way only has to iterate once when it builds the map, once when it builds the cluster array, once when it sorts, and once when it pulls out the sorted elements. And the compiler is probably smart enough to eliminate one or two of those.
I also took it as an implied assumption that "Wall Indices" are unsorted and that the order matters. If the order DOESN'T matter, then you can eliminate a lot of this code and just use a Set. Do one loop to add each element to the Set, then one loop to remove each "Hole" indices from the Set, and one final one to get back an array.
01-12-2024 02:56 AM
Hi Luminary,
@LuminaryKnight wrote:
As I cannot open your VI due to its LabVIEW version I have to ask on this image:
You search the index of the "hole in wall" element in the "Wall" array, then you use the found index as length parameter in the DeleteFromArray operation?
01-12-2024 08:00 AM
@GerdW wrote:
Hi Luminary,
@LuminaryKnight wrote:
As I cannot open your VI due to its LabVIEW version I have to ask on this image:
You search the index of the "hole in wall" element in the "Wall" array, then you use the found index as length parameter in the DeleteFromArray operation?
😅 HA - yep, that was definitely a mistake. Good catch. Fixed it, and it still takes 50 seconds. But actually does it right.
01-12-2024 08:08 AM - edited 01-12-2024 08:18 AM
@BertMcMahan wrote:
I'm out of time for today and threw this together- there's an off-by-one bug somewhere in there that I don't have time to fix, but hopefully this leads you down the right path.
This one completed the sorting in 0.149 seconds on my machine:
(Also, the usual caveats about proper benchmarking apply here... you'd need to disable debugging, run them each "fresh", etc but the point is this method should be considerably faster anyway.)
The issue is that in the original version you're having to look through the ENTIRE array each time you search for a point to remove. This way only has to iterate once when it builds the map, once when it builds the cluster array, once when it sorts, and once when it pulls out the sorted elements. And the compiler is probably smart enough to eliminate one or two of those.
I also took it as an implied assumption that "Wall Indices" are unsorted and that the order matters. If the order DOESN'T matter, then you can eliminate a lot of this code and just use a Set. Do one loop to add each element to the Set, then one loop to remove each "Hole" indices from the Set, and one final one to get back an array.
Nicely done. Yes, very curious 1 element is missing. But still significantly faster. I have absolutely no knowledge of Maps and this has sparked my research interest. So I will be reading up on Maps. Something tells me this could come in handy with the other things I'm working on. Thank you!
And no, the order doesn't matter. Just the understanding that a singular value will only ever be present once. But somewhere.
01-12-2024 08:25 AM
Delete from array is _very_ expensive and should only be used for singular (few) removals. As soon as there are several it's faster to rebuild the array.
This seems quite fast. 🙂
01-12-2024 08:50 AM
@Yamaeda wrote:
Delete from array is _very_ expensive and should only be used for singular (few) removals. As soon as there are several it's faster to rebuild the array.
This seems quite fast. 🙂
So I'm not entirely sure I follow what you're trying to do here. Let me know if I didn't duplicate it correctly. But this nearly broke my machine. Filled up my memory instantly.
01-12-2024 12:51 PM - edited 01-12-2024 12:53 PM
My entry, hats off to Bert for submitting something older than 2023 which I can't open at my work PC. I'm surprised this wasn't much faster than building the map but I guess the sorts end up about equivalent.
01-12-2024 01:16 PM
@LuminaryKnight wrote:And no, the order doesn't matter. Just the understanding that a singular value will only ever be present once. But somewhere.
Well heck then, here's a much simpler version:
All of the Map shenanigans were to maintain the original order. If the order doesn't matter, and all elements are duplicates, then Sets are a much simpler way to do this. 0.081 seconds to do the same array.
(Still one element missing... I suspect the source data may have a duplicate but I'm out of forum time for now, lol)