найпопулярніші слова в двох терабайтах коду

Привіт, Друзі!

Я тут проаналізував 2ТБ коду і отримав найпопулярніші слова в різних мовах програмування. Результати можна показати у вигляді хмар тегів і простим списком:

image

Сайт знаходиться тут, а його вихідні коди можна почитати на гітхабі.

Під катом описано в деталях про те, як збиралися дані, як будувався сайт і як вкладалися хмари. І трошки спостережень.

Приємного читання!


Спостереження

  • найпопулярнішим текстом у всіх мовах програмування текст зі ліцензій. Серед усіх мов Java тут перемогла. З 966 найпопулярніших слів, 127 були про ліцензії:
    image
    Напевно, культура додавання ліцензій в кожен .java файл набагато сильніше ніж у інших мовах. Ви бачили офіційний hello world?
  • Lua
    — єдина мова програмування в якому нецензурне слово увійшло в топ. Можете знайти?
  • Go найпопулярнішим словом виявилося
    err
    . У цій мові немає винятків?


— Як?
Дані я збирав з допомогою BigQuery. Google спільно з GitHub'ом, виклали повний знімок исходников в публічний дата сет github_repos. Індекс був побудований в кінці 2016 року.

При побудові хмар я накладаю деякі обмеження на дані:

  • Максимальна довжина рядка зі словом не повинна перевищувати 120 символів. Це допомагає позбутися від згенерованого коду (наприклад, в минифицированном javascript'е).
  • Пунктуація (
    , ; : .
    ), оператори (
    + - * ...
    ) і числа ігноруються. Наприклад, рядок
    a + b + 42
    буде порахована як два слова
    a
    та
    b
  • Оскільки текст ліцензій запруджував візуалізації, я прибрав всі рядки в яких є слова-маркери, специфічні для ліцензій (наприклад,
    license
    ,
    noninfringement
    і так далі...
  • Регістр слів враховується.
    This
    та
    this
    вважаються двома різними словами.


Як збиралися дані?

BigQuery — приголомшлива платформа. Вміст всіх файлів з гитхаба зберігається прямим текстом у таблицях.

Файл Сожержимое
File 1.h // File 1 content\n#ifndef FOO\n " #define FOO...
File 2.h // File 2 content\n#ifndef BAR\n " #define BAR...
BigQuery дозволяє написати звичайний SQL запит і виконати його з дивовижною швидкістю.

Спочатку я вирішив розбити вміст всіх файлів на слова, і потім використовувати
GROUP BY
щоб порахувати їх.

Слово Скільки разів зустрів
File 2
content 2
... ...
На жаль, такий підхід вириває слово з контексту. Мені ж дуже хотілося показувати слова з прикладами, як вони використовуються:

image

Як же бути? Замість простого розбиття на слова я створив проміжну таблицю, де файли розбиті по рядках:

Рядок Скільки разів зустрів рядок
// File content 1 1
#ifndef FOO 1
#ifndef FOO 1
... ...
Таке проміжне зберігання дозволяє скоротити розмір оброблюваних даних з ~2TB до ~12GB.

Тепер, щоб отримати найбільш популярні слова з цієї таблиці, ми можемо розбити кожну рядок на індивідуальні слова, але при цьому зберегти початкову рядок:

Рядок Слово
// File content 1 File
// File content 1 content
#ifndef FOO ifndef
#define FOO FOO
... ...


Здавалося б, практично нічого не змінилося. Але, в такій інтерпретації ми можемо використовувати віконні функції щоб отримати топ 10 рядків по кожному слову (
SELECT ... OVER (PARTITION BY ...)
як в цьому питанні на StackOverflow

Поточний код запиту можна знайти тут: extract_words.sql.

до Речі... Мій SQL знаходиться на досить початковому рівні. Тому якщо ви, дорогий читачу, знайдете помилку, або знаєте більш відповідний спосіб — будь ласка, дайте мені знати.

Як малювати хмара тегів?



В основі всіх відомих мені отрисовщиков тегів лежить такий алгоритм:

Для кожного слова `w`:
 
Крок 1. Спробувати нарисовать'w` у випадковій точці (x, y)
 
Крок 2. Якщо слово перетинає будь-яке інше слово - повторити Крок 1.
 


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

Для простоти, слова можна розглядати як прямокутники. Ми намагаємося розміщувати всі прямокутники на екрані так, щоб ні один прямокутник не перетинав зайняті пікселі на екрані.

Самої ресурсномісткою частиною цього алгоритму є перевірка перетинів. Особливо в кінці, коли весь вільний простір в основному вже зайнято, знайти нову область куди можна вставити слово стає дуже складно (а інколи і не можливо).

Різні імплементації намагаються прискорити цю частину алгоритму індексуванням зайнятого простору

  • Деякі використовують Summed area table. Це спеціальна структура даних, яка дозволяє за час
    O(1)
    сказати чи перетинає новий прямокутник щось на екрані. На жаль, структуру потрібно оновлювати після змін на екрані, що дає посередню продуктивність.
  • Я бачив дехто використовував різновиди R-дерев, щоб індексувати зайняте простір. У такому підході пошук перетинів працює повільніше, ніж з Summed Area Tables, але зате підтримку індексу працює швидше. Проте реалізація R-дерев — не сама тривіальна задача.


Я хотів спробувати щось інше. Замість індексування зайнятого простору, я хотів мати індекс вільної області. Щоб можна відразу вибрати великий прямокутник в якому гарантовано знайдеться місце для нового надходження.

Для індексу я скористався квад-деревом. Кожний проміжний вузол дерева зберігає інформацію про те, скільки в ньому вільних/зайнятих пікселів. Так можна миттєво відмітати квадранти, в яких недостатньо вільних пікселів.

Простіше всього це бачити на картинці. Ось квад-дерево логотипу JS:

image

Білі порожні прямокутники — це вільний простір. Якщо потрібно додати новий прямокутник який менше ніж будь-який з цих порожніх прямокутників — ми можемо сміливо його там малювати.

Цей підхід дає непогані результати, але може призвести до візуальним артифактам. Адже жоден новий прямокутник не може знаходиться на перетині квадрантів:

image

Більш того, що якщо жоден з вільних квадрантів не володіє достатнім розміром? А при цьому якщо суміжні квадранти об'єднати, то місця достатньо?

Об'єднання вільних квадрантів і був мій наступний крок. Я просто «розширюю» квади вліво/вправо від мети. Це дещо уповільнює час побудови, але зменшує артефакти і дає кращі результати:

image

до Речі... Мій код укладальника не доступний разом з сайтом. Він був написаний на швидку руку і його складно використовувати в інших контекстах. Якщо вам потрібен хороший укладальник, подивіться на
amueller/word_cloud

Як був зроблений сайт?

Вивід тексту

В цілому я був задоволений швидкістю споруди хмари тегів. Але в контексті мого сайту цій швидкості було не досить.

Я використовував SVG щоб малювати слова на екрані. Сама побудова стількох текстових SVG елементів може легко заблокувати UI потік на декілька секунд. Куди вже тут ще позиції вважати хмара тегів?

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

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

Для цих цілей я написав anvaka/rafor. Ця бібліотека являє собою адаптивний, асинхронний цикл `for` на основі
requestAnimationFrame()
. Всі ітерації виконуються на різних етапах циклу подій, і тим самим знижується навантаження на UI потік. Початкова завантаження сайту виглядає більш плавною.

Навігація і зум

З допомогою мишки, клавіатури або touch-screen'a ви можете наближати, видаляти карту і рухати її по екрану так само, як це робить Google Maps. Все це робиться за допомогою бібліотеки panzoom.

Модель програми

Я використовую vue.js UI. Вона проста у використанні і швидка в роботі. Особливо здорово мати vue-компоненти в окремих файлах — не часто доводиться перемикатися між js/розміткою/стилями. Hot-reload робить розробку особливо приємною.

Стан додатки зберігається в одному об'єкті appState. Коли ви вибираєте мову програмування — слова і їх контекст завантажуються асинхронно.

Для обміну подіями між компонентами я використовую свою міні-бібліотеку ngraph.events. Спочатку я зробив її для швидкісного обміну подіями в моїх бібліотеках графів. Але і тут вона працює відмінно як диспатчер.

Нарешті, anvaka/query-state прив'язує рядок запиту двонаправленим байндингом до вибору мови програмування

image

висновок
Цей проект був моїм вечірнім хобі протягом останніх двох місяців. Не дивлячись на всі недоліки хмар тегів, мені було дуже цікаво.

Я щиро сподіваюся, що вам теж сподобалося це дослідження :)!

Спасибі, дорогий читачу, за вашу увагу. І окреме спасибі моїй половинці за її нескінченну підтримку і підказки.
Джерело: Хабрахабр

0 коментарів

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