Yeah, it's N log N only if the domain is truly infinite (arbitrary
precision). Everything else you can use radix with O(N b) where b is number
of bits.
On Wed, Mar 5, 2014 at 4:41 PM, Yike Lu <yikelu.h...@gmail.com> wrote:
> Roger, why is index lookup so slow in the g2 case (see my message
> earlier)? Are you really saying that bounds checking makes it so that the
> lookup is only as fast as the sort?
>
>
> On Wed, Mar 5, 2014 at 4:35 PM, Roger Hui <rogerhui.can...@gmail.com>wrote:
>
>> > I4 count[M];
>> > memset(count,0x00,sizeof(count));
>> > for(i=0;i<n;++i)count[*x++]=1;
>>
>> More typos:
>>
>> for(i=0;i<n;++i)count[*x++]++;
>>
>>
>>
>>
>> On Wed, Mar 5, 2014 at 2:19 PM, Roger Hui <rogerhui.can...@gmail.com>
>> 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
