Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Arduino — это хорошо, когда хочется быстро реализовать идею, не заморачиваясь мелочами. Но когда идея проверена, лишняя функциональность начинает просто мешать.
Собирая робота на гусеничном шасси, я столкнулся с тем, что бутерброд из Arduino + MotorShield + Sensor Shield плюс ко всему аккумулятор и прочие компоненты обросли проводами и стали с трудом помещаться на не самом крошечном шасси. Городить еще кучу шилдов, чтобы избавиться от лишних проводов не хотелось.
Появилась идея избавиться от всего, что в Arduino не требуется в готовом девайсе. Попутно хотелось снизить стоимость робота.
Многих интересующихся электроникой отпугивает еще и стоимость Arduino в магазинах. С ebay и китайских магазинов посылка идет долго, изобретательский пыл успевает остыть, поэтому приобретение откладывается «на потом», «когда сын подрастет». Поэтому я решил собрать Arduino-совместимую плату из деталей, которые всегда можно купить в городе.
В итоге я получил Arduino-совместимую плату, стоимостью в 210 рублей на макетной плате и в ~270 рублей в готовом для наращивания функционала виде.

«Minimalist Arduino»
С нуля до полной готовности собирается с дешевым 40Вт паяльником за 1 выходной без каких-то особых навыков.

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

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

Но сейчас я пришел к выводу, что это утверждение всё же верно.

Вводная

C++ является «небезопасным» («unmanaged») языком, поэтому программы могут «вылетать» — аварийно завершать работу без сохранения данных пользователя, сообщения об ошибке и т.п. — стоит только, например, залезть в не инициализированную память. Например:

void fall()
{
  char * s = "short_text";
  sprintf(s,"This is very long text");
}

или

void fall()
{
  int * pointer = NULL;
  *pointer = 13;
}

Всем было бы лучше, если бы мы могли «отловить» падение программы — точно так же, как в java ловим исключения — и выполнить хоть что-то перед тем, как программа упадет (сохранить документ пользователя, вывести диалог с сообщением об ошибке и т.п.)

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

Начиная рабочий проект под Linux, я застрял в поисках С++ библиотеки, которая бы 1) была free, 2) умела работать с сокетами и можно быстро было поднять свой сервер, 3) нужна была оббёртка над потоками для плюсов. Сперва я наткнулся на Qt, но через некоторое время Qt стал слишком тяжелым для поставленной цели. В итоге поиски подтолкнули к cxxtools.

Кратко

Кратко о том, что умеет делать библиотечка:

• умеет работать с TCP сокетами и поднимать на их основе слушающий сервер;
• умеет парсить http запросы и отдавать ответы;
• умеет работать с SSL;
• реализован быстрый механизм сигналов (как раз похожий на Qt);
• имеется похожий на boost-овский, но более удобный шаблон Function / Method; необходим для callback-функционала
• умеет работать с потоками (threads): attached и detached threads;
• удобный шаблон пула (pool);
• гораздо удобнее smart pointer (ну имхо конечно), чем тот же std::smart_ptr и auto_ptr. Позволяет использовать разные политики управления классом и подсчёта ссылок, что удобно и необходимо для многопотоковых реализаций
• удобный механизм логирования
• ini-парсер

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

Неспособность рассуждать о коде

«Рассуждать о коде» значит понимать порядок исполнения инструкций («исполнять программу в голове»), зная, каково предназначение кода.

Симптомы

• Наличие «волшебного», «вуду» кода или кода, который не имеет никакого отношения к целям программы, но всё равно тщательно поддерживается (например, инициализация переменных, которые никогда не используются, вызов функций, не имеющих отношения к цели, создание выходных данных, которые не используются, и т.д.).
• Многократные вызовы идемпотентных функций (например, вызов save() по нескольку раз, «чтобы уж точно»).
• Исправление ошибок написанием избыточного кода, который замещает данные, полученные при исполнении неисправного кода.
• «Йо-йо код», который конвертирует значения в различные представления, а потом конвертирует их обратно ровно в то же представление, с которого начинали (например, преобразование десятичного числа в строку, а потом обратно в десятичное число, или padding строчки с последующим trim'ом).
• «Бульдозерный код», который создает впечатление рефакторинга посредством разбития кусков кода на процедуры, которые, правда, затем невозможно использовать где-либо еще (высокая когезия).

К написанию сей заметки меня сподвигло то, что я устал делать развёрнутые замечания на эту тему в комментариях к статьям, где в качестве части инструкции по сборке и настройке чего-либо для конкретного дистра предлагают выполнить make install.

Суть сводится к тому, что эту команду в виде «make install» или «sudo make install» использовать в современных дистрибутивах нельзя.

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

Добрый день, уважаемые хабровчане!

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

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

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

Алгоритмы и концепции

Сортировка и поиск

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

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

• Структуры данных
• Алгоритмы и «концепции»
• Язык программирования

Аббревиатура OFDM расшифровывается как Orthogonal frequency-division multiplexing. В русскоязычной литературе встречается несколько различных переводов, несущих, в принципе, один смысл: OFDM — это механизм мультиплексирования (уплотнения) посредством ортогональных поднесущих.

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

Иллюстраций: 18, символов: 27 399, строк кода: 99.

Возникла необходимость как-то и куда-то бэкапится. Причём чтобы процессоры не грузились и место не занималось, а бэкапы ротэйтились и удобно доставались. Раньше всегда пользовался fsbackup, но захотелось отказаться от архивирования. Для решения задачи была использована rsync и механизм жёстких ссылок (так называемых хардлинков) файловой системы.

Архитектура: есть отдельно стоящий сервер с большим винтом — на нём и работает скрипт. Есть много разных серверов с доступом по ssh, на которых в ~/.ssh/authorized_keys добавлен публичный ключ пользователя, под которым работает скрипт резервного копирования.

Прослушивать английские слова и фразы на веб-страницах?
Переводить и моментально добавлять их в личный словарь?
Просматривать словарные статьи в известных онлайн-словарях?
Легко!
Официальное расширение LinguaLeo доступно для установки в Google Web Store.

Ferm — это низкоуровневая надстройка над iptables, позволяющая организовывать своего рода циклы по спискам параметров iptables. Это оказывается особенно полезно при настройке сложных правил файрвола, для написания которых с использованием одного только iptables приходится повторять до умопомрачения -t filter -A INPUT -p tcp --state NEW ..., потом делать аналогичное для -p udp, в общем кто плавал — знает.

Ferm прекрасен тем, что, сохраняя всю гибкость iptables, позволяет добиваться тех же эффектов меньшими усилиями. Так, например, разрешить новые соединения на порты ftp, ssh и http и запретить все остальное (кроме связанных), можно написать вот такой конфиг:
chain INPUT {
policy DROP;
mod state state (RELATED ESTABLISHED) ACCEPT;
proto tcp dport (http ftp ssh) ACCEPT;
}

Удивительно дело, поиск дает по запросу ferm только одну статью, которая к собственно ferm никакого отношения не имеет. То ли все уже все знают и всем очевидно, то ли наоборот. Исходя из последнего, я решил написать этот топик.

В первой части я рассказал как настроить Android смартфон для работы с SL4A (Scripting Layer for Android), показал как вызывать системные всплывающие окна, получать из них введенную пользователем информацию и выводить в них результат работы. В этой же части я расскажу о построении интерфейса к приложению с помощью WebViews. Если коротко, то WebViews это способ построить интерфейс приложения с помощью HTML, JavaScript и CSS. Если учесть, что в Android смартфонах полнофункциональный webkit, то построение интерфейса не такая уж и проблемная задача.

Я очень люблю язык программирования Python и так же люблю Android OS. Для меня было приятным открытием, что для этой ОС существует полноценный интерпретатор Python, но я постоянно откладывал знакомство с ним. В этой статье я хочу рассказать про основные принципы программирования на этом языке под эту ОС.

Посмотрев на цены готовых ардуин в нашей стране я пригорюнился.
Но потом задался вопросом… А какого черта?! Ведь там используются обычные AVR микроконтроллеры, доступные россыпью на радио рынке за нормальную стоимость.
А почему бы не собрать свое и не сидеть на готовеньком?
Тем, кому интересен процесс сборки и настройки своей простейшей Arduino, прошу под кат.

На Хабре уже есть несколько статей\переводов, в которых рассказывается о неизвестных фичах\тонкостях\возможностях Пайтона. Я буду пытаться не повторять их, а дополнять, но если уж так случилось, что вы это уже где-то видели — не огорчайтесь. Я уверен, что найдется что-то интересное и для вас.