Right, definitions have a cost -- parsing for exampler. To demonstrate:
func=: 3 : 0
for_i. i.y do.
swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's.
swap _
end.
1
)
func2=: 3 : 0
swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's.
for_i. i.y do.
swap _
end.
1
)
timespacex 'func 1e5'
0.46398 1.06112e6
timespacex 'func2 1e5'
0.149825 1.05818e6
Your remove verb can be redefined from:
remove =. ,@:|:@:(_&(list}))@:(list&{"1) NB. remove rows already in the
list and flatten matrix.
To something simpler, that takes list as a parameter
I would need a test case to see what this is doing to recommend a better
way. At the very least, you could just replace list with y in an explicit
definition outside of the loop
On Fri, Oct 24, 2014 at 12:12 PM, Jon Hough <[email protected]> wrote:
> I see,
> the verb swap should be outside the loop, but the way I defined remove,
> means it needs to be redefined for each iteration (because list changes, I
> think).I'm assuming redefining it inside the loop slows down the
> calculation?
>
> > Date: Fri, 24 Oct 2014 12:09:07 -0400
> > From: [email protected]
> > To: [email protected]
> > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm
> >
> > In terms of a code review, a few things:
> >
> > the first thing that jumps out to me is that you're defining some verbs
> in
> > your loop:
> >
> >
> >
> >
> > On Fri, Oct 24, 2014 at 11:57 AM, Jon Hough <[email protected]> wrote:
> >
> > > Here it is
> > >
> > >
> > >
> > > prim_alg =: verb define
> > >
> > > list =. 0 NB. list of already counted nodes (start at zero)
> > >
> > > pairs =: '' NB. the pair, i.e. edges, of the spanning tree.
> > >
> > > mat =. y NB. distance matrix, infinity imlies not
> adjacent.
> > >
> > > size =. 0{ $ y NB. Matrix must be square, so just get size of one
> axis.
> > >
> > > while. (size > (# list)) do.
> > >
> > > swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's.
> > >
> > > remove =. ,@:|:@:(_&(list}))@:(list&{"1) NB. remove rows already in the
> > > list and flatten matrix.
> > >
> > > NB. get the next node (still need to get its(i,j) coords)
> > >
> > > next =. (I.@:(swap"0)@:(=<./))@:remove mat
> > >
> > > next =. 0{ next
> > >
> > > NB. get the new node (row index in matrix)
> > >
> > > temp =. size | next
> > >
> > > prevnode =. ((next - temp) % size ){ list NB. find which node reached
> the
> > > new node.
> > >
> > > newnode =. temp
> > >
> > > pairs =: pairs, (< ( prevnode, newnode))
> > >
> > > NB. add new node to list (so don't try to reach it in next iteration).
> > >
> > > list =. list, newnode
> > >
> > > end.
> > >
> > >
> > >
> > >
> > > pairs
> > >
> > > )
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > mat0 =: 4 4 $ _ _ _ 2, _ _ _ 5, _ _ _ 1. 2 5 1 _
> > >
> > > mat1 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7 _ 9 _
> > >
> > > mat2 =: 6 6$ _ 184 222 177 216 231, 184 _ 45 123 128 200, 222 45 _
> > > 129 121 203, 177 123 129 _ 46 83, 216 128 121 46 _ 83, 231
> 200
> > > 203 83 83 _
> > >
> > >
> > >
> > >
> > >
> > > (along with some example matrices)
> > > > Date: Fri, 24 Oct 2014 11:53:28 -0400
> > > > From: [email protected]
> > > > To: [email protected]
> > > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's
> Algorithm
> > > >
> > > > Jon, can you resend without the extra line feeds?
> > > >
> > > > You may need to paste as text or ctrl+shift+v
> > > >
> > > > Pasting it into another editor, such as notepad and then copy/pasting
> > > from
> > > > there is another way to be sure it's plain text
> > > >
> > > > On Fri, Oct 24, 2014 at 10:02 AM, Jon Hough <[email protected]>
> wrote:
> > > >
> > > > > Finding the minimum spanning tree of a graph is (in theory) pretty
> > > easy.
> > > > > I wanted to see if I could write Prim's algorithm in J.The
> algorithm is
> > > > > conceptually simple: http://en.wikipedia.org/wiki/Prim's_algorithm
> ,
> > > and
> > > > > I thought it would not be too difficult to write in J. My attempt
> goes
> > > like
> > > > > this:
> > > > > 1. Use a distance matrix to represent the graph (with infinity
> > > > > representing no connection, and (i,i) positions are also infinity.
> > > > > 2. Loop through the matrix, simultaneously looking for shortest
> edges
> > > from
> > > > > a list of already counted nodes and strike out connections to any
> of
> > > these
> > > > > nodes (to not make trees).
> > > > > This is my attempt:
> > > > >
> > > > >
> > > > > prim_alg =: verb define
> > > > >
> > > > >
> > > > >
> > > > > list =. 0 NB. list of already counted nodes (start at zero)
> > > > >
> > > > >
> > > > >
> > > > > pairs =: '' NB. the pairs, i.e. edges, of the spanning tree.
> > > > >
> > > > >
> > > > >
> > > > > mat =. y NB. distance matrix, infinity implies not
> > > adjacent.
> > > > >
> > > > >
> > > > >
> > > > > size =. 0{ $ y NB. Matrix must be square, so just get size of one
> > > axis.
> > > > >
> > > > >
> > > > >
> > > > > while. (size > (# list)) do.
> > > > >
> > > > >
> > > > > NB. inner functions
> > > > >
> > > > >
> > > > >
> > > > > swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with
> 0's.
> > > > >
> > > > >
> > > > >
> > > > > remove =. ,@:|:@:(_&(list}))@:(list&{"1) NB. remove rows already
> in the
> > > > > list and flatten matrix.
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > NB. get the next node (still need to get its(i,j) coords)
> > > > >
> > > > >
> > > > >
> > > > > next =. (I.@:(swap"0)@:(=<./))@:remove mat
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > NB. get the new node (row index in matrix)
> > > > >
> > > > >
> > > > >
> > > > > temp =. size | next
> > > > >
> > > > >
> > > > >
> > > > > prevnode =. ((next - temp) % size ){ list NB. find which node
> reached
> > > the
> > > > > new node.
> > > > >
> > > > >
> > > > >
> > > > > newnode =. temp
> > > > >
> > > > >
> > > > >
> > > > > pairs =: pairs, (< ( prevnode, newnode))
> > > > >
> > > > >
> > > > >
> > > > > NB. add new node to list (so don't try to reach it in next
> iteration).
> > > > >
> > > > >
> > > > >
> > > > > list =. list, newnode
> > > > >
> > > > >
> > > > >
> > > > > end.
> > > > >
> > > > >
> > > > >
> > > > > pairs
> > > > >
> > > > >
> > > > >
> > > > > )
> > > > >
> > > > > It seems to work for the matrices I fed it. Here is an example of a
> > > > > distance matrix:
> > > > >
> > > > > mat0 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7
> _ 9 _
> > > > >
> > > > >
> > > > > Oh, and before I forget, don't feed it matrices of non-connected
> > > graphs, I
> > > > > think it will infinitely loop. I need to fix that.
> > > > >
> > > > >
> > > > > I understand that it would have been better to use Sparse arrays,
> if
> > > the
> > > > > algorithm is intended to scale up to large graphs, but I haven't
> got
> > > there
> > > > > yet.
> > > > >
> > > > >
> > > > > For now, I would appreciate any comments for improvement,
> criticisms
> > > and
> > > > > explanations of why I am doing things wrong. A code review, I
> suppose.
> > > > >
> > > > >
> > > > > I was surprised how difficult it was to write this, given that J
> is a
> > > > > matrix oriented language and graphs can be comfortably represented
> as
> > > > > matrices, so I am assuming I mad elife difficult for myself
> somewhere.
> > > > >
> > > > >
> > > > > Anyway, thanks,
> > > > > Jon
> > > > >
> > > > >
> > > > >
> ----------------------------------------------------------------------
> > > > > 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
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
