> Suppose x is a vector of bits (such as they have in APL). > How do you sort x?
Yes, the algorithmically interesting aspect is m=:+/x, because /:~x ←→ ((m-~#x),m)#0 1. +/x for bit vector x has an interesting history, celebrated in story and song. See http://www.jsoftware.com/jwiki/Essays/Sum_of_a_Bit_Array and the links therein. The essay needs to be updated because nowadays the fastest way in C is: I4 *w=(I4*)x; q=n/32; for(i=sum=0;i<q;++i)sum+=popcnt(*w++); // the case where n is not a multiple of 32 is // left as an exercise for the reader where popcnt <https://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT> is a machine instruction available in SSE4 and the instruction set of other CPUs. On Thu, Mar 6, 2014 at 6:27 AM, David Lambert <b49p23t...@stny.rr.com>wrote: > NB. In c I'd use an algorithm such as > > BS =: 8 NB. block size > BLOCK =: 2^BS > > NB. convert to blocks with padding > BLOCKED_DATA =: BS (#.\~ -)~ BINARY_DATA > > count_bits =: +/"1@:#: > assert 0 1 5-:count_bits 2b0 2b1000 2b110010010100 > > NB. crucial idea, use known time for bit counting > COUNTS =: ([: count_bits i.) BLOCK > > HIGHS =: BLOCKED_DATA ([: +/ {) COUNTS > > > > NB. Maybe we're just looking for > > HIGHS =: +/BINARY_DATA > LOWS =: (HIGHS -~ #) BINARY_DATA > SORTED_BINARY_DATA =: (LOWS , HIGHS) # 0 1 > > > On 03/06/2014 07:00 AM, programming-requ...@forums.jsoftware.com wrote: > >> Date: Wed, 5 Mar 2014 20:52:35 -0800 >> From: Roger Hui<rogerhui.can...@gmail.com> >> To: Programming forum<programm...@jsoftware.com> >> >> Subject: Re: [Jprogramming] a good bar bet! >> Message-ID: >> <CAMZ_i_BYHHGPQkvMbufbfx3g9292SC2XvHZk >> qjcovhhwbdi...@mail.gmail.com> >> Content-Type: text/plain; charset=UTF-8 >> >> >> How about an extreme version of the sort problem. Suppose x is a vector >> of >> bits (such as they have in APL). How do you sort x? >> >> This would have been one way to solve the sorting small integers problem: >> figure out how to sort 0-1 vectors and then work your way up from that. I >> once posed the 88 Hats >> Problem<http://www.jsoftware.com/jwiki/Essays/88_Hats>to a very smart >> >> and very persistent intern. He solved it by generalizing a >> solution to the 2 Hats problem. >> > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm