webew
Войти » Регистрация
 
JavaScript

Сортировка массивов в JavaScript

9 апреля 2009, 9:09

Задача — разобраться как работает сортировка в JavaScript, насколько она производительна и что с её помощью можно делать.

Метод sort

В JavaScript можно сортировать массивы с помощью метода sort. В качестве единственного необязательного аргумента метод принимает функцию, определяющую правила сортировки. Если sort вызвали без аргументов, то сортировка осуществляется по возрастанию значений элементов. Пример:

// Массив со значениями различных типов
var arr = [0, true, 'Вася', 'Петя', 56, NaN, false, 13, 'Коля'];
// Сортируем
arr.sort();
// Вернет [0,13,56,NaN,false,true,Вася,Коля,Петя]

 

[]

Сортируется массив, в контексте которого вызван метод, так что если вы желаете сохранить исходное состояние — сделайте копию и сортируйте её.

Функции сортировки

Вы можете настраивать сортировку, передавая методу sort специальную функцию. В качестве аргументов функция принимает два значения массива, которые передаст метод sort. Вернуть функция может следующие значения (спасибо за уточнение пользователю alik):

  • положительное (1,2,10), если условие сортировки истинно;
  • отрицательное (-0.1, -3, -20), если условие сортировки ложно;
  • 0, если сравниваемые значения равны.

Пример:

var arr = [1,2,3,4,5,6,7,8,9,10];
// Функции сортировки
function sIncrease(i, ii) { // По возрастанию
    if (i > ii)
        return 1;
    else if (i < ii)
        return -1;
    else
        return 0;
}
function sDecrease(i, ii) { // По убыванию
    if (i > ii)
        return -1;
    else if (i < ii)
        return 1;
    else
        return 0;
}
function sRand() { // Случайная
    return Math.random() > 0.5 ? 1 : -1;
}
arr.sort(sIncrease); // Вернет [1,2,3,4,5,6,7,8,9,10]
arr.sort(sDecrease); // Вернет [10,9,8,7,6,5,4,3,2,1]
arr.sort(sRand); // Вернет случайно отсортированный массив, например [1,10,3,4,8,6,9,2,7,5]
[]

Производительность

На первый взгляд может показаться, что сортировка в JavaScript непроизводительна, и в web-приложениях лучше сортировать данные на server-side. Небольшой эксперимент это опровергает. Будьте осторожны, в циклах на 100.000 элементов браузер может зависнуть!

Сортируем массивы c целочисленными значениями различной длины:

Нет данных

можете зависнуть

Автор, в ходе своих экспериментов на своем PC (Vista, Pentium Dual 2.2Ггц, 2Гб RAM) получил следующие результаты:

1000     10.000      100.000     
IE 7      20-50 ms     200-650 ms      завис     
FF 3      1-2 ms      12-30 ms      150-400 ms     
Safari 3      2-30 ms *      30-400 ms *      350-5000 ms *     
Opera 9.5      2-5 ms     40-75 ms     500-1000 ms     
Chrome 1.0      1-2 ms     10-30 ms      100-300ms     

* В Safari случайная сортировка занимала ровно на порядок больше времени, чем сортировка по возрастанию/убыванию.

За исключением Internet Explorer, который не смог переварить массив на 100.000 элементов, сортировка показала себя вполне производительной операцией.

Многомерный массив

При необходимости можно усложнить функции сортировки. Например, чтобы сортировать многомерные массивы (массивы массивов), или массивы объектов, или любой другой массив с нетривиальными значениями. Пример:

var multi = [
    ['Nikolay', 34],
    ['Andrey', 23],
    ['Stanislav', 20]
];
// Функции сортировки
function sName(i, ii) { // По имени (возрастание)
    if (i[0] > ii[0])
        return 1;
    else if (i[0] < ii[0])
        return -1;
    else
        return 0;
}
function sAge(i, ii) { // По возрасту (возрастание)
    if (i[1] > ii[1])
        return 1;
    else if (i[1] < ii[1])
        return -1;
    else
        return 0;
}
multi.sort(sName); // Вернет [[Andrey,23],[Nikolay,34],[Stanislav,20]]
multi.sort(sAge); // Вернет  [[Stanislav,20],[Andrey,23],[Nikolay,34]]
[]

Отдельная страница со всеми примерами.

Итого мы

  • Разобрали как работает сортировка в JavaScript.
  • Научились писать функции сортировки.
  • Осознали что сортировка достаточно производительна, чтобы использовать её в своих приложениях на стороне клиента, снизив нагрузку на сервер.

Если вам есть что спросить или добавить — прошу в комменты.


// Все права на статью Сортировка массивов в JavaScript принадлежат сайту 2007.fastcoder.ru
Добавить комментарий
Отображение комментариев: Древовидное | Плоское
NO USERPIC

rgbeast

Предлагаю более устойчивый способ сортировки по рандому. Сначала создать массив, содержащий пары (rand(), $value), а затем отсортировать этот массив. Результат сортировки будет однозначиным и быстрым, а случайные числа генерируются единожды.
09.04.2009, 09:43
Ответить

bur

Почему бы и нет.
10.04.2009, 07:03
Ответить

bur

Сразу после сравнения обоих способов дополню статью.
10.04.2009, 07:14
Ответить

alik

Про функцию сортировки Вы не совсем правы.

Она может возвращать не обязательно только -1, 0 или 1.

Согласно спецификации EcmaScript, эта функция принимающей два аргумента x и y, и возвращает:

* при x < y: отрицательное значение (т.е. не только -1, но и, например: -0.1, -100 или -Math.PI);

* при x = y: ноль;

* при x > y: положительное значение (т.е. опять-же, не только 1, но и 0.1, 100 или Math.PI);

Вот цитата из оригинала спецификации: «function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y».

Этот факт в некоторых случаях помогает сильно сократить код.

Например, вашу функцию обратной сортировки:

function sDecrease(i, ii) { // По убыванию
    if (i > ii)
        return -1;
    else if (i < ii)
        return 1;
    else
        return 0;
}

можно сократить до:

function sDecrease(i, ii) { // По убыванию
    return (ii - i);
}


Если Вы согласны, поправьте пожалуйста.


С уважением,
Алик Кириллович
alik@alik.su
http://feeds.feedburner.com/alik-kirillovich
09.04.2009, 21:16
Ответить

bur

Спасибо за уточнение по возвращаемому значению функции сравнения! Внес поправку в статью.
Насчет изменения функция сортировки из примеров я с вами не соглашусь. Ваша функция:
- не так очевидна (пример должен быть максимально доступен для понимания),
- не будет работать, к примеру, со строковыми значениями ('str1' - 'str2' вернет NaN).
10.04.2009, 07:13
Ответить
NO USERPIC

rgbeast

Функцию можно сократить, написав в стиле C. И работать должна быстрее

function sDecrease(i, ii) { // По убыванию
  return (i > ii)?-1:( (i < ii)?1:0 );
}
10.04.2009, 07:22
Ответить

bur

Можно, однако:
1) такая реализация не так очевидна (пример должен быть максимально доступен для понимания),
2) использование тернарного условного оператора не должно дать НИКАКОГО выйгрыша в производительности.
Хотя такая запись лично мне ближе, потому что компактнее :-)
10.04.2009, 07:26
Ответить
NO USERPIC

rgbeast

Это все-таки оператор из стандарта языка, так что можно считать его очевидным. А насчет производительности должен быть выйгрыш, так как использование оператора намного более простая для интерпретатора операция, чем разветвление потока исполнения. Это можно протестить.
10.04.2009, 07:39
Ответить

1234ru

Цитата:
использование оператора намного более простая для интерпретатора операция, чем разветвление потока исполнения. Это можно протестить.

Это в любом языке так?

Например. в PHP код

$n = 1000000;

$start = microtime(1);
for ($i = 1; $i < $n; $i++) {
    if ($i%2 == 1) $d = 1;
    else $d = 0;
}
$t1 = round(microtime(1) - $start, 3);

$start = microtime(1);
for ($i = 1; $i < $n; $i++) {
    $e = ($i%2 == 1) ? 1 : 0;
}
$t2 = round(microtime(1) - $start, 3);

echo "IF: $t1, ОПЕРАТОР: $t2";


даёт приблизительно одинаковые результаты и для if, и для оператора (даже для if немного поменьше).
То, что не убивает нас, делает нас инвалидами.
24.04.2009, 20:59
Ответить
NO USERPIC

rgbeast

PHP интерпретируемый язык, в данном случае время уходит на синтаксический разбор, так что сравнение некорректно
25.04.2009, 11:34
Ответить

1234ru

А что такое "интерпретируемый"?
И какой Javascript? Не интерпретируемый?
То, что не убивает нас, делает нас инвалидами.
25.04.2009, 19:20
Ответить
NO USERPIC

rgbeast

Да, Javascript тоже интерпретируемый. Но сравнение все равно некорректно, так как будет зависеть от интерпретатора.
25.04.2009, 19:45
Ответить

stopkran

Наверное, абстрактный массив FF сортирует быстрее. Но при конкретной работе с DOM у меня получилось, что FF существенно хуже ИЕ. Правда, там не сортировка, а назначение элементам свойств style.display (отбор, фильтрация списка): словарь автозапчастей
19.06.2009, 10:03
Ответить
Добавить комментарий
Отображение комментариев: Древовидное | Плоское
© 2008—2017 webew.ru, связаться: x собака webew.ru
Сайт использует Flede и соответствует стандартам WAI-WCAG 1.0 на уровне A.
Rambler's Top100