> DO(p, DO(yv[j], *v++=j;); yv[j]=0; ++j;); I wonder why I set yv[j] to 0? I see it's there in the source but it shouldn't be necessary.
On Wed, Mar 5, 2014 at 2:32 PM, Joe Bogner <[email protected]> wrote: > Roger, thanks for the explanation. I was just getting to that point in > the C code. > > No wonder I couldn't figure it out at first. I was expecting to see a > sort algorithm. The C code is remarkably clear once the intent is > known. I had to step through it to visualize what it was doing. > > Count up the occurrences of each character > > yv[256]; > ... > DO(n, ++yv[*wv++];); > > .. > DO(p, DO(yv[j], *v++=j;); yv[j]=0; ++j;); > > For each occurrence of the character, add it to the output array > > > > On Wed, Mar 5, 2014 at 5:19 PM, Roger Hui <[email protected]> > 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
