Right. I do need the break. That's what I get when I post code without
testing it.
On Wed, Mar 5, 2014 at 7:53 PM, Raul Miller <rauldmil...@gmail.com> wrote:
> Won't it give the maximum though, instead of the minimum?
>
> Thanks,
>
> --
> Raul
>
>
>
> On Wed, Mar 5, 2014 at 8:43 PM, Roger Hui <rogerhui.can...@gmail.com>
> wrote:
>
> > Yes, a break or return would be nice. It's still OK without that,
> because
> > it's looping a maximum of M times.
> >
> >
> >
> > On Wed, Mar 5, 2014 at 5:00 PM, Raul Miller <rauldmil...@gmail.com>
> wrote:
> >
> > > You probably want a return or break statement in that second loop?
> > >
> > > Thanks,
> > >
> > > --
> > > Raul
> > >
> > >
> > >
> > > On Wed, Mar 5, 2014 at 7:13 PM, Roger Hui <rogerhui.can...@gmail.com>
> > > wrote:
> > >
> > > > > it avoids any branching in the loop. And no "comparisons".
> > > >
> > > > I1 b[M];
> > > > memset(b,0x00,sizeof(b));
> > > > for(i=0;i<n;++i)b[*x++]=1;
> > > > for(i=0;i<M;++i)if(b[i])min=i;
> > > >
> > > > Well, there is branching and there is comparison, but it's in the M
> > loop
> > > > rather than the n loop. M is small and fixed (65536 for 2-bytes)
> > > whereas n
> > > > can be millions, billions. The J models are:
> > > >
> > > > 1 i.~ 1 x}M$0 NB. minimum
> > > > 1 i:~ 1 x}M$0 NB. maximum
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > On Wed, Mar 5, 2014 at 4:05 PM, Roger Hui <rogerhui.can...@gmail.com
> >
> > > > wrote:
> > > >
> > > > > Zehr gut. It's not just that it's O(n) (the conventional
> > > > if(min>*x)min=*x
> > > > > is also O(n)) but it avoids any branching in the loop. And no
> > > > > "comparisons".
> > > > >
> > > > > Bonus question: Suppose M is really large and the cost of setting
> > > count
> > > > > to 0 is prohibitive. How can you avoid that cost? (Not saying
> it's
> > > > > related to finding the min or the max).
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On Wed, Mar 5, 2014 at 3:27 PM, Peter B. Kessler <
> > > > > peter.b.kess...@oracle.com> wrote:
> > > > >
> > > > >> For the minimum in a small universe, use your "broken" sorting
> code
> > > (:-)
> > > > >>
> > > > >>
> > > > >> I4 count[M];
> > > > >> memset(count,0x00,sizeof(count));
> > > > >> for(i=0;i<n;++i)count[*x++]=1;
> > > > >>
> > > > >> (O(n)) and then look for the first (lowest) 1 in count (also
> O(n)).
> > > > >>
> > > > >> ... peter
> > > > >>
> > > > >>
> > > > >> On 03/05/14 14:19, Roger Hui wrote:
> > > > >>
> > > > >>> Good answers. For /:~x vs. g{x, the explanations are:
> > > > >>>
> > > > >>> - Indexing must check for index error. Sorting does not.
> > > > >>> - Indexing uses random read access over a large chunk of
> memory
> > > > (i.e.
> > > > >>>
> > > > >>> x). Sort does not.
> > > > >>>
> > > > >>> A more detailed explanation: To sort over a small known universe
> > > (and
> > > > >>> characters definitely qualify), you basically compute #/.~x (the
> > > > ordering
> > > > >>> is wrong, but you get the idea). In C:
> > > > >>>
> > > > >>> I4 count[M];
> > > > >>> memset(count,0x00,sizeof(count));
> > > > >>> for(i=0;i<n;++i)count[*x++]=1;
> > > > >>>
> > > > >>>
> > > > >>> This is lightning fast on modern CPUs: sequential read access and
> > no
> > > > >>> branch
> > > > >>> prediction fails. (And the ordering is correct.) Once having
> the
> > > > >>> counts,
> > > > >>> as Henry said, you can do count#a. or in C:
> > > > >>>
> > > > >>> for(i=0;i<M;++i){m=count[j]; for(j=0;j<m;++j)*z++=i;}
> > > > >>>
> > > > >>>
> > > > >>> Also lightning fast with very localized reads.
> > > > >>>
> > > > >>> It's ironic that in school sorting is an application with heavy
> > > > emphasis
> > > > >>> on
> > > > >>> comparisons, counting # of comparisons, etc. In the method
> above,
> > > > there
> > > > >>> is
> > > > >>> not a single comparison involving x. I once told someone that I
> > can
> > > > sort
> > > > >>> 4-byte integers and 8-byte IEEE floats in linear time. He looked
> > at
> > > me
> > > > >>> like I was crazy, presumably remembering from school that sorting
> > was
> > > > >>> PROVEN to take n log n comparisons.
> > > > >>>
> > > > >>> As for why sorting is faster than grading, see
> > > > >>> http://www.jsoftware.com/jwiki/Essays/Sorting_versus_Grading
> > > > >>>
> > > > >>> Now, for those of you who know C (or other scalar language), is
> > > there a
> > > > >>> faster way to find the minimum of a vector of small integers x
> > > (2-byte
> > > > >>> integers, say) than the following:
> > > > >>>
> > > > >>> min=-32768;
> > > > >>> for(i=0;i<n;++i){if(min>*x)min=*x; ++x;}
> > > > >>>
> > > > >>>
> > > > >>> I know an alternative which is 70% faster. No fancy SSE
> > > instructions.
> > > > >>> No
> > > > >>> multicore. No loop unrolling.
> > > > >>>
> > > ----------------------------------------------------------------------
> > > > >>> 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
