Тим Петерс разработал гибридный алгоритм сортировки 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 есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

http://habrahabr.ru/post/251751/

Поздравляем вас с наступившей весной новым дайджестом о мобильной разработке и маркетинге. В нем несколько материалов о Swift-е, создание игры за выходные, новый Xcode и Android для работы, реклама в Google Play и новые часы Pebble, рвущие Kickstarter.

Читать дальше →

http://habrahabr.ru/post/251805/

В только что вышедшем релизе Krita 2.9 был реализован один из проектов, выполенных в рамках Google Summer of Code 2014, над которым работал студент из Индии Мохит Гоял (Mohit Goyal). Это был достаточно сложный проект, поэтому предлагаем Вам краткое руководство по использованию новых функций: черновые профили кистей, заблокированные настройки и накопительная отмена!



Перевод статьи: Ксения Кузяева
Читать дальше →

http://habrahabr.ru/post/251803/

Видео, подкасты

js-must-watch
perf-tooling
The Web's Future is Offline
Reflux — Creating Your First Action in React
JS Jabber #147: io.js with Isaac Schleuter and Mikeal Rogers
RadioJS №18
Live Editing React with Amok
What the… JavaScript?
Читать дальше →

http://habrahabr.ru/post/251801/

Доброго времени суток, уважаемые хабравчане. За последнее время я увидел несколько интересных и полезных инструментов/библиотек/событий, которыми хочу поделиться с Хабром.

Unheap

Огромная коллекция реально качественных и нужных jQuery плагинов, грамотно расфасованная по области применения. В Unheap 5 основных разделов UI, Inputs, Media, Nav, Other и каждый из них содержит еще с десяток подкатегорий. В общей сложности на данный момент каталог содержит более 1000 различных плагинов.

Читать дальше →

http://habrahabr.ru/post/251077/

В один прекрасный день я обнаружил, что narod.ru, наше все в области истории рунета и неисчерпаемый кладезь вырвиглазных сайтов, продался! Ucoz купил его. Невелика беда, подумал я, после того как перерегистрировал все свои старые сайты под ucoz и на время забыл о проблеме. Но вот недавно узнав о существовании изобилия генераторов статических сайтов я принял решение сделать еще один сайт ни о чем. Какого же было мое удивление, когда выяснилось, что Ucoz.ru более не поддерживает загрузку файлов html, обрекая вас использовать его конструктор сайтов помимо воли.

Конечно, можно купить хостинг за пару долларов в месяц, можно найти бесплатный хостинг с perl, php и mysql. Можно даже идти в ногу с достижениями времени и воспользоваться heroku или google app engine, получив в нагрузку еще и поддержку передовых языков программирования. Но все это не то. Нет души. Разве может сравниться ламповая закачка обновлений по FTP с бездушной публикацией нажатием одной кнопки в Wordpress? Не может. Именно поэтому давайте посмотрим где и как сегодня можно сделать статический сайт. Читать дальше →

http://habrahabr.ru/post/251797/

Вступление

Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.

Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.

Надеюсь что эта статья будет полезна:
1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science
2. Профессионалам, которые хотят закрыть «дыры» и пробелы
3. Может кто-то из преподавателей возьмет на заметку для своих курсов.
4. Студентам, аспирантам американских вузов — хотелось бы тоже получить фидбэк, особенно касается последних трендов в образовании

Что же здесь будет написано? Минимум философии и общих мыслей: конкретная программа undergraduate и graduate курсов, конечно из дисциплин наиболее мне близких. Все курсы были лично прочувствованы на собственной шкуре, по этому и пишу. (Я пытался записаться на все интересные курсы, которые были, но мой основной упор — системное программирование, базы данных и искусственный интеллект. Отсюда конечно некий bias, но пытаюсь предложить более-менее универсальную программу).

Читать дальше →

http://habrahabr.ru/post/251747/

Кто умеет копировать, тот умеет ДЕЛАТЬ. Это сказал Леонардо да Винчи. Видите ли, вы исходите из своих представлений, о том, что такое ХР, винда, операционка. Люди как рассуждают:

— Мне было ещё мало лет у меня стояла ХР, вот были золотые деньки, но тепереча не то, что давеча. Новые времена, современное ПО. Не понимаю, зачем копаться в старье? Вы бы хоть делали клон десятой винды, но куда с вашей то скоростью, вы его сделаете лет через 100.

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

http://habrahabr.ru/post/251793/

Зима в проекте КолибриОС выдалась на редкость плодотворной: добавлено много мелких, но очень полезных в повседневной работе программ; улучшен пользовательский интерфейс некоторых существующих программ; исправлены ошибки в сетевой и звуковой подсистеме; и многое другое. Кроме того, зимой мы провели новогодний конкурс по написанию игр под нашу операционную систему. В сумме было написано 10 игр, о которых вы можете прочитать здесь. Подробности всех изменений и исправлений под катом. Читать дальше →

http://habrahabr.ru/post/239033/

Два с половиной часа в поезде – прекрасное время для того, чтобы написать благодарность организатору конференции Сергею Платонову (sermp) и его команде за то, что наконец-то в России появилась конференция про C++! Заслуги Сергея поистине впечатляют, учитывая то, что он не обладал бюджетами Microsoft и Intel. Однако оказалось, что главное не бюджет, а желание и энтузиазм. Поэтому собранные Сергеем докладчики были выше всяческих похвал, иностранные гости – крайне общительны и любезны. А на стендах JetBrains, IncrediBuild, Kaspersky и PVS-Studio собрались не говорящие головы, а профессионалы, с которыми интересно было общаться и гостям, и соседям по стенду. Наши личные впечатления – под катом.

Читать дальше →

http://habrahabr.ru/post/251777/

Многие пользователи utorrent переходят на новые версии программы по привычке или до того момента пока у них не перестаёт что-то работать. Кто-то остановился на 2.2.1 или 2.0.4 как последних более-менее стабильных, а кто-то по сей день верен 1.8.2 и даже 1.7.7. Чем же так пугает и привлекает третья версия utorrent? Попробуем проследить и разобраться в изменениях которые были и тех, что ожидают нас в будущем.


Читать дальше →

http://habrahabr.ru/post/251625/

Коммитом 66418 была фактически завершена основная часть работ по модернизации графической оболочки ReactOS, и теперь она очень сильно напоминает файловый эксплорер из Windows 2000. После этого Giannis Adamopoulos посчитал работу над новым проводником в целом завершённой и закрыл баг-репрорт класса «эпик» CORE-7330. Основной разработчик новой оболочки, David Quintana, помимо контрактных денег получил ещё и постепенно собранные через Bountysource 100$.

Скриншоты

http://habrahabr.ru/post/251757/

Сервисом top$dev было проведено исследование стран Восточной Европы по собственной методике на основе данных крупнейших фриланс-бирж (oDesk, Elance, Freelancer и других): более 88 тысяч профилей фриланс-разработчиков и 260 тысяч проектов на общую сумму более $350 млн.
Краткие выводы:
Читать дальше →

http://habrahabr.ru/post/251753/

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

Описание

Данный дисплей имеет разрешение 132 x 176 пикселей и даёт возможность работать с тремя цветовыми палитрами 16(6-5-6), 12(4-4-4) и 8(3-3-2) бит.
Читать дальше →

http://habrahabr.ru/post/251629/

Как-то незаметно прошел анонс новой версии MongoDB. Изменение номера версии с 2 на 3 указывает на значительные изменения внутри базы данных. Разработчики заявляют о значительном увеличении производительности и улучшении маштабируемости. Немного подробнее под катом.

Читать дальше →

http://habrahabr.ru/post/251745/

Мы в rangle.io давно увлекаемся функциональным программированием, и уже опробовали Underscore и Lodash. Но недавно мы наткнулись на библиотеку Ramda, которая на первый взгляд похожа на Underscore, но отличается в небольшой, но важной области. Ramda предлагает примерно тот же набор методов, что и Underscore, но так организовывает работу с ними, что функциональная композиция становится легче.

Разница между Ramda и Underscore – в двух ключевых местах – каррирование и композиция.
Читать дальше →

http://habrahabr.ru/post/251729/

В наше время при помощи JavaScript и HTML можно сделать практически всё. А благодаря Node-WebKit (недавно переименован в NW.js) можно делать даже десктопные приложения, которые выглядят, как нативные и имеют доступ ко всем частям ОС. Сегодня мы покажем, как создать простое десктопное приложение при помощи Node-WebKit, используя jQuery и несколько модулей для Node.js.

Node-WebKit — комбинация Node.js и встроенного браузера WebKit. Код JavaScript выполняется в особом окружении, из которого есть доступ и к стандартному API браузеров, и к Node.js.
Читать дальше →

http://habrahabr.ru/post/251723/

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

Вообще, мы довольно давно думали над этим и присматривались к вашим дискуссиям, но решающим событием стала публикация про «несанкционированныи

http://habrahabr.ru/post/251711/

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

В конце концов люди начали спрашивать нас: «Как вы создаете GIF анимации?». Пришло время раскрыть секрет.
Читать дальше →

http://habrahabr.ru/post/251709/

Привет, Хабр. Хочу поделиться историей из жизненного опыта. Несколько месяцев назад я записался на платные курсы по изучению языка программирования JavaScript в прекрасном городе Минск. Потратил около недели времени на подробное изучение отзывов о каждой из компаний на рынке, сравнивал цены на услуги и местоположение относительно моего дома. Наконец, выбрав «достойного» кандидата, направился к ним в офис для заключения договора. В общем, прошел я начальный инструктаж, получил расписание занятий и содержание всего курса и с радостью приступил к делу.
Читать дальше →

http://habrahabr.ru/post/251705/