Хочу представить вам
Карту Интернета или результат кластеризации более чем 350 тысяч сайтов в соответствии с переходами пользователей между ними. Размер круга определяется посещаемостью сайта, цвет – национальной принадлежностью, а положение на карте – его связями с другими сайтами. Если два сайта имеют стабильный поток пользователей между ними, то они будут «стараться» расположиться ближе друг к другу. После завершения работы алгоритма, на карте можно наблюдать скопления сайтов (кластеры) объединенные общими пользователями.
Инженерная часть Весь проект написан на языке C# и состоит из трех частей: программа кластеризации, программа генерации тайлов и веб-сайт. Каждая часть заслуживает отдельного рассмотрения и, если будет интерес, я бы мог потом рассказать о них подробнее.
Исходные данные были взяты у Алексы, они представляют из себя записи о посещаемости, upstream и downstream переходах юзеров (upstream – откуда пришли, downstream – куда ушли). После нормализации мы получаем взвешенный ненаправленный граф с 350 тысячами вершин и более 2 млн. ребер.
Обсчет такого графа – сложная вычислительная задача, поэтому был написан специальный модуль для GPU, но к счастью он не понадобился. После хитрых оптимизаций весь обсчет занял несколько недель непрерывной работы мощного, но все-таки бытового железа.
Если говорить упрощенно, то работа алгоритма заключалась в пошаговом перемещении сайтов на карте в соответствии с силами действующими на них. Много переходов пользователей – сильная сила старается сблизить сайты; если сайты расположились слишком близко, то начинает работать сила отталкивания и т.д.
Основная проблема заключалась в колоссальной вычислительной сложности подобного алгоритма. Ведь при решении задачи «в лоб», на каждом шаге нужно вычислять суперпозицию сил для каждого сайта, т.е. вычислять силы для каждой пары сайтов, а таких пар около 122 млрд. (неплохо для одного шага, правда?). Поэтому была проведена жесткая оптимизация алгоритма и полное распараллеливание вычислений. К счастью платформа .net оказалась на удивление хорошей для подобного рода забав.
Вторым этапом идет генерация тайлов. Тайл – это маленькая картинка 256х256 пикселей из которых состоит изображение карты на google maps, yandex и других сервисах. В общем-то, ничего сложного – сгенерил большую картинку, разрезал ее на квадраты нужного размера, делов-то. Но таких картинок оказалось почти 30 млн. Даже просто скопировать или удалить каталог с тайлами в windows занимает два дня. А залить их на хостинг отдельная проблема.
Третий этап – прикрутить движок google maps, собрать все воедино и заставить его показывать карту. Здесь в общем-то нет ничего сложного, хотя были некоторые сложности с проекциями и позиционированием карты.
Последний этап – выбор хостинга и релиз. Здесь тоже не обошлось без приключений. Сейчас все вертится в облаке Амазона и это оказалось гораздо проще и дешевле, чем я себе представлял.
В общем, у меня накопился некоторый опыт, и я буду рад поделится им с уважаемым сообществом. Конечно в целом ничего особенного, на Хабре бывают действительно интересные проекты и нетривиальные решения, но все же, я думаю, многим это может быть интересно.
Источник:habrahabr
