Raul wrote:
I think rmcol2 scans the input five times:
But that's a hurried count, and I may be mistaken.
You're either mistaken or you misunderstood me. By "scan" I did not
mean "query", I meant "visits each item" (i.e. performs an O(n)
operation).
Everything except ;: in my solution is calculating the LHA to ;: ,
and is independent of the size of the input (i.e. is an O(1) operation).
To break it down:
rmcol2 =: FSM^:(1 < #)
Here, we're asking at most two questions of the input. The first is
an O(1) operation:
1 < #
The second, if it's asked, is:
FSM =. ;:~ fsm (,<) ijrd
Which also only asks two questions of the input. The first is:
fsm (,<) ijrd
which is a N V V train, so only the rightmost verb is dependent on
the input; and it is defined as:
ijrd =. 1 , 0 , 1 ,~ t f.@:{.
which again only contains a single verb (the rightmost) which is
dependent upon the input:
=&(10{a.)@:{.
but that only looks at the first item of the input, it is O(1).
AFAICT, the only O(n) operation ("scan") is ;: .
-Dan
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
