Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки.

В данной статье хочу поднять несколько холиварную тему — тему безлоковых алгоритмов, а в частности реализации безлокового стека. Точнее, стек этот условно безлоковый, почему — будет ясно далее. Хочу сразу предупредить, что все примеры будут даны на языке C.

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

Предисловие или «Если у нас есть Wi-Fi, а давайте позиционировать с помощью него!»

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

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

В данной статье постараюсь рассмотреть технические аспекты (не касаясь прикладной применимости) позиционирования на базе технологии Wi-Fi (именно эта технология наиболее распространена внутри помещений и подходит для решения этой задачи) и проанализировать причины неудач при реализации.

Измерители CO₂ от Даджет уже снискали некоторую популярность из-за своей доступности и достаточно низкой цены(да, до десяти тысяч за NDIR-измеритель это еще бюджетно).
И вот когда я в один прекрасный момент задумался о мониторинге в своем доме не только температуры и влажности, но еще и количества углекислого газа, я сразу же вспомнил об этой компании и ее приборах.



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

Итак, решено: берем монитор CO₂ и прикручиваем к нему WiFi в виде ESP8266.

В апреле этого года в рамках проекта «Коллективные явления в квантовой материи», которым руководит ведущий ученый К.Б. Ефетов, к нам приезжал ведущий международный ученый А.М. Загоскин, ридер по квантовой физике физического факультета Университета Лафборо, Великобритания, один из основателей компании D-Wave Systems Inc. (1999, Канада), которая выпустила первый в мире адиабатический квантовый симулятор.

Наш университет не мог оставить без внимания столь значимое событие. А.М. Загоскин прочитал лекцию, и мы запечатлели это событие, организовали видеосъемку и смонтировали видео, которое можно посмотреть здесь. Данный материал, несомненно, будет интересен целевой аудитории! Также мы не могли упустить такую возможность и попросили профессора поучаствовать в нашей уже традиционной рубрике на GT «Экспертное мнение».

Александр Маркович с радостью согласился написать заметку в научно-популярном формате про квантовые компьютеры и инженерию специально для нашего корпоративного блога на GT. Мы уверены, что именно на GT сконцентрирована большая часть целевой аудитории, которой будет интересен данный материал!

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

Я сейчас в поисках работы программиста в Москве. И мне звонят некоторые кадровые агентства и интересуются есть ли у меня ИП, так как их клиент-работодатель вместо трудового договора с работниками заключает договоры оказания услуг или субподряда с ИП или ООО с одним учредителем, я их буду называть ИП в дальнейшем. ИП у меня нет, но есть не приносящее дохода ООО, где я веду бухучет самостоятельно. Поэтому и знаю, что это такое, какие именно налоги нужно платить и почему эта схема в России не законна и чем все это грозить горе-работнику, который на это согласился. Еще раз повторяю, я не юрист, а программист; то, что я опишу ниже, вполне могло устареть, измениться и т.п., и, если в комментариях укажут действующую норму, я не буду против.

Термин «О-большое», знакомый нам из курса матанализа, был введён Паулем Бахманом в конце XIX века для описания асимптотического поведения функций. В конце 1970-х Дональд Кнут придумал применять этот термин для оценки эффективности и ресурсоёмкости алгоритмов, благодаря чему с «О-большим» знакомо большинство программистов. Понимание асимптотики быстродействия и ресурсоёмкости даёт возможность выбрать наиболее подходящий метод решения задачи в зависимости от текущих потребностей. «Плохая» асимптотика позволяет сразу же отбросить неподходящий метод.



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

Недавно я выступал на конференции Droidcon в Париже с докладом (оригинал на французском), в котором рассматривал проблемы, возникшие у нас в Square при работе с фрагментами и возможности полного отказа от фрагментов.

В 2011-м мы решили использовать фрагменты по следующим причинам:

• Тогда мы ещё не поддерживали планшеты, но знали, что когда-нибудь будем. Фрагменты помогают создавать адаптивный пользовательский интерфейс, и потому казались хорошим выбором.
• Фрагменты являются контроллерами представлений, они содержат куски бизнес-логики, которые могут быть протестированы.
• API фрагментов предоставляет возможность работы с backstack'ом (в общих чертах это выглядит так же, как и работа со стэком Activity, но при этом вы остаётесь в рамках одной Activity).
• Так как фрагменты построены на обычных представлениях (views), а представления могут быть анимированы средствами Android-фреймворка, то фрагменты могли в теории дать нам возможность использовать более интересные переходы между экранами.
• Google рекомендовал фрагменты к использованию, а мы хотели сделать наш код как можно более стандартным.

С 2011-го года много воды утекло, и мы нашли варианты получше.

Изнурительная работа по 48 часов в неделю и больше становится обычным делом в развитых странах. Но исследования показывают, что такой напряжённый труд повышает риск сердечно-сосудистых заболеваний, негативно отражается на семейной жизни, увеличивает интенсивность курения, уровень тревожности, вызывает нарушения пищеварительной системы и проблемы с алкоголем.

Отпуск не поможет избавиться от проблем, связанных с выгоранием на работе: положительный эффект отпуска длится всего 2-4 недели. К счастью, существуют другие методы снятия стресса.

Пользователь: это невозможно, GPS съест батарейку
Джуниор: это возможно, используй Geofences
Сеньор: есть варианты и получше

На картинке сначала в одну, а потом в другую сторону одновременно с одним человеком «прогулялись» 6 одинаковых телефонов. Но какой разный результат!

Вместо пролога

Я, пожалуй, нарушу традицию всех подобных статей и не буду рассказывать, зачем нужен NDK. Если вы это читаете, значит вам он зачем-то понадобился. Но один из реальных кейсов использования мы, конечно же, рассмотрим.

Эта история началась с того, что на Google I/O 2015 была представлена поддержка нативной разработки прямо не выходя из студии, Android-студии. Естественно, Google, как всегда, наобещал и заставил ждать, пока они все это выкатят для обычных людей. И вот 9 июля это свершилось: на stable channel появился кусочек того пирога, который нам наобещали.

В данной статье я бы хотел рассказать о собственном опыте оптимизации выполнения множества регулярных выражений при помощи системы hyperscan. Так вышло, что при разработке своего спам-фильтра rspamd я столкнулся с необходимостью портировать большой объем старых правил, написанных для spamassassin за несколько лет работы. Моим первым решением было написать плагин, который бы читал эти правила и строил из них синтаксическое дерево. Затем на этом дереве выполнялись различные оптимизации, чтобы сократить общее время выполнения (об этом я даже делал небольшую презентацию).

К сожалению, в ходе эксплуатации выяснилось, что pcre все равно являются узким местом, и на больших письмах этот набор правил работает слишком медленно. Выяснилось, например, что на письме размером в мегабайт pcre проверяет около гигабайта (!) текста. Различные трюки, вроде ограничения количества текста для регулярных выражений, оказывали негативное влияние на срабатывания правил, а оптимизации pcre путем интенсивного использования jit fast path через pcre_jit_exec оказались слишком опасными — некоторые старые выражения были откровенно некорректными и в сочетании с некорректным входным текстом, например, содержащим «битые» UTF8 символы, приводили к воспроизводимым багам с повреждением стека программы. Однако на конференции highload мы поговорили со Вячеславом Ольховченковым, и он мне посоветовал посмотреть на hyperscan. Далее я перейду к сути и расскажу, что из этого получилось.

Обычные торги идут через целую серию «прокладок». Давайте начнём с самого начала и попробуем разобраться, что всё это значит с точки зрения финансового рынка и ИТ-систем.

Итак, вы хотите купить акции Apple. Они листингуются на Санкт-Петербургской бирже (причём без согласия эмитента), можно купить через некоторых брокеров.

Вот кто из иностранных ИТ-игроков есть на бирже СПБ:

• ALPHABET (это GOOGLE)
• APPLE
• CISCO
• FACEBOOK
• INTEL
• INTERNATIONAL BUS. MACHINES ( IBM)
• MICRON TECHNOLOGY
• MICROSOFT
• PAYPAL
• QUALCOMM
• YAHOO

Остальные крупные ИТ-компании не торгуются в России. Вообще. Вы не можете взять и купить одну из них. Поэтому, если вы хотите купить одну из них, вам нужно иметь брокера из другой страны. А дальше начинается интересное.

Часто клиенты спрашивают нас о p99-метрике (99-й перцентиль).

Это определенно разумная просьба и мы планируем добавить подобную функциональность в VividCortex (об этом расскажу позже). Но в то же время, когда клиенты спрашивают об этом, они подразумевают нечто совершенно определенное — нечто, что может быть проблемой. Они просят не 99-й перцентиль по какой-то метрике, они просят метрику по 99-му перцентилю. Это обычное дело для таких систем как Graphite, но все это дает не тот результат, который от таких систем ожидается. Это пост расскажет вам о том, что, возможно, у вас неверные представления про перцентили, о точной степени ваших заблуждений и о том, что вы все таки можете сделать правильно в этом случае.

(Это перевод статьи которую написал Baron Schwartz.)

Год назад выполнял довольно интересную работу по разработке встраиваемого компьютера для одного предприятия, занимающегося электроникой. Компьютер ничего принципиально интересного не представлял: процессор Cortex A-8, работающий на субгигагерцовых частотах, 512Mb DDR3, 1Gb NAND, легковесная сборка Linux. Однако устройству, в который компьютер встраивался, а значит и ему самому, предстояло работать в довольно жестких условиях. Широкий температурный диапазон (от -40 до +85 градусов Цельсия), влагостойкость, стойкость к электромагнитным излучениям, киловольтные импульсы по питанию, защита от статики в 4 кВ и много чего интересного, что хорошо описано в различных ГОСТах на спецтехнику, – это все про него. Одно из основных требований заказчика – срок выработки на отказ не менее 10 лет. При этом производитель обеспечивает гарантийный ремонт изделия в течении пяти лет, потому вопрос не риторический, а денежный и серьезный. В изделие была заложена соответствующая элементная база. Прибор с честью прошел испытания и получил требуемые сертификаты, но разговор не про то. Проблемы начались когда была изготовлена установочная партия, и устройства разошлись по отделам и КБ для создания прикладного ПО. Пошли возвраты с формулировкой: «Чего-то не загружается».

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

Рассмотрим подробно, как защищены современные валюты, как происходит проверка подлинности (валидация) и что за аппаратура для этого применяется.

Было время, когда понадобилось оценить производительность памяти в контексте технологии Hyper-threading. Мы пришли к выводу, что ее влияние не всегда позитивно. Когда появился квант свободного времени, возникло желание продолжить исследования и рассмотреть происходящие процессы с точностью до машинных тактов и битов, используя программное обеспечение собственной разработки.

Для некоторых датчиков ускорения требуется дополнительная калибровка нуля после монтажа на плату. Когда я увидел несколько исходников с калибровкой датчиков ускорения, где составляющая G учитывалась просто путём вычитания из оси Z величины = 9,8 м/с2 — появилась идея написать данную заметку.

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

В статье описана настройка центрального логирования для разных типов приложений (Python, Java (java.util.logging), Go, bash) с помощью довольно нового проекта Heka.

Heka разрабатывается в Mozilla и написана на Go. Именно поэтому я использую его вместо logstash, который имеет сходные возможности.