Replace array subset in parallel for loop without increasing memory

[altenbach]

---

@Kevin_Price wrote:

Meanwhile, you may want to look a more sophisticated, less brute-force method.

---

The current problem is different, because we have vectors and simply need to find the closest next vector starting point from the current endpoint (i.e. O(n²)) while the TS problem is O(n!), much harder. Of course we could ask if the current algorithm gives is the shortest possible total path across all vectors and the answer is probably no. I need to think about that. 😄

[Kevin_Price]

• Find the shortest distance using a FOR loop. (This allows starting the min search at any given index).
• Swap the shortest with the first element and remember the endpoint
• find the shortest from the last endpoint, starting with the second element
• Swap the shortest with the second element
• repeat for all elements. 

This swapping approach while using "Replace Array Subset" to do it in-place was one of the things I tried too.  But I actually got slightly faster results with the following tweak:

I got rid of the in-place swapping and shift register, and instead I auto-concatenated each "shortest distance" point pair onto the output boundary of the inner For Loop.   It wasn't a big difference though and I wouldn't promise it's statistically significant.

-Kevin P

[Kevin_Price]

---

@altenbach

---

The current problem is different, because we have vectors and simply need to find the closest next vector starting point from the current endpoint (i.e. O(n²)) while the TS problem is O(n!), much harder. Of course we could ask if the current algorithm gives is the shortest possible total path across all vectors and the answer is probably no. I need to think about that. 😄

Oops, our replies are overlapping.

Back earlier in the thread however, I believe the *real* goal was never intended to be just to optimize this specific algorithm.  I thought we were focused on it mainly because it's the tangible "bird in hand", and might be a good enough algorithm to accomplish the real goal.

I'm no expert in algorithm theory, but I thought the linked "genetic algorithm" approach to the TS problem could likely be just slightly modified to become an entirely different kind of approach to accomplishing the original poster's real goal -- a "good enough" amount of improvement in these cumulative vector-gap distances, executing in a "fast enough" amount of time.

As mentioned before, I have no idea whether the OOP implementation in the link was ever meant to scale up to hundreds of thousands of lengths per layer.  But knowing the author, it's probably durn good code for whatever the design intent *was*.   Still speculating, haven't really looked it over or tried it yet.  But what's the internet for if not reckless speculation?

-Kevin P

[tshurtz]

Its true, the true goal is ti minimize the space between all vectors. This "greedy" algorithm does not guarantee the optimal solution, in fact it is possible to result in the worst possible solution for specific data (part of why I throw out the new order if it isn't at least as good as the old order, but it generally does a good job if not a great job at reducing the total waste. If another method can perform significantly better in similar time I am interested. I might try allowing for flipping the vectors as well (so start and stop of a vector can be swapped) but ultimately I believe doubling the number of points that can be ordered will not yield significantly better results and will take 4x longer. It is worth a shot though and I will probably try it at some point just to see but I don't have high hopes (also I am not certain the output will not effect my process I am controlling.

Thanks again for all or your help.

[tshurtz]

Leaving off the last loop and first loops as i mentioned previously still finds the same order, but the total length per layer is not calculated correctly (it doesn't include the 2nd to last to last point distance), or the same for the first point (I think that distance should just be ignored in this algorithm). 

[altenbach]

---

@tshurtz wrote:

Leaving off the last loop and first loops as i mentioned previously 

---

This forum has poor threading, so I am not sure which "loops" you are "leaving off". Are you talking about loops or iterations?

[tshurtz]

sorry I meant how I left off the first and last iterations of my inner loop.

Thanks.

[wiebe@CARYA]

---

@tshurtz wrote:

Thanks again!

---

There is still a potential optimization here.

Note how the inner loop does a lot of work. Then all the results are added, and if the result is bigger it's not even used!

So in the inner loop, we can add all the distances in a shift register. Then we can conditionally stop the loop if it gets too big. The add after the inner for loop can be removed.

(NOTE: Completely untested! Also not sure if it even is faster!) 

My benchmarks go all over the place. First run 38 s. Then removed the swaps: 38 s. Restored the swaps 70s. Removed swaps 38... I worked from an untitled VI, and sometimes saving the VI makes a difference.

[altenbach]

---

wiebe@CARYA wrote:

---

@tshurtz

Note how the inner loop does a lot of work. Then all the results are added, and if the result is bigger it's not even used!

---

That's one of the things I tested early on and it might work better with real data. With the random data, early stops seem to be rare. OTOH, checking for early termination with every iteration causes more overhead and slows down each iteration.

[wiebe@CARYA]

---

@altenbach wrote:

---

wiebe@CARYA wrote:

---

@tshurtz

Note how the inner loop does a lot of work. Then all the results are added, and if the result is bigger it's not even used!

---

That's one of the things I tested early on and it might work better with real data. With the random data, early stops seem to be rare. OTOH, checking for early termination with every iteration causes more overhead and slows down each iteration.

---

I agree. Could not make any difference. Guess OP has to check with real data.

Any thoughts on the swap? Can we be sure it compiles to a NO-OP? The swaps are a (tiny) bit cleaner, but I'd default to swapping the wires. The performance difference might be in the noise margins...