Самые популярные слова в двух терабайтах кода

Привет, Друзья!

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

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

Под катом описано в деталях о том как собирались данные, как строился сайт и как укладывались облака. И немножко наблюдений.

Приятного чтения!

Наблюдения

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

Как?

Данные я собирал с помощью BigQuery. Google, совместно с GitHub'ом, выложили полный снимок исходников в публичный дата сет github_repos. Индекс был построен в конце 2016 года.

При построении облаков я накладываю некоторые ограничения на данные:

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

Как собирались данные?

BigQuery — потрясающая платформа. Содержимое всех файлов из гитхаба хранится прямым текстом в таблицах.

BigQuery позволяет написать обычный SQL запрос и выполнить его с изумительной скоростью.

Сначала я решил разбить содержимое всех файлов на слова, и потом использовать GROUP BY чтобы посчитать их.

К сожалению, такой подход вырывает слово из контекста. Мне же очень хотелось показывать слова с примерами как они используются:

Как же быть? Вместо простого разбиения на слова я создал промежуточную таблицу, где файлы разбиты построчно: 

Такое промежуточное хранение позволяет сократить размер обрабатываемых данных с ~2TB до ~12GB.

Теперь, чтобы получить самые популярные слова из этой таблицы, мы можем разбить каждую строку на индивидуальные слова, но при этом сохранить изначальную строку:

Казалось бы, практически ничего не изменилось. Но, в такой интерпретации мы можем использовать оконные функции чтобы получить топ 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:

Белые пустые прямоугольники — это свободное пространство. Если нужно добавить новый прямоугольник который меньше чем любой из этих пустых прямоугольников — мы можем смело его там рисовать.

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

Более того, что если ни один из свободных квадрантов не обладает достаточным размером? А при этом если смежные квадранты объединить, то места достаточно?

Объединение свободных квадрантов и был мой следующий шаг. Я просто «расширяю» квады влево/вправо от цели. Это немножко замедляет время построения, но уменьшает артефакты и дает лучше результаты:

Кстати... Мой код укладчика не доступен вместе с сайтом. Он был написан на скорую руку и его сложно использовать в других контекстах. Если вам нужен хороший укладчик, посмотрите на
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 привязывает строку запроса двунаправленным байндингом к выбору языка программирования

В заключение

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

Я искренне надеюсь, что вам тоже понравилось это исследование :)!

Спасибо, дорогой читатель, за ваше внимание. И отдельное спасибо моей половинке за ее бесконечную поддержку и подсказки.

Автор: anvaka

Источник