Среди множества популярных алгоритмов на графах существует целый ряд алгоритмов, позволяющих находить кратчайшие пути. Каждый из них решает собственную задачу и, соответственно, имеет свое применение на практике. Так, например, алгоритм A* может использовать различные эвристики, чтобы находить путь минимальной стоимости в видеоиграх, а алгоритм Флойда — Уоршелла позволяет эффективно находить кратчайшие пути между всеми парами вершин в плотных графах и даже может использоваться в методе Шульца для определения победителя выборов. Однако, одной из областей, в которых алгоритмы поиска кратчайших путей получили наибольшие развитие и применение, являются компьютерные коммуникационные сети.

Эта статья Романа Климовицкого повествует о том, как возникают и решаются задачи такого типа в компании Qrator Labs.

Вот уже несколько лет как Qrator Labs работает с различными университетами с целью найти студентов, заинтересованных во вполне определенных задачах, над которыми мы работаем. Студентам это помогает получить новый опыт или обозначить будущую карьерную тропу в области сетевой и, в общем, компьютерной инженерии. А Qrator Labs — найти потенциальных сотрудников.

На данный момент в составе Qrator Labs работают несколько сотрудников, пришедших со стажировки, в свою очередь начавшейся с участия в небольших проектах, курируемых разработчиками Qrator Labs в рамках университетского “инновационного практикума”. Конечно, далеко не все в итоге выбирают компьютерную инженерию в качестве области специализации: из 23 студентов, прошедших практику под нашим кураторством в 2019 и 2020 годах, лишь 9 были приглашены на стажировку. И только четверо из них стали нашими коллегами, что делает каждую такую историю особенной.

Введение

В одной из наших предыдущих публикаций мы рассказывали о способе измерения интенсивности потока событий при помощи счетчика на основе экспоненциального распада. Оказывается, идея такого счётчика имеет интересное обобщение.

Мы рады представить вам заметку, написанную инженером Qrator Labs Дмитрием Камальдиновым. Если вы хотите быть частью нашей команды Core и заниматься подобными задачами - пишите нам на hr@qrator.net.

1 Введение

При реализации потоковых алгоритмов часто возникает задача подсчёта каких-то событий: приход пакета, установка соединения; при этом доступная память может стать узким местом: обычный \(n\)-битный счётчик позволяет учесть не более \(2^n - 1\) событий.
Одним из способов обработки большего диапазона значений, используя то же количество памяти, является вероятностный подсчёт. В этой статье будет предложен обзор известного алгоритма Морриса, а также некоторых его обобщений.

Другой способ уменьшить количество бит, необходимое для хранения значения счётчика, — использование распада. Об этом подходе мы рассказываем здесь, а также собираемся в ближайшее время опубликовать ещё одну заметку по теме.

Мы начнём с разбора простейшего алгоритма вероятностного подсчёта, выделим его недостатки (раздел 2). Затем (раздел 3) опишем алгоритм, впервые преложенный Робертом Моррисом в 1978 году, укажем его важнейшие свойства и приемущества. Для большинства нетривиальных формул и утверждений в тексте присутствуют наши доказательства --- интересующийся читатель сможет найти их во вкладышах. В трёх последующих разделах мы изложим полезные расширения классического алгоритма: вы узнаете, что общего у счётчиков Морриса и экспоненциального распада, как можно уменьшить ошибку, пожертвовав максимальным значением, и как эффективно обрабатывать взвешенные события.

В чем заключается ценность участия в одной из партнерских программ Qrator Labs?

Мы твердо верим — работая вместе, можно добиться лучшего результата, нежели по отдельности. Это основная причина, по которой мы годами прикладывали усилия к построению осмысленных партнерских отношений с самыми разнообразными компаниями. Но на верхнем уровне все наши партнеры делятся на два типа. Первые хотят предоставить собственному потребителю первоклассную технологию защиты от DDoS-атак, разрабатываемую в Qrator Labs, вместе со всеми экосистемными продуктами и услугами. Вторые заинтересованы в том, чтобы предоставить продукт собственной разработки клиентам Qrator Labs, интегрировавшись в нашу сеть фильтрации.

В начале 2021 года Qrator Labs отмечает собственный десятилетний юбилей. 19 января наша компания пройдет через формальную отметку 10 лет деятельности, войдя во вторую декаду существования.

Хотя, на самом деле, все началось несколько ранее - когда в возрасте десяти лет Александр первый раз увидел Robotron K 1820 - в 2008 году, когда Александр Лямин - основатель и директор Qrator Labs, пришел с идеей к начальникам в МГУ, где на тот момент времени он работал сетевым инженером, о создании исследовательского проекта по нейтрализации DDoS-атак. Сеть МГУ тогда была одной из крупнейших в стране и, как мы знаем сейчас, это было лучшее место для того, чтобы посеять зерно будущей технологии.

Тогда администрация МГУ согласилась, и Александр перенёс собственное оборудование в университет, одновременно с этим собирая команду. Через два года, летом 2010, стало ясно, что проект успешен. Он принял на себя DDoS-атаку, превышающую емкость вышестоящего поставщика МГУ. И 22 июня боссы выдвинули ультиматум г-ну Лямину - закрываться или уходить.

Александр Лямин решил инкорпорироваться на свои собственные средства, что буквально значило за свои строить инфраструктуру с нуля. При этом изначальная архитектура сети должна быть распределенной вместо концентрированной, так как ресурсы последней бы точно не справились со столь специфической задачей.

В сентябре 2010 года первая площадка была введена в эксплуатацию.

Это транскрипция выступления прозвучавшего на Yandex NextHop 2020 — видео в конце страницы

Приветствую. Меня зовут Александр Зубков, я хочу рассказать про Linux Switchdev — что это такое и как мы с ним живем в Qrator Labs.

На первом в истории полностью виртуальном мероприятии РИТ++, прошедшем в конце мая, инженер Qrator Labs — Георгий Тарасов, рассказал публике про веб-скрейпинг, он же парсинг, популярным языком. Мы решили предоставить вашему вниманию транскрипцию выступления.

«В 1665 году Кембриджский университет закрылся из-за эпидемии чумы. Исааку Ньютону пришлось работать из дома. Он открыл дифференциальное и интегральное исчисление, а также закон всемирного тяготения».

К сожалению, мы живем в выдающееся время. С наступлением 2020 года и эпидемией COVID-19 сотрудники по всему миру закрываются дома на карантин, стараясь изо всех сил поддерживать нормальное течение жизни, а значит, и продолжать работать. Но есть одно отличие от всех предыдущих инфекционных пандемий, которые пережило человечество — в этот раз у нас есть Интернет.

tl;dr

github.com/QratorLabs/fastenum

pip install fast-enum

Зачем нужно перечисление (enum)

(если вы все знаете — опуститесь до секции «Перечисления в стандартной библиотеке»)

Представьте, что вам нужно описать набор всех возможных состояний сущностей в собственной модели базы данных. Скорее всего, вы возьмёте пачку констант, определенных прямо в пространстве имен модуля:

# /path/to/package/static.py:
INITIAL = 0
PROCESSING = 1
PROCESSED = 2
DECLINED = 3
RETURNED = 4
...

… или как статические атрибуты класса:

class MyModelStates:
  INITIAL = 0
  PROCESSING = 1
  PROCESSED = 2
  DECLINED = 3
  RETURNED = 4

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

Однако, и константа модуля, и класс со статическими атрибутами страдают от внутренней природы объектов Python: все они изменяемы (мутабельны). Можно случайно присвоить значение своей константе во время выполнения, а отладка и откат сломанных объектов — отдельное приключение. Так что вы можете захотеть сделать пачку констант неизменяемыми в том смысле, что количество объявленных констант и их значения, на которые они отображаются, не будут изменяться во время выполнения программы.