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

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

Все примеры приведены на Java, но содержат комментарии и я надеюсь будут понятны программистам не знакомым c Java. Данная статья носит обзорный характер и не претендует на полноту. В то же время она наполнена ссылками, которые дают более подробное объяснение терминам и утверждениям.

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

Продолжим разговор о нейронах-детекторах. Предположим, на зону коры посредством волновых туннелей проецируется некая информация. Каждый из проекционных пучков – это аксоны нейронов, расположенных на той зоне, которая эту информацию посылает. Проекция снимается с малого по площади участка коры. Волокна проекционного пучка, по сути, транслируют проходящие по этому участку волновые картины. То место принимающей коры, куда приходится проекция, само становится источником волн. Эти волны несут на принимающей зоне коры ту же информацию, что и волны на исходной зоне.

Если мы настроим веса какого-либо нейрона на узнавание определенного волнового узора, проходящего по его рецептивному полю, то мы превратим его в детектор, срабатывающий в тот момент, когда появляется характерное для него сочетание идентификаторов.

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

Как проект может отстать на год?
… по дню «за раз»
…Фред Брукс

Идея написать пост появилась в связи с тем, что в последнее время приходится сталкиваться со следующий кейсом: Руководители проектов стараются поддерживать процессы, соблюдать предписания методологий, собирать метрики, поддерживать высокую мотивацию на проекте. Но приходит время очередной проверки результатов работы (milestones, deliverables) и оказывается, что степень завершенности проекта отстает от плановой, что неминуемо приведет к срыву сроков. И руководитель проекта, стараясь устранить угрозу как можно раньше, озвучивает ее команде, а далее просто пытается ускорить процесс напутствующим словом и частным мониторингом, что без определения причин редко работает.

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

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

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

Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации.

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

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

Функциональность LINQ запросов в C# переписана на PHP. Изначально библиотека задумывалась как тренинг, так как подобные библиотеки уже существуют, но потом было решено её опубликовать для всех. Скопировать LINQ на PHP один в один невозможно, поскольку возможности языков C# и PHP очень разные. Отличительной возможностью предлагаемого решения является ориентация на итераторы, ленивые лямбда выражения и сигнатура LINQ методов, идентичная C# на сколько это возможно. Все стандартные LINQ методы, естественно, реализованы. Описание возможностей проекта с объяснением причин, почему именно такое решение было выбрано, под катом.

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

Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ — много времени, которого часто нет, становится всё ещё печальнее.

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

Пролог

Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга, она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь.

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

Моему сыну, как и многим мальчишкам, нравятся автомобили. Причём чем они больше и необычнее — тем больше нравятся. Когда мы идём по улице, а мимо проезжает эвакуатор или снегоуборочная машина, он неизменно дёргает меня за руку, указывает на заинтересовавший его объект и говорит: «Папа, б-р-р!». Говорит он так потому, что ему один год и вышеуказанные два слова составляют 40% его словарного запаса. Тем ни менее, в общем мысль понятна — обратить внимание на автомобиль. Давайте подумаем, каким образом ребёнок в возрасте 8-10 лет сказал бы своему сверстнику то же самое. Что-то вроде «Ух ты, смотри какая крутая тачка!», да? Мысль та же, но обратите внимание — уже шесть слов вместо двух. И, наконец, представьте, каким образом то же самое скажет человек лет в тридцать: «Эй, смотри, да это же Ferrari California 2008-го года выпуска с двигателем V8 мощностью в 454 лошадиных силы и 7-ми скоростной коробкой-автоматом! Она до сотни разгоняется за 3.9 секунды!». Да, здесь уже больше деталей, но, если вы не автомеханик или фанат Ferrari — они вам скорее всего не нужны и не важны. Основная же мысль — всё та же, что и в «Ух ты, смотри какая крутая тачка!» или «Папа, б-р-р!». Но выражена она уже в 30 слов.

Вы заметили, как абстракция «интересный автомобиль» обросла деталями и нюансами, стала занимать существенно больше места в тексте и времени на понимание, анализ и ответ? То же самое происходит и с программным кодом.

Я работаю в Яндексе, у Яндекса есть карты, а у карт есть API. API – вещь, которая позволяет встроить карты Яндекса на свой сайт. С версии 2.0 наш API умеет кластеризовать метки на клиенте. Вот как выглядят метки до и после кластеризации:



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

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

Предисловие

Гуляя по англоязычным просторам интернета в поисках решения одной из наболевших тем на работе, наткнулся на очень интересный алгоритм под названием «Fast Threshold Clustering Algorithm». Данный алгоритм кластеризации, что примечательно, появился сравнительно недавно, а именно в ноябре этого года и автором является Дэвид Варади. Ссылка на первоисточник будет доступна в конце статьи.

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

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

Открытые вакансии на должность разработчика в Яндексе есть всегда. Компания развивается, и хороших программистов не хватает постоянно. И претендентов на эти должности тоже хоть отбавляй. Главная сложность – отобрать действительно подходящих кандидатов. И в этом плане Яндекс мало чем отличается от большинства крупных IT-компаний. Так что базовые принципы, описываемые в этой статье, могут быть применимы не только к Яндексу.

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

Если вам понадобится алгоритм сортировки массива, который:

• Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
• Требовал бы O(1) дополнительной памяти;
• Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)

то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N²)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)²) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)²) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан алгоритм со всеми тремя свойствами.

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

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

Agile движение имеет свой взгляд на спецификации. Наиболее экстремальное крыло выражает свои взгляды так:

В жопу спецификации!

Q:

В Facebook используют MySQL зная, что он плохо масштабируется (или здесь какая-то особая магия?). Я хотел спросить, из каких соображений они выбрали MySQL? Используют ли JOIN'ы? И не планируют ли перейти на другую БД?

A:

Отвечает Adam D'Angelo, бывший CTO Facebook, сейчас он развивает свой стартап Quora:

1. Если разбивать данные по разным серверам на уровне приложения, то масштабируемость MySQL не такая уж и большая проблема. На 2008 год, в Facebook [1] у нас было 1800 MySQL серверов для которых требовалось всего два администратора. Конечно, вы не сможете сделать JOIN с данными с разных серверов, но NoSQL-базы вам тоже этого не позволят. Нет никаких данных о том, что в Facebook используют Cassandr'у как основное хранилище, и, кажется, что единственное, для чего она там нужна — это поиск по входящим сообщениям. [2]

HC-128 (pdf) — финалист европейского проекта eSTREAM, поточный шифр с довольно большим внутренним состоянием
(2 независимых массива по 512 32битных слов). Он очень шустрый если шифровать большие потоки, но, поскольку инициализация этих массивов занимает приличное время, не сильно эффективен в пакетном режиме. Справа 6 основных функций, которые в нём используются. Он не перегружен страшными длинными массивами констант, его реализация (под катом) по сравнению с другими выглядит простой и более-менее понятной. Началось всё с того, что меня зацепили две функции f1 и f2