I have put my solution to this problem in
http://code.jsoftware.com/wiki/Essays/PropagatingMinimum
The details are a little different, but the basic idea is the same.
Henry Rich
On 3/2/2016 3:15 PM, Brian Schott wrote:
Oops, I forgot to enter "the following sentence":
expand;<./@lineup each
Oops, I forgot to enter "the following sentence":
expand;<./@lineup each DD([,+)each each PP
On Wed, Mar 2, 2016 at 3:14 PM, Brian Schott wrote:
> Upon a closer look, and Henry's earlier comment (see below) regarding "...the
> little piece excP...", and noticing that my most recent last line re
Upon a closer look, and Henry's earlier comment (see below) regarding "...the
little piece excP...", and noticing that my most recent last line really
requires that the verb excD (which is almost identical to excP)must be
executed at each step also, I can tell more efficiency is required.
I am say
I have a faster script which pre processes all the lines except the line.
Only the last line is executed at each step.
The boxing, lining up, and unboxing worries me, but this is a speed
improvement,
for me.
H =: 99 NB. can be any large value, like 1e6
L =: _1
D =: H, H, 1, H, 5, H, 8, H, 11, L,
Yes, an external process updates the data D but not the penalties (or
the positions of the blockages indicated by L). This code gets called
maybe 2000-5000 times on a list of length 100 or so and needs to take
less than 0.1 seconds to run all the iterations.
Henry Rich
On 3/1/2016 3:51 PM, J
Raul, yes, that helps. Thanks
I'm not entirely clear about the performance issues with any of the
approaches outlined. It would be useful to be able to simulate that I
think so any of the approaches outlined or new ones could be tested.
It sounds like the approach will be called multiple times pe
I implemented what I think is a scalar model of how this could work:
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
mdi=:dyad define
x+y
P=.x
r=. D=.y
for_j. }.i.#D do.
p=. j{P
d0=. (j-1){D
d1=. j{D
if.
Henry, just curious, do you have a scalar solution to the problem? You
mentioned it'd be trivial to write so I was curious if there is one.
It'd be helpful to compare against. Is the pseudocode on wikipedia
what you had in mind?
https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
On Mo
You can avoid splitting the input into sections.
Henry Rich
On 3/1/2016 7:52 AM, Brian Schott wrote:
By not needing to calculate the whole thing, do you mean that because the
L's are permanent you only need to calculate the sums for sections between
the Ls, or is there something else?
On Tue,
By not needing to calculate the whole thing, do you mean that because the
L's are permanent you only need to calculate the sums for sections between
the Ls, or is there something else?
On Tue, Mar 1, 2016 at 7:39 AM, Henry Rich wrote:
> Now you're talkin'. You don't have to calculate the entire
Now you're talkin'. You don't have to calculate the entire +/\\. either.
FSM is not needed.
Henry Rich
On 3/1/2016 7:35 AM, Brian Schott wrote:
Henry,
I suspect the trick is that the list P does not change and that +/\\. can
be precalculated (perhaps with boxed lists of sums), and then reus
Henry,
I suspect the trick is that the list P does not change and that +/\\. can
be precalculated (perhaps with boxed lists of sums), and then reused when
D changes. Maybe even an fsm could be developed to combine the new D's.
What say you?
--
(B=)
-
Henry,
I can now see how a slight improvement on D++/\\.P can accomplish the
desired result,
but can you say if even that much is too slow.
If that is not two slow, then my next question is this:
The +/\\.P constructs a square matrix with incrementally more 0 fills on
each row. I want the fills
I can't follow what the verb is doing, but I tried it on some other
cases & it produced correct results.
Needless to say, a much faster version is needed. Even the little piece
excP,
which potentially runs the verb < on each atom, would be too slow.
Henry Rich
On 2/29/2016 5:36 PM, Brian Sc
I have a non iterative script which seems to work on the test sample.
Can you tell me if it works more generally, please?
H =: 99 NB. can be any large value, like 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
excP =: (1,L=])<;._1
No.
The first atom of the array might potentially affect the result in the
last atom.
I need a method that takes at most a couple of dozen machine
instructions per atom. Any method that starts a verb on each atom of
the array is too slow.
Henry Rich
On 2/25/2016 10:35 PM, Brian Schott wr
Does your really fast algorithm start with something like my mask, but
instead of a while. loop on the whole array, do you just check to update
the indices one above each altered atom of the revised D?
On Wed, Feb 24, 2016 at 11:43 AM, Henry Rich wrote:
> That looks like the right result.
>
> He
That looks like the right result.
Henry Rich
On 2/24/2016 11:20 AM, Brian Schott wrote:
Not FAST, but is this correct?
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
while
Not FAST, but is this correct?
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
while. +./mask=.(L~:H,}:D)*.D>D<.P+H,}:D do.
D=. mask{"0 1|: D,:P+H,}:D
end.
D
)
D,:P proc D
100
You are right, the last 2 atoms could be *s.
Penalties & distances are measured in the same units & are essentially
the same in this context. To move to a new atom you must pay a penalty
and traverse a distance, both of which are rolled into the value in P.
D holds accumulated values of P, e
Henry,
Why in your example answer for D aren't the rightmost 2 atoms *s, since
they have not changed from 20 and 3? Does that suggest that the "new" 20
and 3 are calculated but that you are not giving their calculations?
Also you say, "An atom of D indicates the minimum number of penalty points
t
'proc' has the right idea, but CP+<./\ CD does not take into account all
the P values between the minimum point found by <./\CD and the point
that the minimum value is being propagated to. It adds in only the last
P. [Also it doesn't prevent a value from affecting results on the other
side of
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 =:
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
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, tr
I left out one important point. The list P, and the locations of
blocked-off sections of D, do not change over the many iterations of the
verb you are asked to design. They represent the obstacles that the
router is trying to avoid.
What changes between iterations is the non-blocked values o
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
27 matches
Mail list logo
