> 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

Reply via email to