Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

JavaScript: BitMask Sorters

Last updated at Posted at 2025-01-19

BitMask Sortersはべらぼうに高速で、複数の整列関数を状況に応じて使い分ける事になります。現時点では昇順整列のみ実装されています。
本家に組み込み関数との速度比較の表が掲載中。

sortInt() は、-2^31 ... 2^31-1 の範囲の負の整数と正の整数を整列できます。
引数はArrayInt8ArrayInt16ArrayInt32ArrayUint8ArrayUint16Arrayのいずれかです。
Float32ArrayFloat64ArrayUint32Array の場合、-2^31 ~ 2^31-1 の範囲の全整数が限定的に対応。
BigInt64 または BigInt64Array は未対応。

sortNumber() は、負と正の IIEE 754 64 bit数値を整列できます。
引数はArrayFloat32ArrayFloat64ArrayInt8ArrayInt16ArrayInt32ArrayUint8ArrayUint16ArrayUint32Arrayのいずれかです。
BigInt64BigInt64Array は未対応。

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);

ちなみに他の言語にも移植されています(JavaC#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>
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?