28-е место в финале чемпионата Highload Cup 2018

Принял участие в соревновании разработчиков высоконагруженных систем Highload Cup 2018. В финале занял 28-е место из 212 участников с ~410 сек. штрафа и потреблением памяти 1,6-1,7 Гб.
Описание задачи здесь. Код решения опубликован на github.



Особенностью решения стала разработка inmemory column store, с операциями соединения и пересечения колонок без аллокации дополнительной памяти, для любого содержимого колонок.
Все алгоритмы хэш или основанные на деревьях - не пригодились по причине того, что они сильно тратят память на указатели (именно на сами указатели, а не на данные), которые дополнительно еще обрабатывает и GC. Из-за этого было принято решение реализовывать алгоритмы на массивах, без указателей.

Популярные сообщения из этого блога

Сертификат по Go (Golang)