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
