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

• Работал бы гарантированно за 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), в которой описан алгоритм со всеми тремя свойствами.

Robot Odyssey

Нью-йоркский программист Дэвид Ауэрбах (David Auerbach) вспоминает компьютерную игру, для прохождения которой ему понадобилось 13 лет и которая определила его будущее как программиста.

Зарегистрироваться на контест можно будет до 26 мая. Алгоритм 2014 проводится по правилам TCM/Time и состоит из нескольких раундов: разминочного, квалификационного, трёх отборочных и финального. В этом году финальная игра Яндекс.Алгоритма состоится в Берлине в нашем новом офисе. Квалификационные и отборочные туры будут проходить онлайн на платформе Яндекс.Contest в июле.

Впервые Яндекс.Алгоритм прошел в 2011 году и получился очень камерным — он проходил в рамках Летней школы Яндекса по распределённым вычислениям. В прошлом году в нем участвовали уже 3 000 программистов из 84 стран. Среди них были разработчики ВКонтакте, Фейсбука, Google. А победителем стал Геннадий Короткевич, который в тот же год в составе команды НИУ ИТМО победил на чемпионате ACM ICPC.


Офис Яндекса в Берлине

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

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

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

Мы познакомились с Владиславом Архиповым во время питерской конференции WNCONF, где он выступал с докладом. В его выступлении особое внимание уделялось важной для нас теме трактовки gambling для social casino. В ходе разговора, в котором участвовали и другие коллеги, выяснилось, что юридическим моментам в своей работе инди-девелоперы уделяют очень мало внимания, создавая необходимые документы по остаточному принципу. Мы решили восполнить этот пробел и провести вместе с практикующим юристом небольшой “ликбез”.

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

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

Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений примечателен тем, что фактически позволяет получить «векторную» графику на видеоускорителе, причём даром. Одной из первых данный метод растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется особой популярностью, хотя позволяет рендерить прекрасного качества шрифты, используя текстуру всего 256х256 точек. Данный метод прекрасно подходит для современных экранов высокой чёткости и позволяет серьёзно сэкономить на текстурах в играх, он не требователен к железу и прекрасно работает на смартфонах.



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

Как же создавать такие изображения? Очень просто, ImageMagick позволяет сделать это одной командой:

convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png

На этом можно было бы поставить точку, но так полноценного топика не получится. Что ж, под катом — описание быстрого алгоритма расчёта SDF, пример на C++ и немного шейдеров для OpenGL.

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

Вначале определим цели этой реализации:

1. При обнаружении новой версии обновление должно происходить автоматически;
2. После обновления программа должна автоматически перезапускаться;
3. После обновления имя программы должно остаться прежним.

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

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

Впервые она появилась, когда еще никаких практических надобностей для больших сетей не было: в тридцатые годы XX века. На самом деле Штейнер начал ее изучать еще раньше, в XIX веке. Это была чисто геометрическая задача, практические приложения которой стали известны только несколько десятилетий спустя.

Разговор пойдет о той области математики, которая впоследствии выросла в теорию больших сетей и разбилась на несколько областей. Это прикладная отрасль, которая задействует очень много методов из других математических дисциплин: дискретной математики, теории графов, функционального анализа, теории чисел и т.д. Бурное развитие теории больших сетей пришлось на конец девяностых и начало двухтысячных годов. Связано это конечно, с прикладными задачами: развитием интернета, мобильной связи, транспортных задач для больших городов. Кроме того теория сетей используется в биологии (нейронные сети), при построении больших электронных плат и т.п.



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

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

Корутины (Coroutines, сопрограммы) в Unity — простой и удобный способ запускать функции, которые должны работать параллельно в течение некоторого времени. В работе с корутинами ничего принципиально сложного нет и интернет полон статей с поверхностным описанием их работы. Тем не менее, мне так и не удалось найти ни одной статьи, где описывалась бы возможность запуска группы корутинов с продолжением работы после их завершения.
Хочу предложить вам небольшой паттерн, реализующий такую возможность, а также подбор информации о корутинах.

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм SSSP — поиска кратчайшего пути в графе с использованием графических ускорителей. В качестве графического ускорителя будет рассмотрена карта GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Для решения данной задачи на CPU существует, по крайней мере, два известных алгоритма: алгоритм Дейсктры и алгоритм Форда-Беллмана. Так же существуют параллельные реализации алгоритма Дейстры и Форда-Беллмана на GPU. Вот основные статьи, в которых описаны решения данной задачи:

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

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

На хабре незаслужено обойден вниманием замечетальный .Net-фреймворк ServiceStack. Упомянут он очень кратко, в одной лишь статье, и то косвенно, мельком, и в самом конце, и упомянута там лишь мизерная его часть. Очевидно, это связано с тем, что основная масса .Net-разработчиков использует стандартные решения от Microsoft для решения задач по разработке веб-сервисов и веб-приложений, а именно ASP.Net MVC/WebAPI или WCF и не заморачивается. Как мы попытаемся показать в этой статье, современный .Net хорош далеко не только своими стандартными технологиями.



Если интересно, прошу под кат.

Если вы хотите создать игру для Windows 8, но не знаете с чего начать, обязательно подключайтесь к веб-трансляции мероприятия «Создание игр для Windows 8 с использованием Unity3D» 20 февраля в 10:00 (MSK). Мы расскажем вам все самое важное о платформе Microsoft, Windows 8 и Unity3D, а также об инструментах совместной работы, и эти знания помогут вам создать замечательную игру.
Плеер с трансляцией доступен под катом. Смотрите конференцию онлайн и общайтесь в твиттере (#unity3dwin).

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

Если у вас уже есть Pebble, или вы только присматриваетесь к ним, или как раз выбираете себе умные часы — прошу под кат. Я постараюсь рассказать о самых интересных возможностях часов на данный момент и о том, как упростить себе жизнь с помощью умных часов.

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

Это статья попытка показать, что сила функциональных языков и в первую очередь Хаскеля — это в том числе и силе функторов и монад.

Несколько раз начинал писать эту статью и бросал. Бросал потому, что тема, как мне кажется, несколько спорная. Изобретенный мною велосипед может кому-то показаться смешным и нелепым и вообще не совсем корректным. Тем не менее…

Вообще, мне кажется, что в области разработки электронных устройств существует как бы несколько мало пересекающихся миров. Например, существует разработка устройств на базе микроконтроллеров и параллельно существует разработка устройств на базе ПЛИС. Принципы работы этим микросхем принципиально отличаются и точно так же отличаются принципы и методы разработки, используемые языки программирования и отладки. Конечно, выбор элементной базы сильно зависит от поставленной задачи. Однако и так понятно, что эти миры, мир микроконтроллеров и мир ПЛИСов почти не пересекаются. Может быть на стыке технологий что-то есть?

Бац…

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

Но, как говорят гномы, за любой бедой стоит тролль.

                                                                   сэр Терри Праттчетт

Thud! Разумеется, я не мог пройти мимо этой игры. Не только потому, что мне очень нравятся произведения Терри Пратчета, но, главным образом, по той причине, что игра эта ни на что не похожа. Начнем с того, что играется она на восьмиугольной доске. Гномы сражаются с троллями (и последних существенно меньше). Как тролли могут победить, пребывая в меньшинстве? Очень просто — за один ход тролль может снять с доски несколько гномов. А гномам, даже действуя сообща, чтобы снять с доски одного тролля приходится попотеть.

Настольная игра, по произведению Пратчетта, была разработана в 2002 году Тревором Трураном и выпущена в продажу. С того самого момента, как я узнал про эту игру, мне очень хотелось в нее сыграть. Я долго и безуспешно искал ее компьютерную реализацию, но все, что я нашел, это рассуждения о том, что игра эта слишком сложная, чтобы компьютер мог в нее играть. Теперь, у меня есть возможность проверить это утверждение.

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

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