Що приховує Array#sort: реверс-інжиніринг підручними засобами

Як вам, можливо, відомо, специфікація мови JavaScript не наказує якоїсь певної реалізації методу sort у масивів. Алгоритм, що перебуває «під капотом», може відрізнятися (і відрізняється) в різних браузерах. Теоретично можна уявити собі ситуацію, коли від того, як саме реалізована сортування масивів в конкретному движку, залежить продуктивність вашого веб-додатки. Прихований текстДуже сильно сумніваюся, що так може статися на практиці, але як людина, який написав свого часу певну кількість курсових і дипломних робіт, я просто не зміг обійтися без секції «застосування в народному господарстві».

Якщо мова йде про браузер з відкритим вихідним кодом, то можна просто відкрити цей код і подивитися, який там використаний алгоритм. Однак існують браузери з закритим вихідним кодом (не будемо показувати пальцем). Що робити в такому випадку?

Оскільки ми на Хабре, я готовий припустити, що деякі читачі вже потягнулися до своїм коханим дизассемблерам, в той час як деякі інші готуються дзвонити своїм друзям з однієї невеликої і нетвердою компанії. Однак сьогодні ми не будемо копатися в машинному коді або використовувати інсайдерську інформацію. Ми будемо дивитися веселі картинки.



Існує можливість дізнатися дещо про реалізацію методу sort прямо всередині скрипта. Вона полягає в тому, що цей метод приймає в якості аргументу компаратор — функцію двох змінних, повертає числове значення, на підставі якого алгоритм сортування робить висновок, який з аргументів більше. Це дозволяє сортувати масиви довільних об'єктів, а не тільки чисел і рядків. Також, що важливо в нашому випадку, це дозволяє дізнатися, які саме елементи масиву і в якому порядку метод sort порівнює між собою. Наприклад, так:

function compare(a, b){
console.log(a, b);
return a - b;
}


Однак мало отримати дані, що потрібно ще придумати, як їх інтерпретувати. Коли я в останній раз заходив у книгарню, там не було книги під назвою «Класифікація алгоритмів сортування на підставі того, які елементи вони порівнюють між собою, для чайників». Можливо, з тих пір вона там з'явилася, але я вирішив обійтися без неї і покластися на здатність людини розпізнавати візуальні патерни.

Будемо робити так: візьмемо якийсь масив, потім відсортуємо його з допомогою спеціально навченого компаратора, який зберігає дані про кожному порівнянні. Потім візьмемо ці дані і побудуємо на їх підставі наступну діаграму: для кожного порівняння, в якому брали участь елементи з індексами a і b (маються на увазі індекси цих елементів у вже відсортованому масиві), ми відзначимо точку з координатами (a, b). Заразом відзначимо точку з координатами (b, a), щоб було красиво і щоб вигляд діаграми не залежав від дрібних деталей реалізації. Причому точка буде не проста, а кольорова: її колір буде символізувати те, коли сталося це порівняння. Порівняння, що сталися на самому початку сортування, зазначимо червоним, ті, що ближче до кінця — синім, а між ними будуть інші кольори веселки.

Як не дивно, цей план виявився не таким вже безглуздим. Я реалізував кілька найбільш поширених алгоритмів, і вони дійсно давали чітко помітні патерни. Ось, наприклад, сортування вибором (selection sort):



А так виглядає бульбашкова сортування (bubble sort). Відмінність добре помітно, і, в принципі, неважко зрозуміти, звідки воно береться.



І той, і інший — неефективні алгоритми сортування (середня часова складність — Про(n2)). Більш просунуті алгоритми використовують меншу кількість порівнянь, бо діаграма виходить менш зафарбованим. На початку статті наведена діаграма для пірамідального сортування (heap sort), на ній куди більше білих пікселів.

Кожна сортування володіє своїм упізнаваним паттерном. Плавний градієнт у сортування вибором, градієнт з невеликими поперечними смугами у бульбашкового сортування, смуги різного кольору сортування вставками (insertion sort). Швидке сортування (quicksort) всі расчерчивает хрестиками, сортування бінарним деревом (tree sort) — схожими хрестиками, але не монотонними, а строкатими. У сортування злиттям (merge sort) характерні короткі сині смуги ближче до діагоналі. Діаграма пірамідального сортування нагадує сортування злиттям, але має виражений колірної градієнт.

«Але що там щодо браузерів?» — запитає мене допитливий читач, не забула ще, з чого починалася стаття. Спеціально для таких читачів я зробив сторінку, де можна подивитися діаграму Array#sort у своєму поточному браузері і порівняти її з діаграмами деяких відомих алгоритмів.

Якщо коротко:

  • Свіжий Firefox використовує сортування злиттям (merge sort), але на досить малих масивах переключається на щось, що нагадує сортування вставками (insertion sort). Можете перевірити це самостійно, додавши до URL сторінки "?size=4" (без лапок, природно).
  • Свіжий десктопний Chrome використовує швидке сортування (quicksort). Однак на iOS він же використовує сортування злиттям.
  • Safari на MacOS і iOS також використовує сортування злиттям
  • Яндекс.Браузер використовує сортування злиттям
  • І стара Opera також використовує сортування злиттям


«Але що там щодо Internet Explorer?» — запитає мене допитливий читач. Що ж, я знав, що до цього питання коли-небудь дійде… З IE вийшов конфуз. Отримані в IE11 і Edge діаграми не збігаються ні з одним з реалізованих алгоритмів. Виглядають вони якось так:



Є щось спільне з сортуванням AVL-деревом, але чіткого збігу немає. Однак я не втрачаю надії і продовжую впиливать в свою сторіночку нові алгоритми. А якщо у вас сверблять руки мені допомогти, я охоче прийму ваші пулл реквесты.

На поточний момент це все, що я маю сказати. Сподіваюся, вам було цікаво.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.