Pull to refresh
3
0
Александр Спиридонов @Sipidronov

Software engineer

Send message

Алгоритм резервуарной выборки

Reading time 3 min
Views 12K
Резервуарная выборка (eng. «reservoir sampling») — это простой и эффективный алгоритм случайной выборки некоторого количества элементов из имеющегося вектора большого и/или неизвестного заранее размера. Я не нашел об этом алгоритме ни одной статьи на Хабре и поэтому решил написать её сам.

Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:

// C++
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, vect.size() — 1);

auto result = vect[dis(gen)];

Задача «вернуть K случайных элементов из вектора размером N» уже хитрее. Здесь уже можно ошибиться — например, взять K первых элементов (это нарушит требование случайности) или взять каждый из элементов с вероятностью K/N (это нарушит требование взять ровно K элементов). Кроме того, можно реализовать и формально корректное, но крайне неэффективное решение «перемешать случайно все элементы и взять K первых». И всё становится ещё интереснее, если добавить условие того, что N — число очень большое (нам не хватит памяти сохранить все N элементов) и/или не известно заранее. Для примера представим себе, что у нас есть какой-то внешний сервис, присылающий нам элементы по одному. Мы не знаем сколько их придёт всего и не можем сохранить их все, но хотим в любой момент времени иметь набор из ровно K случайно выбранных элементов из уже полученных.

Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
Читать дальше →
Total votes 41: ↑41 and ↓0 +41
Comments 20

«Магическая константа» 0x5f3759df

Reading time 9 min
Views 120K
В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

image

Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.
Читать дальше →
Total votes 212: ↑210 and ↓2 +208
Comments 188

Точное вычисление средних и ковариаций методом Уэлфорда

Reading time 7 min
Views 22K

Метод Уэлфорда — простой и эффективный способ для вычисления средних, дисперсий, ковариаций и других статистик. Этот метод обладает целым рядом прекрасных свойств:


  • достигает отличных показателей по точности решений;
  • его чрезвычайно просто запомнить и реализовать;
  • это однопроходный онлайн-алгоритм, что крайне полезно в некоторых ситуациях.

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


Настоящая статья пытается заполнить эти пробелы.


Читать дальше →
Total votes 53: ↑53 and ↓0 +53
Comments 9

Методы определения принадлежности точки многоугольнику

Reading time 9 min
Views 73K
Недавно на хабре была статья, в которой описывалось как можно определить, где находится точка по отношению к многоугольнику: внутри или снаружи. Подобная проблема встречается в геометрическом моделировании и в компьютерной графике достаточно часто. А так как метод, описанный в статье, был несколько не оптимален, а в комментариях был небольшой хаос, возникла мысль написать эту статью. Итак, какие алгоритмы существуют в современной компьютерной графике, чтобы определить, принадлежит ли заданная точка многоугольнику или нет.
Читать дальше →
Total votes 27: ↑26 and ↓1 +25
Comments 23

Немного о Iptables, Iproute2 и эмуляции сетевых проблем

Reading time 4 min
Views 37K
Однажды мне понадобилось в Zabbix сделать мониторинг потери пакетов между мастером и репликами (репликация плохо себя чувствует если канал не очень хороший). Для этого, в Zabbix есть встроенный параметр icmppingloss, на удаленный хост отправляется серия ICMP пакетов и результат фиксируется в системе мониторинга. И вот параметр добавлен, триггер настроен. Казалось бы задача выполнена, однако как говорится «Доверяй, но проверяй». Осталось проверить что триггер сработает когда потери действительно будут. Итак, как сэмулировать потерю пакетов? Об этом, да и не только, пойдет речь под катом.

image

Читать дальше →
Total votes 48: ↑47 and ↓1 +46
Comments 8

Поиск простого на сложном: tips & tricks

Reading time 5 min
Views 20K
Достался мне тут довольно интересный проектик: на рентгенограммах сварных швов находить проволочные образцы стандартных размеров. Казалось бы, сколько уже было написано по поводу поиска паттернов на изображении, выработаны стандартные подходы и методики, но когда речь заходит о реальных задачах академические методы оказываются не настолько эффективны, как от них ожидается. Для затравочки, попробуйте найти здесь все семь проволочек:

image

Читать дальше →
Total votes 67: ↑66 and ↓1 +65
Comments 32

Хронометраж для любительских автогонок, гибкий и беспроводной

Reading time 8 min
Views 48K
Здравствуйте.
С некоторого времени я увлекся любительским автоспортом, — нет, не ночной стрит-рейсинг, а вполне легальные соревнования, проводимые в дневное время и согласованные с соответствующими структурами. Как многие догадываются, цель таких соревнований — проехать дистанцию быстрее соперника. Для чего надо измерить время прохождения дистанции.
Читать дальше →
Total votes 40: ↑39 and ↓1 +38
Comments 35

Компрессия данных в системах промышленной автоматизации. Алгоритм SwingingDoor

Reading time 5 min
Views 9K
Здравствуйте, уважаемые читатели. Хочу представить вашему вниманию описание алгоритма компрессии данных SwingingDoor и рассказать о том, как мы его применяем.



По роду деятельности я занимаюсь разработкой решений в области промышленной автоматизации, а более конкретно — разработкой информационных систем производства. Их назначение — предоставлять информацию для людей и других систем. Они предоставляют оперативные, самые последние данные, а также данные за прошлое. Данные поступают из многочисленных систем контроля (СК), количество параметров измеряется десятками тысяч.

Зачем использовать компрессию, почему бы не хранить все данные?
Читать дальше →
Total votes 70: ↑66 and ↓4 +62
Comments 43

Удачная модель ветвления для Git

Reading time 10 min
Views 974K
Перевод статьи Vincent Driessen: A successful Git branching model

В этой статье я представляю модель разработки, которую использую для всех моих проектов (как рабочих, так и частных) уже в течение года, и которая показала себя с хорошей стороны. Я давно собирался написать о ней, но до сих пор не находил свободного времени. Не буду рассказывать обо всех деталях проекта, коснусь лишь стратегии ветвления и управления релизами.



В качестве инструмента управления версиями всего исходного кода она использует Git.

Читать дальше →
Total votes 180: ↑171 and ↓9 +162
Comments 105

Важные аспекты RESTful API для вашего проекта

Reading time 6 min
Views 34K
Данная статья давно назревала в моей голове, но совсем в ином формате.
Прочитав последние несколько неуклюжих статей на тему WEB-сервисов (например: http://habrahabr.ru/blogs/development/108973/) и применения в них REST технологии, решил что настало время все-таки откинуть лень, выделить время и написать «переформатированную» в своей голове статью.
Итак, кратко, что Вы найдете в статье и кому она будет полезна:

новичкам, которые интересуются или планируют написать WEB-сервис для проекта
профи вряд ли найдут что-то новое для себя
— общая идеология REST
— применение CRUD в WEB-сервисах
— принципы KISS при построении раутеров
— лучшие практики
— немного пиара ;)
— ссылки, литература
Читать дальше →
Total votes 84: ↑74 and ↓10 +64
Comments 47

Написание web-API к своей системе

Reading time 3 min
Views 24K
Добрый день, %username%!
За последний год столкнулся с несколькими задачами по написанию SOAP/REST API к различным сервисам и вывел для себя боле-менее удобную модель. Я не претендую на фундаментальное исследование, просто хочу поделиться опытом наступания на грабли.

Для начала общие требования к default API:
  • возможность расширения
  • удобный стандартизированный формат запросов
  • удобный стандартизированный формат ответов
  • достаточный уровень безопасности
  • возврат ошибок выполнения запроса

Читать дальше →
Total votes 108: ↑83 and ↓25 +58
Comments 180

apache+nginx+gzip_static+yuicompressor

Reading time 6 min
Views 14K
В этой статье я опишу принципиальные различия Apache и Nginx, архитектуру фронтэнд-бэкэнд, установку Apache в качестве бэкэнда и Nginx в качестве фронтэнда. А также опишу технологию, позволяющую ускорить работу веб-сервера: gzip_static+yuicompressor.
Читать дальше →
Total votes 117: ↑109 and ↓8 +101
Comments 71

Linux HA на основе Pacemaker

Reading time 5 min
Views 120K
В своей предыдущей статье я вкратце коснулся темы создания High Availability решения на основе демона heartbeat. Однако, как выяснилось, что-то сложнее чем 2-х узловой кластер на нем делать не так уж удобно. Изучение проблемы вывело меня на след проекта Pacemaker. Его-то мы сейчас в кратце и рассмотрим.
Читать дальше →
Total votes 59: ↑54 and ↓5 +49
Comments 32

Балансировка нагрузки с LVS

Reading time 6 min
Views 98K
Итак, у вас есть нагруженный сервер и вам вдруг захотелось его разгрузить. Вы поставили и залили такой же (такие же), но пользователи упорно ходят на первый. В этом случае конечно же нужно задуматься о балансировке нагрузки.

Читать дальше →
Total votes 77: ↑77 and ↓0 +77
Comments 50

Information

Rating
Does not participate
Location
Akershus, Норвегия
Registered
Activity