Решаем вопрос сортировки в JavaScript раз и навсегда

K

Kate

Administrator
Команда форума

Вступление​

Многим JavaScript разработчикам доводилось сортировать данные на стороне клиента. К сожалению, существующие библиотеки имеют мелкие недостатки. Но эти недостатки складываются, и ограничивают то как программисты думают о сортировке. Чтобы преодолеть эти ограничения, давайте рассмотрим сортировку в разных языках. Вооруженные этими знаниями, мы сможем выбрать наиболее удобный и строгий интерфейс.

С чего все началось​

В один прекрасный летний день, на проекте с AngularJS мне поручили добавить функцию сортировки в таблицу. При этом критериев для сортировки может быть сразу несколько, и направление по каждому критерию может быть независимым.
Список требований:
  • использовать несколько выражений как ключ для сортировки
  • возможность указать направление сортировки независимо по каждому из ключей
  • возможность сортировать строки без учета регистра, и с учетом локали
  • устойчивость сортировки
Что нам предлагает AngularJS для сортировки? документация по filter:eek:rderBy
{{ orderBy_expression | orderBy : expression : reverse : comparator }}
$filter('orderBy')(collection, expression, reverse, comparator)
Example:
<tr ng-repeat="friend in friends | orderBy:'-age'">...</tr>
У меня возникло несколько замечаний по поводу этого фильтра. Для начала, знак - в этом примере не может быть математической операцией, потому что есть значения для которых это бессмысленная операция, например строки. В документации говорится что это префикс, который указывает направление сортировки. Если продолжить разбор, что это вообще за выражение? Это, вроде как, похоже на JS, но в то же время не очень. Это синтаксис выражений для AngularJS, который так же опасен как eval, но при этом имеет свои ограничения. То что этот синтаксис исключителен для AngularJS значит что эти знания невозможно перенести на другие проекты на JS. Кроме того, нельзя использовать TypeScript для проверки этих выражений. expression кроме того может принимать не только строку, но и функцию, которая возвращает ключ для сортировки. Но если указывать функцию, то направление сортировки указать нельзя и теряется гибкость. Так же можно указать несколько критериев сортировки, если задать массив из строк или функций.
Идем дальше, направление сортировки так же можно поменять вторым параметром — reverse. Но возникает проблема! Если указывать несколько критериев сортировки с помощью функций, то нельзя указать направление индивидуально для каждого критерия. Если же указывать направление сортировки в каждом критерии индивидуально, то этот параметр лишний.
Теперь посмотрим на третий параметр — comparator, который позволяет задать особый способ сравнения элементов. Но при этом если было указано несколько критериев сортировки, то один и тот же comparator будет использоваться для каждого критерия. В результате localeSensitiveComparator будет использоваться для сортировки чисел.
И спрашивается, какая мне польза использовать интерфейс который сам с собой не дружит в трех местах, несовместим с TypeScript и его можно использовать исключительно в богом позабытом фреймворке? В мире JavaScript таких примеров, к сожалению, полным-полно.

lodash​

Посмотрим на библиотеку lodash, В ней есть функция _.sortBy, которая позволяет сортировать массив по ключу.
var users = [
{ 'user': 'fred', 'age': 48 },
{ 'user': 'barney', 'age': 36 },
{ 'user': 'fred', 'age': 40 },
{ 'user': 'barney', 'age': 34 }
];

_.sortBy(users, [(o) => o.user]);
// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]]

_.sortBy(users, ['user', 'age']);
// => objects for [['barney', 34], ['barney', 36], ['fred', 40], ['fred', 48]]
Хм, эта функция не позволяет указывать направление сортировки, почему так? Из-за этого я хотел сразу отбросить lodash, но потом увидел _.orderBy.
This method is like _.sortBy except that it allows specifying the sort orders of the iteratees to sort by.
Нажмите для раскрытия...
Добавление опционального параметра не должно ломать обратную совместимость, поэтому мне совсем непонятно почему это сделали отдельной функцией. Посмотрим на его использование:
// Sort by `user` in ascending order and by `age` in descending order.
_.orderBy(users, ['user', 'age'], ['asc', 'desc']);
// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]]
И сразу же возникает замечание — поскольку направление сортировки указывается отдельно от самого критерия, не очевидно в какую сторону он будет сортироваться. Это приведет к тому, что удаление или добавление критериев сортировки может рассинхронизовать эти два массива, и может привести к неожиданным последствиям.
В целом, _.orderBy это терпимый метод сортировки.

Array#sort​

Если же мы хотим использовать только стандартную библиотеку JavaScript, у Array нам доступен метод sort. В этом методе можно указать функцию для сравнения элементов. Сам по себе этот интерфейс для сортировки позволяет указать любой возможный критерий для сортировки. Правда он не так удобен для использования как сортировка по ключу, и есть довольно много подводных камней. Самый большой подводный камень, с моей точки зрения, — к этой функции есть очень строгое требование линейно упорядоченного множества. Это требование очень просто нарушить. В прошлом, несоблюдение этих требований в некоторых браузерах приводило к бесконечным циклам и крахам.
items.sort(function(a, b) {
if (b.salary < a.salary) {
return -1;
}
if (b.salary > a.salary) {
return 1;
}
if (a.id < b.id) {
return -1;
}
if (a.id > b.id) {
return 1;
}

return 0;
});
// Для сравнения, эквивалентный код с использованием `lodash`
// намного короче и его проще читать:
lodash.orderBy(items, ['salary', 'id'], ['desc', 'asc']);
Когда критериев для сортировки будет больше, то разница в удобстве будет еще больше, что приведет повторению кода. Отсутствие удобства и громоздкость обычно приводит к тому, что в код закрадываются трудно уловимые ошибки.
Если же мы хотим примеры адекватных интерфейсов, нужно смотреть в сторону других языков.

SQL / SEQUEL​

Стоит начать с того что данные лучше всего нужно сортировать на стороне сервера, и отображать на клиенте как есть, без перестановок. Если можно убрать сортировку на клиенте, поздравляю, проблема решена! Но этот пост не о таких ситуациях, поэтому попробуем позаимствовать опыт SQL.
Как ни как, сортировка это часть языка SQL с 1976 года, и с его помощью люди давно сортируют данные налево и направо. Кому, как не пользователям реляционных баз данных, приходится больше всего сортировать данные по сложным критериям?
SELECT EMPNO,NAME,SAL
FROM EMP
WHERE DNO 50
ORDER BY EMPNO
SQL позволяет указывать несколько критериев сортировки, а так же независимо указывать направление сортировки по разным критериям:
SELECT EMPNO,NAME,SAL
FROM EMP
ORDER BY SAL DESC, EMPNO ASC
Вот к такому нужно стремиться. К сожалению, SQL это отдельный язык и без специального синтаксиса нет возможности внедрить это напрямую.

Haskell и Rust​

Haskell и Rust предоставляют довольно элегантные методы для сортировки по ключу:
Haskell sortOn:
import Data.Ord (Down)
import Data.Sort (sortOn)
sortOn (\employee -> (Down (salary employee), employee_id employee)) employees
Rust slice::sort_by_key:
use std::cmp::{Reverse};
slice.sort_by_key(|employee| (Reverse(employee.salary), employee.id))
Здесь сортировка по нескольким критериям достигается за счет лексикографического порядка кортежей, а сортировка по убыванию — за счет оберточных типов (newtype) Down и Reverse, которые инвертирует порядок сортировки своего содержания. Это очень простой для использования интерфейс, и он полностью совместим со всеми требованиями.

Python​

В Python у списков есть встроенный метод list.sort и глобальный метод sorted, в котором можно указать критерий сортировки через именованный аргумент key.
Ранее эти методы так же принимали аргумент cmp, но его убрали потому что он не нужен.
sorted(employees, key=lambda employee: (employee.salary, employee.id))
Python, как Haskell и Rust, здесь использует кортеж для сортировки по нескольким критериям, но нельзя указывать направление сортировки отдельно для каждого критерия. К счастью, это легко исправить, создав клас-обертку для обратной сортировки. Это упростит метод сортировки, убрав один аргумент, и одновременно расширит возможности сортировки.
from ord_reverse import Reverse
sorted(employees, key=lambda employee: (Reverse(employee.salary), employee.id))

Java и C#​

В Java метод Arrays.sort принимает Comparator (который почти состоит одной функции сравнения двух элементов). Но Comparator так же позволяет строить компараторы, добавляя новые критерии сравнения, используя метод thenComparing. Можно обратить направление сортировки используя метод reversed.
Comparator<Employee> comparator =
Comparator.comparing(Employee.getSalary).reversed()
.thenComparing(Employee.getId);
Arrays.sort(array, comparator);

Здесь есть небольшой недостаток — нет простого способа указать обратное направление сортировки для отдельного критерия. Давайте попробуем написать компаратор вида ORDER BY SALARY ASC, ID DESC:
// Вариант 1, создавать два компаратора, и складывать их
Comparator<Employee> comparator =
Comparator.comparing(Employee.getSalary)
.thenComparing(Comparator.comparing(Employee.getId).reversed());
// Вариант 2, инвертирует компаратор дважды. Таким образом первый компаратор
// будет использовать прямое направиление сортировки.
Comparator<Employee> comparator =
Comparator.comparing(Employee.getSalary).reversed()
.thenComparing(Employee.getId).reversed();

Если не учитывать LINQ Query, который есть прямым наследником SQL, в C# для сортировки используется Enumerable.OrderBy и Enumerable.OrderByDescending, а так же Enumerable.ThenBy и Enumerable.ThenByDescending для добавления новых критериев сортировки.
IEnumerable<Employee> query =
employees
.OrderByDescending(employee => employee.Salary)
.ThenBy(employee => employee.Id);

По сравнению с Java здесь легче указать обратную сортировку для индивидуальных ключей. Но есть и недостатки — не очевидно когда именно будет происходить сортировка, и слишком множатся методы: IEnumerable — 4 метода, по сравнению с 1 в Haskell/Rust/Python. Количество методов в C# можно было бы свести к двум, используя простой класс для инверсии сравнения.
В целом, как Java, так и C# удовлетворяют требования сортировки. К сожалению, оба языка используют более громоздкий подход с ООП.

C и C++​

C qsort:
#include <stdlib.h>
int cmp_employee(const void *p1, const void *p2)
{
const employee *a = (employee*)p1;
const employee *b = (employee*)p2;

if (b->salary < a->salary) {
return -1;
}
if (b->salary > a->salary) {
return 1;
}

if (a->id < b->id) {
return -1;
}
if (a->id > b->id) {
return 1;
}

return 0;
}

/* ... */
qsort(employees, count, sizeof(employee), cmp_employee);
C++ std::sort:
#include <algorithm>
/* ... */
std::sort(employees.begin(), employees.end(), [](const employee &a, const employee &b) {
if (b->salary < a->salary) {
return true;
}
if (b->salary > a->salary) {
return false;
}
return a->id < b->id;
});
Как в C, так и в C++ сортировать можно только предоставляя функцию сравнения элементов. Только в C сравнение элементов требует возвращать результат сравнения в виде числа (меньше нуля, нуль и больше нуля), а в C++ — проверять что первый элемент меньше второго. В каком-то смысле, так теряется часть информации о сравнении. Скорее всего, это приводит к тому что функция сравнения в C++ вызывается больше чем необходимо.
В C и в C++ нет встроенных способов сортировки по ключу и отсутствуют вспомогательные классы для сборки компараторов из нескольких частей. Array#sort, который мы рассматривали ранее имеет те же недостатки, как и эти две функции.

Выбираем то что лучше подходит​

Из всех перечисленных интерфейсов, наиболее компактная и выразительная сортировка в Haskell и Rust. Можем ли мы перенести ее в JavaScript?
Кортежей в JS нет, но для этих целей можно использовать массивы, так как JS позволяет хранить разные типы в массивах. Оберточных типов нет, но мы можем выбрать нужные типы и определить их форму в функции сравнения. Как это будет выглядеть?
sortBy(array, (employee) => [{ reverse: employee.salary }, employee.id]);

Определяем линейный порядок в JavaScript​

Для того чтобы использовать сортировку по ключу, нужно для начала определиться как сравнивать ключи. Так как в JavaScript нет приемлемого встроенного порядка, нет интерфейсов, Trait-ов и typeclass-ов, то необходимо выбрать достаточное подмножество сравнений для которых будет определен полный порядок, или сравнение будет неуспешным.
Определяем с нуля:
  1. null меньше всех значений. Это альтернативно использованию типа Maybe или Option.
  2. Если типы разные, сравнение бросает ошибку.
  3. Особое значение NaN меньше всех других чисел.
  4. Остальные числа, строки, булеаны и BigInt сравниваются между собой как определено в JavaScript.
  5. Массивы сравниваются используя лексикографический порядок, рекурсивно сравнивая элементы.
  6. Если оба значения имеют форму { reverse: xxx }, то значение xxx будет рекурсивно сравниваться в обратном порядке. Это равносильно использованию Down / Reverse
  7. Если оба значения имеют форму { localeCompare: sss, collator: ccc }, строки sss сравниваются используя коллатор ccc. Коллаторы в обоих значений должны быть равны.
  8. Все остальное бросает ошибку.
Из-за строгости определения, здесь должно быть достаточно ограничений чтобы сравнение удовлетворяло линейному порядку или было неуспешным. Этого подмножества должно хватить для того чтобы решать все возможные задачи сортировки.
Как только мы выбрали интерфейс для сортировки и определили линейный порядок, осталось дело за малым — воплотить это в виде библиотеки: better-cmp

Бонус: почему я не использовал библиотеку X?​

  • orderBy: несмотря на "Inspired by Angular's orderBy filter", эта библиотека довольно хороша. Но я предпочел пойти дальше.
  • thenby: довольно хорошая библиотека, копирует интерфейс Java для комбинации компараторов, но я решил копировать другой язык из-за эргономики.
  • multisort: ಠ_ಠ
    if (/[^\(\r\n]*\([^\(\r\n]*\)$/.test(nextKey)) {
    var indexOfOpenParenthesis = nextKey.indexOf("(");
    var args = JSON.parse("[" + nextKey.slice(indexOfOpenParenthesis+1, -1) + "]");
    nextKey = nextKey.slice(0, indexOfOpenParenthesis);
    }

Заключение​

  • Надеюсь что этот обзор интерфейсов сортировок в разных языках был вам полезен, и что в будущем вам легче будет разобраться как сортировать данные по многим критериям.
  • Довольно странно что для такой распространенной операции как сортировка разные языки используют разные интерфейсы.
  • Ещё более странно странно что в "текущем году" в JavaScript нет широко известной и адекватной сортировки по ключу.
  • Лучшее решение для JavaScript что смог сделать теперь воплощено в виде библиотеки better-cmp, доступной на npm.


Источник статьи: https://habr.com/ru/post/559944/
 
Войдите или зарегистрируйтесь для ответа.
Сверху