LoginSignup
3
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?

More than 1 year has passed since last update.

@_tt

javascript: array.sort((a, b) => a - b) にどこまで迫れるか

Last updated at Posted at 2022-07-13

（思いついたら追加していこうかと）

経緯

キャンペーンとのことで参加してみようと
https://qiita.com/official-campaigns/engineer-festa/2022

お題を探してたところ、こちらのソートアルゴリズムの記事を拝見し、
https://qiita.com/fuwasegu/items/0f27a7eee2ec72035855
いっちょあたくしも考えてみっか、と思い立ちまして。

javascript で並べ替えと言えばこれです。

sort.js
source.sort((a, b) => a - b);

ということで、javascript エンジンはどれも、これが最速になるよう実装してそうです。（たぶん）
よって勝つのは難しそうですが、どこまで迫れるか、考えてみます。

条件

・javascript で実装
・Windows 10 Home 21H2 19044.1766 （64 ビット）
・Chrome 103.0.5060.66（Official Build） （64 ビット）
　DevTools の Console にコードを貼り付けて実行
・対象配列は下記4パターン

sourceArray.js
// 1.乱数の範囲：0～8,191、要素数：1万
const source = [...Array(10**4)].map(_ => Math.floor(Math.random()*8192));

// 2.乱数の範囲：0～8,191、要素数：10万
const source = [...Array(10**5)].map(_ => Math.floor(Math.random()*8192));

// 3.乱数の範囲：0～65,535、要素数：10万
const source = [...Array(10**5)].map(_ => Math.floor(Math.random()*65536));

// 4.乱数の範囲：0～65,535、要素数：100万
const source = [...Array(10**6)].map(_ => Math.floor(Math.random()*65536));

結果

※値はミリ秒で、上位3桁に四捨五入

アルゴリズム 配列1 配列2 配列3 配列4 感想
sort((a, b) => a - b) 4.54 48.4 52.6 488 早い上に安定してる
さすが
Min Max 法 92.0 7,820 8,230 - 全然相手にならないですね
Min Max+ 法 18.7 1,250 1,300 - かなり改善もまだ桁が違う
さらに案が必要そう
Min Max++ 法 14.6 182 219 6,830 MinMax+からさらに改善
あともう一歩
Value Index 法 6.41 35.2 69.2 409 え？超えた？

各案の詳細

以下の案すべて、勝手ネーミングです。

1. Min Max 法

配列から最大値と最小値を探し、
それを結果配列に追加しつつ、元配列から削除、
これを繰り返します。
image.png

minMaxSort.js
const high = [];
const low = [];
while(source.length > 1) {
	let max = {value: source[0], index: 0};
	let min = {value: source[0], index: 0};
	for (let i = 1; i < source.length; i++) {
		if (max.value < source[i]) {
			max.value = source[i];
			max.index = i;
		}
		else if (source[i] < min.value) {
			min.value = source[i];
			min.index = i;
		}
	}
	high.unshift(max.value);
	low.push(min.value);
	if (min.index < max.index) {
		source.splice(max.index, 1);	
		source.splice(min.index, 1);		
	}
	else {
		source.splice(min.index, 1);		
		source.splice(max.index, 1);
	}
}
if (source.length) low.push(source[0]);
const result = [...low, ...high];

2. Min Max+ 法

配列の要素を先頭から順に、都度、
・これまでで最大であれば結果配列の末尾に追加
・これまでで最小であれば結果配列の先頭に追加
・最大でも最小でもない場合は、
　最大値と最小値との差の小さい方から順に
　結果配列と比較していき追加すべき index を探します。

minMaxPlusSort.js
const result = [source.shift()];
source.forEach(s => {
	if (result[result.length - 1] <= s) {
		result.push(s);
	}
	else if (s <= result[0]) {
		result.unshift(s);
	}
	else if ((s - result[0]) < (result[result.length - 1] - s)) {
		for (let j = 1; j < result.length; j++) {
			if (s <= result[j]) {
				result.splice(j, 0, s);
				break;
			}
		}
	}
	else {
		for (let j = result.length - 2; 0 <= j; j--) {
			if (result[j] <= s) {
				result.splice(j + 1, 0, s);
				break;
			}
		}
	}
}

3. Min Max++ 法

Min Max+ 法で、最大でも最小でもない場合を置き換えたものです。
最大でも最小でもない場合は、「別の配列」を用意しそこに格納し、
その「別の配列」においても、都度、
・これまでで最大であれば「別の配列」の末尾に追加
・これまでで最小であれば「別の配列」の先頭に追加
・最大でも最小でもない場合は、「さらに別の配列」を用意しそこに格納
これを最後まで繰り返します。
image.png

値の格納された各配列はソート済になるので
各配列の先頭を比較し、最小のものを削除しては結果配列の末尾に追加、
これを最後まで繰り返すとできあがりです。

minMaxPlusPlusSort.js
const temp = [[source.shift()]];
source.forEach(s => {
	let added = false;
	for (let i = 0; i < temp.length; i++) {
		if (temp[i][temp[i].length - 1] <= s) {
			temp[i].push(s);
			added = true;
			break;
		}
		else if (s <= temp[i][0]) {
			temp[i].unshift(s);
			added = true;
			break;
		}
	}
	if (!added) temp.push([s]);
});
const result = [temp[0].shift()];
while (temp.length) {
	let min = {value: temp[0][0], index: 0};
	for (let i = 1; i < temp.length; i++) {
		if (temp[i][0] < min.value) {
			min = {value: temp[i][0], index: i};
		}
	}
	result.push(temp[min.index].shift());
	if (!temp[min.index].length) temp.splice(min.index, 1);
}

4. Value Index 法

ソートアルゴリズムが for (let i = ... を含まないってあり得るんでしょうか。
この案では出てこないです。
まあ、sort() を使わずソートできてるのでよしとしましょうか。
一応、これが現在の自己ベストです。

数値をそのまま結果配列のインデックスにします。
ただ、同値が上書きされていくと、結果配列の要素数が足りなくなるため
結果配列の要素は値ではなく配列にし、値はその要素配列（2次元目の配列）に追加します。
image.png

valueIndexSort.js
let result = [];
source.forEach(v => result[v]
                    ? result[v].push(v)
                    : result[v] = [v]);
result = result.filter(v => v)
               .flat();

※これ、最大値(M)に対して要素数(n)が十分に大きい場合に早くなるようです
　ここ、n/M = ? とかで境界が表せるのか確認したいと思います

全コード

タイマと検算を含む全コードです。
Chrome DevTools Console に貼付 Enter でチェックできます。
（MinMax は遅いのでコメントにしています）

all.js
const source = new class {
	constructor() {
		//this.source = [...Array(10**4)].map(_ => Math.floor(Math.random()*8192));
		  this.source = [...Array(10**5)].map(_ => Math.floor(Math.random()*8192));
		//this.source = [...Array(10**5)].map(_ => Math.floor(Math.random()*65536));
		//this.source = [...Array(10**6)].map(_ => Math.floor(Math.random()*65536));
	}
	get() {
		return JSON.parse(JSON.stringify(this.source));	//deep copy
	}
}();
const defaultSort = new class DefaultSort {
	constructor() {
		this.result = [];
		console.time(DefaultSort.name);
		this.do();
		console.timeEnd(DefaultSort.name);
	}
	do() {
		this.result = source.get().sort((a, b) => a - b);
	}
	validate(name, arr) {
		const isCorrect = this.result.length === arr.length
						&& !this.result.some((s, i) => s !== arr[i]);
		console.assert(isCorrect, name + ' incorrect');		
	}
}();
/*
const _mm = new class MinMax {
	constructor() {
		this.result = [];
		console.time(MinMax.name);
		this.do();
		console.timeEnd(MinMax.name);
		defaultSort.validate(MinMax.name, this.result);
	}
	do() {
		const s = source.get();
		const high = [];
		const low = [];
		while(s.length > 1) {
			let max = {value: s[0], index: 0};
			let min = {value: s[0], index: 0};
			for (let i = 1; i < s.length; i++) {
				if (max.value < s[i]) {
					max = {value: s[i], index: i};
				}
				else if (s[i] < min.value) {
					min = {value: s[i], index: i};
				}
			}
			high.unshift(max.value);
			low.push(min.value);
			if (min.index < max.index) {
				s.splice(max.index, 1);	
				s.splice(min.index, 1);		
			}
			else {
				s.splice(min.index, 1);		
				s.splice(max.index, 1);
			}
		}
		if (s.length) low.push(s[0]);
		this.result = [...low, ...high];	
	}
}();
*/
const _mmp = new class MinMaxPlus {
	constructor() {
		this.result = [];
		console.time(MinMaxPlus.name);
		this.do();
		console.timeEnd(MinMaxPlus.name);
		defaultSort.validate(MinMaxPlus.name, this.result);
	}
	do() {
		const _source = source.get();
		const result = [_source.shift()];
		_source.forEach(s => {
			if (result[result.length - 1] <= s) {
				result.push(s);
			}
			else if (s <= result[0]) {
				result.unshift(s);
			}
			else if ((s - result[0]) < (result[result.length - 1] - s)) {
				for (let j = 1; j < result.length; j++) {
					if (s <= result[j]) {
						result.splice(j, 0, s);
						break;
					}
				}
			}
			else {
				for (let j = result.length - 2; 0 <= j; j--) {
					if (result[j] <= s) {
						result.splice(j + 1, 0, s);
						break;
					}
				}
			}
		});
		this.result = result;
	}
}();
const _mmpp = new class MinMaxPlusPlus {
	constructor() {
		this.result = [];
		console.time(MinMaxPlusPlus.name);
		this.do();
		console.timeEnd(MinMaxPlusPlus.name);
		defaultSort.validate(MinMaxPlusPlus.name, this.result);
	}
	do() {
		const _source = source.get();
		const temp = [[_source.shift()]];
		_source.forEach(s => {
			let added = false;
			for (let i = 0; i < temp.length; i++) {
				if (temp[i][temp[i].length - 1] <= s) {
					temp[i].push(s);
					added = true;
					break;
				}
				else if (s <= temp[i][0]) {
					temp[i].unshift(s);
					added = true;
					break;
				}
			}
			if (!added) temp.push([s]);
		});
		const result = [temp[0].shift()];
		while (temp.length) {
			let min = {value: temp[0][0], index: 0};
			for (let i = 1; i < temp.length; i++) {
				if (temp[i][0] < min.value) {
					min = {value: temp[i][0], index: i};
				}
			}
			result.push(temp[min.index].shift());
			if (!temp[min.index].length) temp.splice(min.index, 1);
		}
		this.result = result;
	}
}();

const _vi = new class ValueIndex {
	constructor() {
		this.result = [];
		console.time(ValueIndex.name);
		this.do();
		console.timeEnd(ValueIndex.name);
		defaultSort.validate(ValueIndex.name, this.result);
	}
	do() {
		const result = [];
		source.get().forEach(v => result[v]
								? result[v].push(v)
								: result[v] = [v]);
		this.result = result.filter(v => v).flat();	
	}
}();
3
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
Sign upLogin
3
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?