Huh? :) I'm not sure I understand what any of this has to do with finding a shortest path.
You say D is a list of ordered distances... Distances between what? Is the idea that you have a graph, with a fixed number of nodes, but the edge costs have shifting weights for some reason? (Like say, traffic congestion during rush hour?) And if so, is the idea that you're trying to dynamically adjust to the changing weights, to see if a longer route might be better when congestion is high? I'm not sure, but it seems like you're asking us to help you optimize the innermost loop of an algorithm you've already created. If so, it might be more enlightening to ask how people might solve the problem as a whole -- maybe we might turn up a different algorithm altogether? On Mon, Feb 22, 2016 at 12:28 PM, Henry Rich <[email protected]> wrote: > This task shows J in my hands at its best and its worst. Best, because I > found a good solution; worst, because it took me 4 hours to come up with > something that would have been trivial in a scalar language. See what you > can do with it. > > The task is to write a REALLY FAST program to solve the problem. Solving > the problem correctly is not so hard, but this is the innermost loop of > many nested loops, and it must run at close to maximum machine speed. > > The problem arises in shortest-path-finding. You are given two lists, the > list of distances D and the list of penalties P. D is to be thought of as > ordered left-to-right. An atom of D indicates the minimum number of > penalty points that must be incurred to reach that position. > > At each step, new elements of D are created by external code, as new best > ways to reach positions are discovered. After the new elements of D have > been installed, you come in. You have to process D (and P) to propagate > the new distances through D, leaving every atom of D showing the best > distance. This best distance may be either the incumbent distance at that > position, or a smaller value inherited from the position to its left. If > you inherit the distance from the left, you must add the value of the atom > of P in the position being moved into. The incumbent value in that > position already includes the value of P. > > There is one more fillip. Certain positions of D are blocked off. A > blocked-off atom must not be changed, and its value may not be inherited by > the cell to its right. > > In the representation of D, empty cells are given a distance of HIGH-VALUE > (=1e6), and blocked cells are given a distance of LOW-VALUE (=_1). > > Example: > > Given the setup > H =. 1e6 > L =. _1 > D =. H, H, 1, H, 5, H, 8, H, 11, L, L, H, H, 20,3 > P =. 1, 1, 1, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2 > > you would produce > > > * * * 3 * 7 * 9 10 * * * * 20 3 > > 3 = 1+2-------| > 7 = 5+2-------------| > > The * values indicate 'anything greater than or equal to the incumbent > value' and indicate atoms that are unchanged by the process. You are free > to give them any value you like, as long as it is not less than the > incumbent value. > > The numbered values are the inherited distances: the ones you must find. > > All the values can be integer and all are small compared with the range of > an integer. The length of the lists will not exceed 10,000, the values of > D will not exceed 50,000, and the values of P will not exceed 20. > > Your code will be executed many times. If you want to factor out > computation by pre-computing any values, do so and do not count that as > part of the execution time. > > Henry Rich > > > > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
