Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

В этой статье я попробую ответить на такие вопросы:

• может ли один доклад умного человека сделать другого человека одержимым?
• как окунуться в машинное обучение (почти) с нуля?
• почему не стоит недооценивать многоруких бандитов?
• существует ли серебряная пуля для a/b тестов?

Ответ на первый вопрос будет самым лаконичным — «да». Услышав это выступление bobuk на YaC/M, я восхитился элегантностью подхода и задумался о том, как бы внедрить похожее решение. Я тогда работал продуктовым менеджером в компании Wargaming и как раз занимался т.н. user acquisition services – технологическими решениями для привлечения пользователей, в число которых входила и система для A/B тестирования лендингов. Так что зерна легли на благодатную почву.

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

В сентябре прошлого года мы порадовали вас новостью о начале программы публичного превью (Public Early Access Program) нашей новой кросс-платформенной IDE для разработки на C и C++ — CLion. А уже сегодня мы готовы сказать — релиз CLion 1.0 состоялся! За два года от первого (полушутливого) объявления о начале разработки C++ IDE мы прошли огромный путь — переосмыслили свои навыки и умения по работе с кодом на C++, дружно освоили CMake, расширили команду, протестировали CLion на десятках больших проектов на C и C++.

Но самое главное — это каждодневная поддержка C++ коммьюнити, которое (спасибо вам!) приняло нас очень благосклонно. Спасибо за слова поддержки, репорты багов, предложения новых фич, сотни ретвитов и репостов наших новостей и анонсов! Сегодня мы готовы показать вам и рассказать, что же вошло в CLion 1.0.

Данная статья продемонстрирует возможность легко написать свою нейронную сеть на языке Javа. Дабы не изобретать велосипед, возьмем уже хорошо проработанную библиотеку Fast Artificial Neural Network. Использование нейронных сетей в своих Java-проектах — реально. Часто можно услышать упреки в адрес Java касательно скорости выполнения. Хотя разница не так велика — подробно об этом можно узнать в публикации «Производительность C++ vs. Java vs. PHP vs. Python. Тест «в лоб»». Мы будем использовать обертку вокруг библиотеки FANN.

Эта публикация о том, как можно в Windows скомпилировать библиотеку для обработки видео и аудио FFmpeg под Android в Eclipse с помощью NDK. Вы узнаете, как связать FFmpeg с библиотекой для обработки изображений OpenCV и как это всё можно использовать в Java-коде Android приложения. Всё это будет рассказано в контексте процесса создания Android приложения, основной функционал которого как раз и завязан на использовании этих библиотек и их взаимодействии. Итак, заинтересованных прошу под кат.

Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

Привет. Из названия темы вы могли заметить, что речь пойдет о том, как устроены Tasks и Back Stack в Android. Эта статья будет являться свободным переводом официального источника. Тема больше ориентирована на новичков, но я думаю, что и опытный разработчик сможет узнать что-то новое, т.к. тема специфична и не часто приходится кастомизировать поведение наших Activity.

Вот такими словами начинается комментарий к свежему коммиту в master-ветку Go:

This change deletes the C implementations of the Go compiler and assembler from the master branch.

(«Эти изменения удаляют C-реализацию компилятора и ассемблера Go из главной ветки»)

Эти слова — труд почти года работы команды Go по переписыванию компилятора с C на Go. Это был на 90% автоматический процесс. Теперь Go компилирует сам себя.

Зачем это было нужно и чуть больше подробностей под катом.


Картинка: Твиттер Russ Cox

Чтобы направить всю энергию системы в необходимом направлении, нужно эту систему ограничить правилами.

Привет, Хабр! Продолжаем серию статей об архитектурном дизайне мобильных приложений. Под катом поговорим о проектировании слоёв UI. Добро пожаловать!

Всем привет! Я — начинающий свифтер, то есть изучаю Swift без опыта ObjC. Недавно мы с компаньонами начали проект, требующий приложение под iOS. А еще у нас есть idée fixe: с нами непременно должен работать студент из Физтеха, а приложение должно быть написано на языке Swift. И вот, пока мы ищем физтеховцев и знакомимся с ними, я решил не терять время и параллельно начать своими силами пилить проект на Swift. Так я впервые открыл XCode.

Вдруг обнаружилось много знакомых, которые точно так же не имея опыта мобильной разработки, стали осваивать ее именно посредством Swift, а не ObjC. Кто-то из них подтолкнул меня поделиться опытом на Хабре.

Итак, вот топ пять «ловушек», своевременное понимание которых точно бы сэкономило мне время.

Мне было немного странно видеть, что в таком замечательном ресурсе мало обсуждения и самой темы о торговых марках, то есть наименовании IT продуктов и компаний (“торговой марки”, “торгового наименования”, “ТМ”, “trademark”). Очевидно, что любой программист и участник IT рынка (а особенно те, кто пишут свои продукты), рано или поздно столкнется с этим вопросом. Поэтому, чем раньше IT-шники об этом будут задумываться, тем меньше будет проблем в их бизнесе в будущем.

Итак, постараемся восполнить пробел и открыть тему торговых марок. Очевидно, что с точки зрения программирования легко повторить и tetris, и facebook, и любые «фермы». Но попробуйте раскрутить свой продукт (клон он или нет) с похожими на эти продукты названиями — тут же владельцы (вернее их юристы) вас закроют со всех ресурсов. С другой стороны, если ваш продукт становится популярным, то тут же назревает необходимость защитить его от клонов и сделать так, чтобы другие не использовали и не забивали вашу марку в свои ключевые слова. Если коротко — это и есть причина, по которой торговая марка выступает одним из основных параметров оценки и стоимости любого IT проекта при его финансировании, продаже и заключении солидных контрактов.

Цель данной статьи — показать возможный подход для построения микросервисов с использованием Scala, RESTful JSON, Spray и Akka. В качестве базы данных мы будем использовать MongoDB. В результате нашей работы мы упакуем наш проект в Docker-контейнер, а Vagrant и Ansible позволит нам управлять конфигурацией приложения.

В этой статье вы не найдете подробностей о языке Scala и других технологиях, которые будут использоваться в проекте. В ней вы не найдете руководства, которое ответит на все ваши вопросы. Цель статьи — показать технику, которую можно использовать при разработке микросервисов. На самом деле, большая часть этой статьи не завязана на конкретной технологии. Docker имеет более широкую сферу использования, нежели только микросервисы. Ansible позволяют быстро развернуть любое требуемое окружение, а Vagrant — отличный инструмент для создания виртуальных машин.

В конце октября прошлого года ребята из твиттера запустили Fabric. До сих пор информации о Fabric на русском языке в сети не было, поэтому я решил на примере объяснить, как все работает на примере авторизации, ленты твитов, добавлении твита и выходе из аккаунта.

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

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

Р. Брэдбери

UPDATE: Parse не будет работать к 2017 году.

Введение

В статье описан Backend-as-a-Service подход к хранению и обработки данных. Рассказаны преимущества и недостатки представителя такого подхода — сервиса parse.com. Коротко представлен сервис аутентификации пользователей через соц. сети uLogin. Основное назначение — показать, как эти два сервиса могут взаимодействовать, чтобы проект не требовал регистрации пользователей по логину и паролю, но в то же время сохранилась возможность авторизации пользователей к действиям над объектами.

О BaaS и parse.com

Parse.com — один из самых популярных провайдеров backend-as-a-service (BaaS). BaaS подход позволяет не поднимать свой сервер для хранения и обработки данных приложения. Это используется в мобильных разработках и в обычном вебе. Parse.com имеет свои SDK под несколько платформ, в том числе серверных. Но я расскажу о javascript.

Возможность работать с базой данных через javascript, не поднимая свой сервер, открывает отличные возможности, например, для Single page application (SPA), которое можно хостить на Github Pages, Bitbucket и многих других бесплатных. Первый вопрос, который у меня возник, когда я услышал про работу с БД из клиентского кода — это разграничение прав доступа, так как ключи общеизвестны. Изучив документацию parse.com, я выяснил, что для этого используется авторизация пользователей. Каждый пользователь имеет свой логин и пароль. SDK имеет методы регистрации нового пользователя по логину и паролю, аутентификации по этим же данным. Можно добавить email, при этом сам parse.com умеет отправлять настраиваемые письма для верификации email.

Доброго времени суток, уважаемые хабровчане! Сегодня я хотел бы поговорить о том, как не имея особого опыта в машинном обучении, можно попробовать свои силы в соревнованиях, проводимых Kaggle.



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

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

Здравствуйте, меня зовут Дмитрий Карловский и я… много думал. Думал я о том, что не так с XML и почему его в последнее время променяли, на бестолковый JSON. Результатом этих измышлений стал новый стандарт формат данных, который вобрал в себя гибкость XML, простоту JSON и наглядность YAML.

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

Больше — лучше	JSON	XML	YAML	INI	Tree
Человекопонятность	3	1	4	5	5
Удобство редактирования	3	1	4	5	5
Произвольная иерархия	3	3	3	1	5
Простота реализации	3	2	1	5	5
Скорость парсинга/сериализации	3	1	1	5	5
Размер в сериализованном виде	3	1	4	5	5
Поддержка поточной обработки	0	0	5	5	5
Бинарная безопасность	3	0	0	0	5
Распространённость	5	5	3	3	0
Поддержка редакторами	5	5	3	5	1
Поддержка языками программирования	5	5	3	5	1

Это третья статья в цикле «Теория категорий для программистов».

Категория типов и функций играет важную роль в программировании, так что давайте поговорим о том, что такое типы, и зачем они нам нужны.

Кому нужны типы?

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

Компания, где я работаю, разрабатывает программное обеспечение на C++ под Linux. Долгое время мы использовали Qt Creator, с редкими ребятами работающими из Emacs и Vim. Когда я сам попытался пересесть на Vim, я понял, что ситуация с плагинами для разработки на С++ очень не простая. Поработав немного с CTags, я быстро понял, что без напильника работать в Vim будет очень сложно.
К сожалению, с ростом опыта работы с Vim редактор в Qt Creator в режиме эмуляции устраивал меня все меньше, и в какой-то момент я решил потратить немного времени и разобраться, как же сделать из Vim нормальную среду.
Я очертил для себя четыре вещи, которые я бы хотел от среды разработки, и которых мне бы хватило в Vim, чтобы полностью на него перейти:

1. Автодополнение
2. Навигация по коду
3. Отладка прямо из среды
4. Интеграция с Git (в частности Blame прямо в редакторе, и Git Grep)

Автодополнение в Vim — это решенная проблема, и название у решения YouCompleteMe. Это очень качественный плагин, который реализует автодополнение для большого количества языков программирования, в частности Python и C++. Ходят слухи, что внутри Google YouCompleteMe решает и вторую проблему с навигацией кода, но использует для этого внутренные инструменты гугла для индексирования.

Интеграция с Git в какой-то степени решена с помощью vim-fugitive. Это не такая комплексная интеграция, как бывает у Jet Brains, или в Visual Studio, но сравнимая с тем, что предлагает Qt Creator. Те два сценария, которые нужны были мне: blame и grep — работают хорошо.

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

Сегодня мы рассмотрим алгоритм TILT (Transform Invariant Low-rank Texture) и множество его методов применения в области Computer Vision. Статья будет нести несколько обзорный характер, без плотного углубления в математические дебри.