読者です 読者をやめる 読者になる 読者になる

doubleの配列をバケットソートする

Array.sortよりも少しだけだけど高速に動作したりした!やった!
※体感には個人差環境差があります

IEEE754の仕様により、double値をそのままlong値にキャストすると、正負それぞれが正しい順序を保つ、という性質を利用しています。

また、バケットソートというのは嘘で正確にはラディックスソート(基数ソート)です。

public class DoubleSort {
    public static void sort(double[] ary) {
        int[] idx;
        int sum;
        long[] a1 = new long[ary.length];
        long[] a2 = new long[ary.length];
        long[] tmp;
        for(int i = 0; i < ary.length; i++) {
            a1[i] = Double.doubleToRawLongBits(ary[i]);
            a1[i] ^= (-(a1[i]>>>63)&0x7fffffffffffffffL);
            a1[i] ^= 1L<<63;
        }
        for(int d=0;d<64;d+=8) {
            idx = new int[256];
            for(int i = 0; i < ary.length; i++) {
                idx[(int)(a1[i]>>>d)&255]++;
            }
            sum=0;for(int i = 0; i < 256; i++){int j=sum+idx[i];idx[i]=sum;sum=j;}
            for(int i = 0; i < ary.length; i++) a2[idx[(int)(a1[i]>>>d)&255]++]=a1[i];
            tmp=a2;a2=a1;a1=tmp;
        }
        for(int i = 0; i < ary.length; i++) {
            a1[i] ^= 1L<<63;
            a1[i] ^= (-(a1[i]>>>63)&0x7fffffffffffffffL);
            ary[i] = Double.longBitsToDouble(a1[i]);
        }
    }
    public static void main(String[] args) {
        double[] ary1 = new double[10000001];
        double[] ary2 = new double[ary1.length];
        for(int i = 0; i < ary1.length; i++) {
            ary1[i] = ary2[i] = Math.random();
        }
        long st,en;
        st = System.nanoTime();
        sort(ary1);
        en = System.nanoTime();
        System.out.println(en-st);
        System.out.println(ary1[(ary1.length+1)/2]);

        st = System.nanoTime();
        java.util.Arrays.sort(ary2);
        en = System.nanoTime();
        System.out.println(en-st);
        System.out.println(ary2[(ary1.length+1)/2]);
    }
}