So, ok, maybe we can talk a bit more about the system this fits into, in dissect? Please forgive me for being slow, I'm not thinking about this very well at the moment.
My first attempt at an implementation looked like this: 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 proc=: dyad define P=. x D=. y C=. notblocked=. _1 ~: D CP=. C#P CD=. C#D C #inv!._1 CD<.CP+<./\ CD ) Here, I was thinking that D would represent the shortest distance from any node to the left. But, clearly, that's not what you have asked for. Instead, you're going for "nearest left neighbor", and apparently there tend to be a lot of these, and you run a lot of tries. So, taking a step back, just a little - for dissect I imagine you have a rectangle size that you need to support (and presumably you're clamping these sizes for large arrays, with interior scrolling within the rectangle though... hmm... a quick test (10+i.1e3 1e3) suggests that you are also handing the entire inner rectangles off to Qt to manage - perhaps out of necessity, given the current jQt implementation?). Anyways... I imagine your data structure is some kind of a directed acyclic graph describing which rectangles connect to which rectangles and you're trying to approximate a "minimum total distance for the connections" algorithm. So... all of this sort of suggests that D represents a specific path from the start of the expression down through the various rectangles representing intermediate results and down to a specific [intermediate] result. But that path contains several aspects: left-to-right position and where you introduce the bends. So, anyways, presumably this represents... the location of those bends? And the total horizontal distance traveled? (As you can see, I'm having trouble understanding the spec itself, and not just the algorithm it fits into... ) Going back to the algorithm I described above - it might represent something like an A* approach if you slapped a ^:_ onto it. But limiting us to the immediate left neighbor? That... doesn't actually seem to me to be an a star algorithm. Anyways, if you feel comfortable spelling this out in more detail, I think that could help me understand what you're asking for. Thanks, -- Raul On Mon, Feb 22, 2016 at 9:40 PM, Henry Rich <[email protected]> wrote: > No, the weights are fixed. > > I am implementing essentially the A* algorithm: > > https://en.wikipedia.org/wiki/A*_search_algorithm > > The code is for dissect: given a number of blocks and a set of > (source,destination) pairs, find paths to connect the pairs, on a discrete > routing grid. > > One important optimization is the problem I gave. It arises when the > connection to be made is across a large empty space, and it is important to > cross the space without trying all the different ways to do it. > > The distance in each element of D is the distance from the starting point(s) > to the cell represented by the element. If cell B is next to cell A, with a > penalty of P for moving to the cell, one way of reaching B is D(A)+P(B); the > other is whatever external path provided a distance for D(B). The requested > program solves this problem for the whole grid at once, for the special case > of moves in a single direction. > > I was thinking about asking for help in solving this problem, but I came up > with a good solution. I hope that a better one will be found, but for the > moment I pose it as a challenge to use J to produce an efficient solution > for this problem which would be easily solved in C. > > Henry Rich > > > > On 2/22/2016 9:17 PM, Michal Wallace wrote: >> >> 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 > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
