Не так давно в boost-1.53 появился целый новый раздел — lockfree реализующий неблокирующие очереди и стек.
Я последние несколько лет работал с так называемыми неблокируюшими алгоритмами (lock-free data structures), мы их сами писали, сами тестировали, сами использовали и втайне ими гордились. Естественно, у нас немедленно встал вопрос, переходить ли с самодельных библиотек на boost, и если переходить, то когда?
Вот тогда у меня и возникла в первый раз идея применить к boost::lockfree кое-какие из методик которыми мы испытывали собственный код. К счастью, сам алгоритм нам тестировать не придется и можно сосредоточиться на измерении производительности.
Я постараюсь сделать статью интересной для всех. Тем кто еще не сталкивался с подобными задачами будет полезно посмотреть на то что такие алгоритмы способны, а главное, где и как их стоит или не стоит использовать. Для тех кто имеет опыт разработки неблокирующих очередей возможно будет интересно сравнить данные количественных измерений. Я сам по крайней мере таких публикаций еще не видел.

Несколько лет назад я про него писал, а сейчас запилил видюшку с изготовлением и использованием.



Само жало обкатано мной при поточной пайке, позволяет поддерживать высокое качество штырьевой пайки при практически любой квалификации монтажника и любой отстойности паяльной станции. Выгорает оно спустя примерно — 30..40 тысяч точек. Впрочем, зависит от типа жала донора. Родное Хакко живет очень долго, т.к. у него очень толстый слой защитного покрытия и пока с него не вымоет всю медь, а его самого наглухо не окислит изнутри, оно будет жить. Сколько будет жить этот странный китаец я не знаю. Но выглядит достойно, может сдюжит.

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

Не пришло ли время для следующего технологического уклада, который позволит вывести цивилизацию человеков на качественно новый уровень? Судя по интересу со стороны государств и крупных корпораций (aka Google), да и просто с точки зрения личных убеждений основой нового технологического уклада могут стать биоинженерия и робототехника. Если, конечно, внезапно не наступит технологическая сингулярность!

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

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

Что вас ждёт под катом:

• Избегаем вызовов макросов вместо функций, на примере max/min.
• Вызываем оптимальную функцию, на примере std::swap и её специализации в разных пространствах имен.
• Ускоряем вставку в std::vector.
• Деструкторы в C++11.

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

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

во всякой теории, включающей аксиоматику Пеано (аксиоматика о натуральных числах), для любого высказывания P доказуемость высказывания «если доказуемо P, тогда P истинно» возможна только в случае доказуемости самого высказывания P.

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

Известно, что задача определения того, истинна ли некоторая функция Integer -> Bool хотя бы для одного числа вычислительно неразрешима. Однако, нечто, на первый взгляд кажущееся как раз таким оракулом (а именно, функцией (Integer -> Bool) -> Maybe Integer) будет описано в этой статье.

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

data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)

Другими словами, натуральное число — это либо ноль, либо некоторое натуральное число, увеличенное на единицу (Succ от слова successor).

Также, для удобства, определим основные операции (сложение, умножение, конвертация из Integer) над числами в таком представлении:

instance Num Nat where
    Zero + y = y
    Succ x + y = Succ (x + y)

    Zero * y = Zero
    Succ x * y = y + (x * y)

    fromInteger 0 = Zero
    fromInteger n = Succ (fromInteger (n-1))

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

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

21 октября мы с Филлипом Компо и Павлом Певзнером из Университета Калифорнии запускаем онлайн-курс по алгоритмам в биоинформатике на Coursera. Уже до 21 октября можно посмотреть содержание первой главы курса и порешать задачи на нашем новом образовательном проекте Stepic, над которым работает команда широко известного в узких (биоинформатических) кругах проекта Розалинд.

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

Что делает крупный разработчик игр, когда ему нужно состряпать много помещений для игрового мира? Нанимает кучу художников. Что делает ленивый/бедный/одинокий разработчик игр в такой же ситуации? Пишет процедурный генератор, который выполняет за него всю грязную работу.

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

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

Abstract: Рассказ про устройство Интернета, как «сети сетей» в виде текста для чтения, без двоичной системы счисления и нюансов BGP. Большая часть расказа будет не про процесс общения ноутбука с точкой доступа, а о том, что происходит после того, как данные пройдут «шлюз по умолчанию». Предупреждаю, букв много.

Вступление

Маленький провокативный вброс: ни один из читателей этой статьи к Интернету не подключен. Все подключены к сети своего провайдера, и не более. Подключение к Интернету дорогое, его сложно делать, вам потребуется очень крутое оборудование, несколько договоров с несколькими операторами связи и квалифицированные сотрудники. Простому домашнему пользователю это никак и никогда не светит. Не говоря уже о том, что в Интернете может быть не больше 4 миллиардов подключившихся (а до недавнего времени было даже «не более 65536») [1]. Даже если весь Интернет перейдёт на ipv6, это число не поменяется.

Вот число подключившихся к Интернету [2]:

По оси Y — число в штуках. Штуках, штуках. И вас в этом числе не посчитали.

Почему?

Дело в том, что Internet — это, если переводить буквально, «межсетье». Сеть Сетей. И участниками Интернета являются не пользователи (их компьютеры, планшеты, микроволновки с wifi и т.д.), а сети. Сети и только сети участвуют в работе Интернета. Интернет — это то, что связывает разные сети между друг другом.

За четыре года работы над онлайн консультантом WebConsult мы накопили достаточно большой опыт, и оказалось, что изначально мы не учли многих вещей, которые потом приходилось переделывать – в итоге это стоило нам массы времени, средств и нервов. Эта статья, а возможно и цикл статей, будут посвящены аспектам, которые необходимо продумать еще до начала разработки, дабы будущие стартаперы изначально закладывали грамотную основу в свои веб-приложения. Этой статьи нам очень не хватало четыре года назад, когда создание системы только начиналось, и мы надеемся, что она поможет вам не повторить наших основных ошибок. Многие приведенные советы кому-то покажутся очевидными, однако часто разработчики их упускают, поэтому мы считаем необходимым еще раз напомнить о простых вещах.

Пост №1. Что такое SOINN


SOINN – это самоорганизующаяся инкрементная нейронная сеть. Структура и алгоритм такой нейронной сети повидимому хорошо себя зарекомендовал в японской лаборатории Hasegawa (сайт — haselab.info), потому что он в итоге был взят за основу и дальнейшее развитие алгоритмов искусственного интеллекта шло путем небольших модификаций и надстроек к сети SOINN.

Базовая сеть SOINN состоит из двух слоев. Сеть получает входной вектор и на первом слое после обучения создает узел (нейрон) – определяющий класс для входных данных. Если входной вектор похож на существующий класс (мера похожести определяется настройками алгоритма обучения) то два самых похожих нейрона первого слоя объединяются связью, либо если входной вектор не похож не на один существующей класс, то в первом слое создается новый нейрон, определяющий текущий класс. Очень похожие нейроны первого слоя, объединенные связью, определяются как один класс. Первый слой является входным слоем для второго слоя, и по аналогичному алгоритму, с небольшим исключением, создаются классы во втором слое.

На основе SOINN созданы такие сети, как (далее представлены название сети и описание сети от ее создателей):

^{«The Grizzly» — первое распечатанное на 3D-принтере ружье}

Технология 3D-распечатки набирает обороты с каждым месяцем, и все чаще появляются новые модели оружия, распечатанные на 3D-принтере. На Хабре было подробное описание нашумевшего пистолета «Освободитель» («The Liberator») — Как работает «Освободитель» (Да-да, мы напечатали пистолет). Для его производства требовался принтер Stratasys Dimension SST стоимостью $8000. Совсем скоро компания Lulzbot усовершенствовала пистолет, который уже можно было распечатать на принтере Lulzbot AO-101 стоимостью всего $1700.

C тех пор, как я опубликовал первую обзорную статью о биоинформатике, прошел уже почти год. Хотелось бы писать чаще, но как раз биоинформатика отвлекаться и не дает. В предыдущей статье была упомянута задача сборки генома, а также Лаборатория алгоритмической биологии (СПбАУ РАН), в которой ей занимаются. Как уже было сказано, над этой задачей работают во многих университетах мира давно и достаточно успешно. Однако для сборки генома биологи получают огромное количество различных типов данных, каждый из которых имеет свои особенности. Около пяти лет назад появилась технология MDA, открывшая большие возможности в области изучения бактерий. В результате появился тип данных, для которого потребовался новый геномный сборщик. Через несколько лет он был разработан, и не в Стэнфорде или Массачусетсе, а в Санкт-Петербурге, в молодом Академическом университете. Но обо всем по порядку.

Внимание: перед тем как читать текст ниже, вы уже должны иметь представление о том, что такое монады. Если это не так, то прежде прочитайте вот этот пост!

Перед нами функция half:


И мы можем применить её несколько раз:

half . half $ 8
=> 2

Всё работает как и ожидалось. Но вот вы решили, что хорошо бы иметь лог того, что происходит с этой функцией:

half x = (x `div` 2, "Я только что располовинил  " ++ (show x) ++ "!")

Что ж, отлично. Но что будет если вы теперь захотите применить half несколько раз?

half . half $ 8

Вот то, что мы хотели бы, чтобы происходило:


Спойлер: автоматически так не сделается. Придётся всё расписывать ручками:

finalValue = (val2, log1 ++ log2)
    where (val1, log1) = half 8
          (val2, log2) = half val1

Фу! Это ни капли не похоже на лаконичное

half . half $ 8

А что, если у вас есть ещё функции, имеющие лог? Напрашивается такая схема: для каждой функции, возвращающей вместе со значением лог, мы бы хотели объединять эти логи. Это побочный эффект, а никто не силён в побочных эффектах так, как монады!

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

Вас ждет много анализа и немного частных производных. Код прилагается.
Прошу под кат!

31 августа 2012 года японский математик Cинъити Мотидзуки опубликовал в интернете четыре статьи.

Заголовки были непостижимы. Объём был пугающим: 512 страниц в сумме. Посыл был дерзким: он заявил, что доказал abc-гипотезу, знаменитую, соблазнительно лёгкую числовую теорию, которая десятилетиями заводила математиков в тупик.

Затем Мотидзуки просто ушёл. Он не отправил свою работу в Annals of Mathematics. Он не оставил сообщение ни на одном сетевом форуме, которые часто посещают математики со всего мира. Он просто опубликовал статьи и ждал.

Два дня спустя, Джордан Элленберг, профессор математики в Висконсинского университета в Мадисоне, получил почтовое оповещение от Google Scholar, сервиса, который сканирует интернет в поисках статей по указанным темам. Второго сентября Google Scholar отправил ему статьи Мотидзуки: «Это может заинтересовать вас».

«А я такой: „Да, Гугл, мне это как бы интересно!“» – вспоминает Элленберг, – «Я запостил их в Фэйсбуке и в моём блоге, с пометкой: „Между прочим, похоже, что Мотидзуки доказал abc-гипотезу“».

Интернет взорвался. В течение дней даже далёкие от математики СМИ подхватили историю. «Решена сложнейшая в мире математическая теория», – объявила Telegraph. «Возможный прорыв в abc-гипотезе», – немного скромнее писала New York Times.

На математическом форуме MathOverflow математики со всего мира стали оспаривать и обсуждать заявление Мотидзуки. Вопрос, который быстро стал самым популярным на форуме был прост: «Кто-нибудь может объяснить философию его работы и прокомментировать почему она может пролить свет на abc-гипотезу?» – спросил Энди Путман, ассистент профессора в Университете Райса. Или, если перефразировать: «Я ничего не понял. Кто-нибудь понял?»

Проблема, с которой столкнулись многие математики, сбежавшиеся к сайту Мотидзуки, была в том, что доказательство было невозможно прочесть. Первая статья под заголовком «Интер-универсальная теория Тейхмюллера 1: Построение театров Ходжа», начинается с утверждения, что цель работы в «разработке арифметической версии теории Тейхмюллера для цифровых полей ограниченных эллиптической кривой… с помощью применения теории полуграфов анабелиоидов, фробениоидов, эталь тета-функций и логарифмических оболочек».

Это похоже на тарабарщину не только для обывателя. Это было тарабарщиной и для математического сообщества.

«Смотря на неё, ты чувствуешь будто читаешь статью из будущего или далёкого космоса», – написал Элленберг в своём блоге.

«Она очень, очень странная», – говорит профессор Колумбийского университета Йохан де Йонг, работающий в близких сферах математики.

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

Как профессор Мун Дучин из университета Тафтса выразила это: «Он воистину создал свой собственный мир».

Должно пройти долгое время прежде чем кто-нибудь будет способен понять работу Мотидзуки, тем более оценить верность доказательства. В последующие месяцы статьи лежали камнем на плечах математического сообщества. Горстка людей подобралась к ним и начала изучать. Другие пытались, но быстро сдались. Некоторые полностью игнорировали их, предпочитая наблюдать издалека. Что же до виновника беспокойства, человека, который заявил, что решил одну из величайших проблем математики – от него не было ни звука.

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

Предположим, что у вас есть несколько объектов и вам нужно узнать нет ли между ними столкновений. Простейшим решением будет посчитать расстояние от каждого объекта до всех остальных объектов. Однако, при таком подходе количество необходимых вычислений растёт слишком быстро. Если на десятке объектов приходится делать сотню проверок, то на сотне объектов выходит уже десяток тысяч проверок. Это и есть печально известная квадратичная сложность алгоритма.