CTAPbIu_MABP's BLOG

Возвращаясь к вопросам с собеседований... как отсортировать матрицу по нескольким столбцам сразу. Вопрос, скорее не по javascript, а по теории в общем, но тем не менее меня порадовал.

Будем думать что нам дана матрица 5x25 с буквами ABC. Буков мало, столбцов - тоже, зато строчек много, так удобнее смотреть результат.

var matrix = [];
for(var i=0;i<25;i++){
	matrix.push([]);
	for(var j=0;j<5;j++){
		matrix[i].push(String.fromCharCode(65+Math.random()*3));
	}
}

Теперь представим что у нас крутой язык под названием ява и напишем компоратор для сортировки

matrix.sort(function(a, b){
	var eq0, eq1, eq2; 
	eq0 = a[0] == b[0];
	if (eq0){
		eq1 = a[1] == b[1];
		if (eq1) {
			eq2 = a[2] == b[2];
			if (eq2) {
				return 0;
			} else {
				return a[2] > b[2];
			}
		} else {
			return a[1] > b[1];
		}
	} else {
		return a[0] > b[0];
	}
});

Конечно компоратор, это очень громкое слово, это скорее callback для сортировки. Не смотря на то что по спецификации callback должен возвращать -1, 0, 1 , он прекрасно работает возвращая результат сравнения строк "A" > "B" ;)

Дальше легким движением руки превращаем данный уродливый кусок копипасты (ммм... вкусной пасты) в мега-универсальный фреймворк по компорации матриц любого размера.

function (a, b, d){
	(2 in arguments) || (d = 0);
	return (d in a && d in b) && (a[d] == b[d] ? arguments.callee(a, b, d+1) : a[d] > b[d]) || 0;
}

кто не понял - пропустите...

Еще одно маленькое замечание: этот callback безбожно тупит. На массиве из 250000 элементов [].sort() = ~50мс , а с колбеком [].sort(function(a,b){return a>b;}) тормозит аж 950мс, то есть почти в 20 раз.

Теперь наверное надо показать как это работает?! Ну вы поняли...