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



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

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

Примерно два года назад я арендовал у одного немецкого хостера не очень мощный сервер на базе Centos 5.2. На нём живут несколько вебпроектов, приносящих некоторую прибыль, и поэтому, я стараюсь присматривать за ним по мере возможности.
На Centos есть стандартный анализатор логов Logwatch, который запускается ежедневно по крону, анализирует содержимое /var/log, делает сводный отчет и присылает его по электропочте. В один прекрасный день я обнаружил в этом отчете запись:

--------------------- yum Begin ------------------------ 
 
 Packages Installed:
    lzo2 - 2.02-3.el5.rf.i386
    dnstracer - 1.8-1.2.el5.rf.i386
    openvpn - 2.0.9-1.el5.rf.i386

---------------------- yum End -------------------------

В тот момент меня она очень смутила, так как в предыдущий день на сервер я не логинился и тем более ничего не устанавливал. Первое, что пришло в голову — сервер был скомпроментирован. Себя я считал уверенным пользователем Linux, однако я растерялся. Благо в тот момент в icq был мой бывший коллега, лучший системный администратор, которого я знаю, и просто очень хороший человек.
Он помог быстро проверить систему. В результате у меня сформировалось краткое HowTo о том, как быстро проверить свой сервер на предмет взлома. Уверен, что многим Храброчитателям оно будет полезно. Предполагается, что пользователь знаком с консолью Linux/Unix.

Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop

Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.

Pipe — что это?

Pipe (конвеер) – это однонаправленный канал межпроцессного взаимодействия. Термин был придуман Дугласом Макилроем для командной оболочки Unix и назван по аналогии с трубопроводом. Конвейеры чаще всего используются в shell-скриптах для связи нескольких команд путем перенаправления вывода одной команды (stdout) на вход (stdin) последующей, используя символ конвеера ‘|’:

cmd1 | cmd2 | .... | cmdN

Например:

$ grep -i “error” ./log | wc -l
43

grep выполняет регистронезависимый поиск строки “error” в файле log, но результат поиска не выводится на экран, а перенаправляется на вход (stdin) команды wc, которая в свою очередь выполняет подсчет количества строк.

Логика

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

Размер буфера начиная с ядра версии 2.6.11 составляет 65536 байт (64Кб) и равен странице памяти в более старых ядрах. При попытке чтения из пустого буфера процесс чтения блокируется до появления данных. Аналогично при попытке записи в заполненный буфер процесс записи будет заблокирован до освобождения необходимого места.
Важно, что несмотря на то, что конвейер оперирует файловыми дескрипторами потоков ввода/вывода, все операции выполняются в памяти, без нагрузки на диск.
Вся информация, приведенная ниже, касается оболочки bash-4.2 и ядра 3.10.10.

Простой дебаг

Утилита strace позволяет отследить системные вызовы в процессе выполнения программы:

$ strace -f bash -c ‘/bin/echo foo | grep bar’
....
getpid() = 13726                   <– PID основного процесса
...
pipe([3,  4])                       <– системный вызов для создания конвеера
....
clone(....) = 13727                <– подпроцесс для первой команды конвеера (echo)
...
[pid 13727] execve("/bin/echo",  ["/bin/echo",  "foo"],  [/* 61 vars */] 
.....
[pid 13726] clone(....) = 13728    <– подпроцесс для второй команды (grep) создается так же основным процессом
...
[pid 13728] stat("/home/aikikode/bin/grep",   
...

Видно, что для создания конвеера используется системный вызов pipe(), а также, что оба процесса выполняются параллельно в разных потоках.

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

Знание истории происхождения вещей и их названий, будь то простой карандаш, автомобиль или команда операционной системы, делает их повседневное использование намного интереснее. В этой заметке я постарался разобраться в причинах странного, казалось бы, наименования некоторых программ, используемых в операционной системе Unix и её родственниках: *BSD, Solaris, HP-UX, Linux и т.д.

Перепечатка моей статьи, написанной, в свою очередь, по мотивам страницы What does {some strange unix command name} stand for?

_{Томпсон (сидит) и Ритчи работают на PDP-11, 1972 год.}

Период 1968-69 гг. был очень неопределенным для Bell Labs: проект операционной системы с разделением времени Multics (Multiplexed Information and Computing Service), разрабатываемой с 1964 года для дорогой 36-битной ЭВМ GE-645, не имел четких перспектив и целей, а лишь разрастался в размерах и сложности, всё ясней был виден его предполагаемый провал. В конце концов, American Telephone & Telegraph вышла из проекта, в который за пять лет были вложены миллионы долларов.

Однако, некоторые из инженеров, работавших над Multics — Кен Томпсон, Деннис Ритчи, Малкольм Дуглас Макилрой, Джозеф Оссанна, — ощущали необходимость в продолжении работы над подобным проектом, и не хотели терять успевшую сформироваться уютную рабочую атмосферу. Поэтому в 1969 году они начали искать альтернативу Multics: Оссанна, Томпсон, Ритчи пытались протолкнуть покупку машины средней мощности, для которой группа обещала написать операционную систему. Заказ на предлагаемые ЭВМ DEC PDP-10 и Sigma 7 так и не был сделан, и хотя несколько раз ситуация выходила на грань получения нужного оборудования, было вполне очевидно, что команда просит слишком крупную сумму для проекта с расплывчатым планом, тем более, что после провала Multics операционные системы стали не настолько привлекательной сферой. Поэтому Томпсон (в основном это была его задумка), Кэнэдэй и Ритчи (привнесший идею файлов-устройств) разработали на обычных черных учебных досках и бумаге устройство файловой системы, которая позже стала сердцем Unix.

Это перевод фрагмента из статьи, который, на мой взгляд, уместно вынести в отдельный пост. Основная статья: habrahabr.ru/post/193798

Проект МАС (Multiple Access Computer, Machine-Aided Cognition, Man and Computer) начался как чисто исследовательский в MIT в 1963 году. Потом он разросся в лабораторию компьютерных наук (LCS), а в наши дни назыается Лаборатория компьютерных наук и искусственного интеллекта

В начале 60-х был всплеск интереса к системам с разделением времени. Джон МакКарти написал заметку под заглавием “Программа для оператора с разделением времени для проекта IBM 709” в 1959 году. Корбато, Мервин-Даггет и Далей в 1962 году написали в статье, что “мы на пороге третьего глобального изменения к подходу использования компьюьтеров, из-за разделения времени”. Сначала это рассматривали как способ поднять эффективность использования компьютера, но очень быстро пришли к идее многопользовательской системы. Деннис Ритчи потом скажет, что самый медленный этап в цикле “написать-скомпилировать-выполнить-отладить” стал определяться человеком, а не машиной.



В рамках проекта МАС получился значительный вклад в системы с разделяемым временем, включая разработку операционной системы (тогда таких слов не было, но давайте так говорить для определенности — прим. перев.) CTSS (Compatible Time-Sharing System). Во второй половине 60-х было создано несколько других систем с разделением времени, например BBN, DTSS, JOSS, SDC, и пр. Но все это не имеет отношения к этой статье. А вот Multiplexed Information and Computing Service (MULTICS) — имеет.

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

Интернет уже не тот, что прежде — кругом враги. Тема обнаружения непосредственного заражения сайта и поиска вредоносных/зараженных скриптов на взломанном сайте рассмотрена слабо, попробуем это исправить.
Итак, представляем вашему вниманию Linux Malware Detect.

Linux Malware Detect (LMD) — это сканер для Linux, предназначенный для поиска веб-шеллов, спам-ботов, троянов, злонамеренных скриптов и прочих типичных угроз характерных для веб-пространств и особенно актуален для виртуальных шаред-хостинг платформ. Главное отличие от прочих Linux-антивирусов — его веб направленность, сканирование файлов веб-сайтов, ведь обычные антивирусы ориентируются на более глобальные угрозы уровня системы.

Привет всем!

Чуть менее года назад я включился в процесс строительства устройства, которое находится где-то между авиасимулятором и профессиональным авиатренажером. Это был не первый опыт — в 2009 году мы уже решали такую задачу, поэтому приступая к реализации весьма амбициозной мечты мы постарались не наступить на все возможные грабли. Тут я опишу предысторию с «первым блином», и как она повлияла на второй. Если будет интересно, напишу подробно про наш второй тренажер.

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

Осторожно, много картинок, вызывающих нервный тик у любителей авиации и инженеров.
Итак…

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

Предлагаю перейти на сторону зла, на темную сторону программирования. Ситхи сильнее джедаев. И печенек хватит на всех. Предупреждаю, прежде чем начнете читать далее. Характер при переходе на темную сторону портится.
Прошу под кат

Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.

# Весь код в статье написан на языке Python

Основы

Пожалуй, лучшее описание динамики в одно предложение, которое я когда либо слышал:

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Многие знакомы с выступлением Алекса Мартелли (Alex Martelli) на Google Tech Talk под названием Python for Programmers (слайды) — в нём он чётко и лаконично рассказывает основы Питона для тех, кто уже умеет программировать, например на C, С++ или Java. По его презентации я сам учил Питон четыре года назад, перед тем как начать использовать его в преподавании программирования на матмехе СПбГУ.

Сегодня хочу представить вам интерактивный вариант этой презентации — онлайн мини-курс Python for Programmers, созданный и опубликованный под лицензией Creative Commons с разрешения Алекса. Мы добавили к его презентации интерактивных упражнений, обновили материал с Python 2.5 до Python 3.3, добавили информацию по актуальным библиотекам и разнице между 2 и 3 версиями Питона.

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

Материальное производство (обработка объектов физического мира) насчитывает десятки тысяч лет истории. Оно прошло путь от каменных пещер до современных небоскребов, от сигнальных костров до мобильной связи, от навигации по звездам до навигации по космическим спутникам. На этом пути был накоплен колоссальный объем знаний естественных наук: математики, физики, химии, географии, геологии, биологии и проч.

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

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

Вот наиболее распространенные мифы и факты, которые их опровергают.

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

TL;DR — за два года маленькая команда из 2 человек (я как «строитель», и мой московский друг как главный конструктор) сумела спроектировать раму и механику дорожного электробайка, а так же построила его первый прототип. Собственно, на КПДВ — именно этот самый прототип, да. Видео тестовых покатушек — в конце статьи.

Если вам интересна история его создания — прошу под кат.

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

Этот жестокий мир теплового хаоса

Мы живем в компьютерном мире, а современная электроника в части кремниевых «мозгов» достаточно тёплая вещь — процессоры нагреваются нещадно, как основные, так и специализированные, GPU например. В каждом электрическом изделии присутствуют радиаторы пассивные и если совсем много тепла нужно рассеять — то и вентиляторы.
Как известно, электротехника это наука о контактах. Так же можно сказать, что и теплотехника — тоже наука о контакте, о тепловом контакте и передаче тепла от теплого к холодному посредством конвекции и/или излучения. Но не будем в это углубляться, поговорим о конкретном решении, направленном на уменьшение перегрева оборудования и сопутствующего шума от активных систем воздушного охлаждения в паре металл-металл.

Как-то мы сидели в баре с Джошем Лонгом и ещё несколькими друзьями с работы, когда он обнаружил, что я на «эй, ты!» с математикой. А он как раз недавно наткнулся на вот этот вопрос на StackOverflow и сейчас спросил меня, что это означает:



Однако, перед выяснением смысла данной китайской грамоты, думаю, стоит в принципе получить представление о том, для чего вообще это нужно. Пост в блоге Даниэля Спивака (перевод) даёт по-настоящему хорошее объяснение конечной цели алгоритма Хиндли-Милнера (в дополнение к углубленному примеру его применения):

Функционально говоря, Хиндли-Милнер (или Дамас-Милнер) — это алгоритм для вывода типов, основанный на рассмотрении того, как они используются. Он буквально формализует интуитивное знание о том, что тип может быть выведен через функционал, который он поддерживает.

Итак, мы хотим формализовать алгоритм вывода типа для любого заданного выражения. В этом посте я собираюсь остановиться на том, что означает «формализовать что-то», а затем описать «кирпичики» формализации Хиндли-Милнера. Во второй части я дам более конкретное описание этих блоков. Наконец, в третьей части я переведу вопрос со StackOverflow.