BitMask Sortersはべらぼうに高速で、複数の整列関数を状況に応じて使い分ける事になります。現時点では昇順整列のみ実装されています。
本家に組み込み関数との速度比較の表が掲載中。
sortInt()
は、-2^31 ... 2^31-1 の範囲の負の整数と正の整数を整列できます。
引数はArray
、Int8Array
、Int16Array
、Int32Array
、Uint8Array
、Uint16Array
のいずれかです。
Float32Array
、Float64Array
、Uint32Array
の場合、-2^31 ~ 2^31-1 の範囲の全整数が限定的に対応。
BigInt64
または BigInt64Array
は未対応。
sortNumber()
は、負と正の IIEE 754 64 bit数値を整列できます。
引数はArray
、Float32Array
、Float64Array
、Int8Array
、Int16Array
、Int32Array
、Uint8Array
、Uint16Array
、Uint32Array
のいずれかです。
BigInt64
、BigInt64Array
は未対応。
import {sortInt} from "@aldogg/sorter";
import {sortNumber} from "@aldogg/sorter";
sortInt(array);
sortNumber(array)
sortObjectInt
は、-2^31 ~ 2^31-1 の範囲内の負の整数keyと正の整数keyを持つobjectのみを整列できます。
sortObjectNumber
はIEEE 754の数字keyでobjectを整列できます
import {sortObjectInt, sortObjectNumber} from "@aldogg/sorter";
sortObjectInt(array,x=>x.id);
sortObjectNumber(array,x=>x.id);
ちなみに他の言語にも移植されています(Java、C#、C++、Python)
その実体
さて、その実体はと言うと基数整列、鳩の巣整列、quick sortの応用したものです。細かく関数を見て行きましょう。
<script type=module>
function test(A){for(let a=0,b=A.length-1;a<b;)if(A[a]>A[++a])return"bad";return"OK"}
//////// sort integer ////////
console.log("sort integer")
let size=1e6,range=1e4,A=new Uint32Array(size);
for(let a=size;a;)A[--a]=Math.random()*range;
import{aFlagBitSorterInt}from"./a-flag-bit-sorter-int.js";
let B=A.slice(),t=performance.now();
aFlagBitSorterInt(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{radixBitSorterInt}from"./radix-bit-sorter-int.js";
B=A.slice();
t=performance.now();
radixBitSorterInt(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{radixBitSorterNumber}from"./radix-bit-sorter-number.js";
B=A.slice();
t=performance.now();
radixBitSorterNumber(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{quickBitSorterInt}from"./quick-bit-sorter-int.js";
B=A.slice();
t=performance.now();
quickBitSorterInt(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{pCountBitSorterInt}from"./p-count-bit-sorter-int.js";
B=A.slice();
t=performance.now();
pCountBitSorterInt(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{pCountNoMaskSorterInt}from"./p-count-bit-sorter-int.js";
B=A.slice();
t=performance.now();
pCountNoMaskSorterInt(B);
t=performance.now()-t;
console.log(test(B),t,"ms")
B=A.slice();
t=performance.now();
B.sort();
t=performance.now()-t;
console.log("builtin sort",test(B),t,"ms")
//////// sort object ////////
console.log("sort object")
A=Array(size);
for(let a=size;a;)A[--a]={key:Math.random()*range>>>0,item:a};
let comp=a=>a.key;
import{radixBitSorterObjectInt}from"./radix-bit-sorter-object-int.js";
B=A.slice();
t=performance.now();
radixBitSorterObjectInt(B,comp);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{radixBitSorterObjectIntV2}from"./radix-bit-sorter-object-int-v2.js";
B=A.slice();
t=performance.now();
radixBitSorterObjectIntV2(B,comp);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{radixBitSorterObjectNumber}from"./radix-bit-sorter-object-number.js";
B=A.slice();
t=performance.now();
radixBitSorterObjectNumber(B,comp);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{quickBitSorterObjectInt}from"./quick-bit-sorter-object-int.js";
B=A.slice();
t=performance.now();
quickBitSorterObjectInt(B,comp);
t=performance.now()-t;
console.log(test(B),t,"ms")
import{pCountBitSorterObjectInt}from"./p-count-bit-sorter-object-int.js";
B=A.slice();
t=performance.now();
pCountBitSorterObjectInt(B,comp);
t=performance.now()-t;
console.log(test(B),t,"ms")
B=A.slice();
t=performance.now();
B.sort((a,b)=>a.key-b.key);
t=performance.now()-t;
console.log("builtin sort",test(B),t,"ms")
</script>