Быстрая сортировка в JavaScript
Jan. 8th, 2007 06:50 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kostikНе секрет, что спрос на приложения c приставкой “AJAX” постоянно растет. Волей-неволей приходится делать некоторые вещи неприспособленными для этого инструментами: характерным примером является Internet Explorer – программа, однозначно неприспособленная для выполнения кода, соответствующего стандарту и здравому смыслу. С одной из его проблем мне пришлось столкнуться: мне понадобилось отсортировать по заданному полю массив объектов. Выяснилось, что сортировка в IE работает в 100 раз медленнее, чем в FireFox. В результате было найдено решение, которое позволяет сортировать примерно в 6 раз быстрее, чем это делает Internet Explorer, ниже есть ссылка на библиотеку, которая реализует этот метод.
Проблема
Тривиальное
// Object а содержит 15000 элементов
a.sort(function(a, b){return b.item – a.item;})
заставило IE задуматься на 40(!) секунд (15000 взято в качестве теста, реальный массив, конечно, меньше). (FireFox выполнял тот же за 422ms, примерно в 100 раз быстрее!) Реализация сортировки на стороне сервера потребовала бы изменить много кода, так как поле и направление сортировки выбирались пользователем произвольно; это была проблема.
Решение
После недолгих поисков я обнаружил отличную статью Russel Lindsay: “Faster Javascript sorting”. Он использует очень простую вещь: переписать метод toString() для обращения к свойству объекта, превратить числа в строки ([1, 2, 10] в [’01’,’02’,’10’]) и использовать sort() без параметров для ускорения поиска. Вот результаты тестов:
Internet Explorer
41516ms – sort(function(a, b){return b.item - a.item;})
7031ms - sort() для массива, где числа конвертированы в строки
7047ms – sort() и reverse() для массива, где числа конвертированы в строки
FireFox
438ms – sort(function(a, b){return b.item - a.item;})
891ms - sort() для массива, где числа конвертированы в строки
954ms – sort() и reverse() для массива, где числа конвертированы в строки
Таким образом, фокус с дополнением чисел нолями до строк дает выигрыш примерно в 6 раз при сортировке в Internet Explorer, и проигрыш всего вдвое при сортировке в FF, что позволяет использовать код в обоих браузерах.
Russel Lindsay использует маску фиксированного размера, то есть массив ([1, 2, 10] превращается не в [01, 02, 10], а в [’00000000001’,’ 00000000002’,’ 00000000010’]), это ужасно по многим причинам, и память – не последняя из них. Так что я написал маленькую библиотеку на основе его кода, она расширяет Array() методами Array.sortIntAsc(property) и Array.sortIntDesc(property) для сортировки по числовому полю property, и методами Array.sortAsc(property) и Array.sortDesc(property) для сортировки по строковому полю property.
Пример
[js] var team = [
{name:'Bill', age:25},
{name:'John', age:21},
{name:'Ann', age:20}
];
alert([team[0].name,team[1].name,team[2].name]);
// Bill, John, Ann
team.sortIntAsc(‘age’);
alert([team[0].name,team[1].name,team[2].name]);
// Ann, John, Bill
team.sortAsc(‘name’);
alert([team[0].name,team[1].name,team[2].name]);
// Ann, Bill, John
[/js]
Мои 5 копеек
Этот метод, мне кажется, неплохое решение конкретной проблемы. Но это так же прекрасная иллюстрация: лучший способ сделать что-то с данными в Internet Explorer – это не делать совсем, то есть организовать модель так, что бы вся обработка данных (включая сортировку) осталась на стороне сервера. Иначе потом, когда IE будет отвратительно справляться с очевидными задачами, придется потратить немало сил на обход проблемы.
