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

Иногда для понимания того, как работает та или иная вещь, лучше один раз увидеть, чем сто раз услышать.

Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



Все это бегает и сортируется прямо на ваших глазах!

Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

Последующее описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.

Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

В данной статье рассмотрен один из вариантов шифрования данных в Linux.

Введение

Как известно, многие С-библиотеки используют обратные вызовы для обеспечения какого-либо функционала. Так поступает, например, библиотека expat для реализации SAX модели. Обратный вызов или callback используется для возможности выполнить пользовательский код на стороне библиотеки. Пока такой код не несет побочных эффектов — все нормально, но как только на арене появляется С++, все, как всегда, становится нетривиальным.

По долгу службы мне время от времени приходится копировать, архивировать, разархивировать и проводить другие стандартные действия с большими файлами. Консольные утилиты, типа cp, tar или cat — отлично справляются с поставленной перед ними задачей, но возникает одна маленькая проблема: предположим, что надо заархивировать SQL-дамп на 500 Мб, на среднем железе данная операция может выполняться 5 — 10 минут и при этом, стандартный tar не выводит никакой строки прогресса, т.е. консоль как бы подвисает и только открыв top в соседнем окне можно понять что что-то происходит. Я думаю, что будет намного удобнее, если в консоли появится полоска прогресса как в том же scp и тогда пользователь будет лучше осведомлен о том, как долго ему осталось ждать до завершения операции.

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

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

Первые посты серии уже подготовлены, и бета-тестировались в одном маленьком и наглухо закрытом сообществе. Тем не менее, я буду продолжать их править с учётом пожеланий почтенной хабрапублики.

Далее в посте:

1. С какой стати писать компиляторы?
2. Общий план
3. Анализ текста
4. Практический пример
5. Как это работает?

Как известно, C++ позволяет глобально переопределять операторы new и delete. Обычно такое переопределение используется для диагностики, поиска утечек памяти и более эффективного распределения памяти.

Все это мы используем в нашем крупном проекте. Однако у нас есть часть, написанная на C#, которая с помощью C++/CLI взаимодействует с основной частью на C++. И вот тут появились проблемы. У нас получались утечки памяти там, где их быть ну никак не могло.

Я давно читал про них, ещё когда учился основам юникс, но как-то не было нужды с ними работать. И, вот, нужда возникла.

Некая программа (допустим, foo) не умеет писать вывод в stdout, только в файл. Даже "-" в качестве имени файла всего лишь создаёт файл с названием "-" [большинство умных программ под unix знают, что одиночный минус вместо имени файла означает вывод в stdout]. Аналогично она отвергает и /dev/stdout.

Другая же программа, обрабатывающая результаты первой, допустим, bar, читает из stdin и пишет в stdout. (если быть точным, первое — это трейсер специального вида, дающий двоичный дамп, а второе — конвертор, печатающий их же в человекочитаемом виде).

Нужно их объединить в конвеер.

Некрасивый вариант — использование обычного файла. Записал, прочитал.

Есть куда более красивый вариант — это именованные пайпы. Так как у пайпа есть имя, мы можем передать его как файл первой программе, а потом передать содержимое другой.

Выглядит это так:

mkfifo mypipe
cat mypipe | bar &
foo mypipe&
rm mypipe