[Jprogramming] A practical problem: minimum distance with penalties

Tue Mar 1 22:42:44 UTC 2016

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, Joe Bogner wrote:
> 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 per interval
> as some external process is updating data? Running it once with the
> parameters outlined seems to be fine:
>
> timespacex '(? 10000#20) mdi ((? 10000#15) { D)'
> 0.0384976 926464
>
> But I could see how that would be a problem if it needs to be run 100
> times per second. It would be helpful to include the simulation in the
> problem definition.
>
> On Tue, Mar 1, 2016 at 3:25 PM, Raul Miller <rauldmiller at gmail.com> wrote:
>> 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. d0>_1 do.
>>        D=. (d1 <. d0+p) j} D
>>      end.
>>    end.
>>    D
>> )
>>
>>     P mdi D
>> 1000000 1000000 1 3 5 7 8 9 10 _1 _1 1000000 1000000 20 3
>>
>> That said, I'll note that Henry left a number of semi-wildcards in his
>> spec - perhaps for good reason.
>>
>> That said, I don't have a good mental model of what's supposed to
>> happen here, I'm just working rotely, which limits my ability to think
>> about the problem. (Henry's description about how it's used didn't
>> hook into anything I understood.)
>>
>> I hope this helps,
>>
>> --
>> Raul
>>
>>
>>
>> On Tue, Mar 1, 2016 at 3:21 PM, Joe Bogner <joebogner at gmail.com> wrote:
>>> 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 Mon, Feb 22, 2016 at 1:28 PM, Henry Rich <henryhrich at gmail.com> 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