Isn't this a fair timing which shows that <./ is fastest? I still think
/:~#:A is awesome!
A=:?1000000$10000000
10 timer '{.#./:~#:A'
0.861233
10 timer '{./:~A'
0.152205
10 timer '<./A'
0.00360548
{.#./:~#:A
7
{./:~A
7
<./A
7
Linda
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Linda Alvord
Sent: Thursday, March 06, 2014 10:55 PM
To: [email protected]
Subject: Re: [Jprogramming] a good bar bet!
You warned me that dyadic /: was spectacular!
Linda
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Roger Hui
Sent: Thursday, March 06, 2014 10:39 PM
To: Programming forum
Subject: Re: [Jprogramming] a good bar bet!
Kind of, except I don't think you need to convert to bits and then convert
back.
It boggles my mind that taking the first element of sort to find the
minimum is competitive with the conventional coding for finding the minimum:
x=: a.{~1e7 ?@$ 256
y=: 1e7 ?@$ 2e9
timer=: 6!:2
10 timer '{./:~x'
0.0134736
10 timer '<./y'
0.0126129
I can not do a direct comparison in J because J doesn't have 1-byte
integers. In Dyalog APL, which does have 1-byte integers, the times
are 0.0124262
for the conventional coding and 0.0104232 for the first element of the
sort. Unbelievable.
On Thu, Mar 6, 2014 at 6:45 PM, Linda Alvord <[email protected]>wrote:
> Is this considered fair?
>
> ]A=:?20$1000
> 951 524 574 923 841 986 242 790 695 936 140 901 900 366 33 309 244 327 817
> 680
>
> f=: 13 :'{.#.(#:y)/:#:y'
> f
> [: {. [: #. #: /: #:
>
> f A
> 33
>
> Linda
>
> -----Original Message-----
> From: [email protected]
> [mailto:[email protected]] On Behalf Of Roger Hui
> Sent: Thursday, March 06, 2014 8:50 PM
> To: Programming forum
> Subject: Re: [Jprogramming] a good bar bet!
>
> You are not guaranteed sortedness, but nobody promised that it'd be
sorted.
>
>
> On Thu, Mar 6, 2014 at 5:42 PM, Yike Lu <[email protected]> wrote:
>
> > Problem with the hash table is how do you guarantee sortedness when you
> > spit the result back out?
> > On Mar 6, 2014 6:49 PM, "Roger Hui" <[email protected]> wrote:
> >
> > > Well, if you use a hash table it'd be O(1) expected time to read and
> > write.
> > > The method I know is O(1) worst case time to read and write.
> > >
> > >
> > > On Thu, Mar 6, 2014 at 2:54 PM, Yike Lu <[email protected]> wrote:
> > >
> > > > Hmm, maybe not. It has to basically be able to insert ordered in
> > constant
> > > > time. Everything I remember seems to be log time for one or the
> other.
> > > >
> > > > I'm starting to lean towards a multi-pass / multi-array solution.
> > > >
> > > >
> > > > On Thu, Mar 6, 2014 at 4:42 PM, Roger Hui <[email protected]
> >
> > > > wrote:
> > > >
> > > > > The method I know offers O(1) time to read and write. Can your
> > > > dictionary
> > > > > do the same? (And I think we are talking about _how_ you
implement
> a
> > > > > dictionary.)
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On Thu, Mar 6, 2014 at 2:34 PM, Yike Lu <[email protected]>
> > wrote:
> > > > >
> > > > > > Using a dictionary is another way.
> > > > > >
> > > > > >
> > > > > > On Thu, Mar 6, 2014 at 3:30 PM, Roger Hui <
> > [email protected]
> > > >
> > > > > > wrote:
> > > > > >
> > > > > > > Yes, that's the cost. The trick is to avoid initializing
count
> > > > > > altogether,
> > > > > > > because for this subproblem M is much greater than n. The
> answer
> > > is
> > > > > > > algorithmic and not a matter of using this or that C
operation.
> > > > > > >
> > > > > > > Recently I had occasion to use the trick for M=65536 and n
> about
> > > > 5000.
> > > > > > As
> > > > > > > originally posed, I think the intention was that M would be
> > > zillions.
> > > > > > >
> > > > > >
> > > ----------------------------------------------------------------------
> > > > > > 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
>
> ----------------------------------------------------------------------
> 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
