От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

Многие современные программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.

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

Предисловие

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

Часть 2
Часть 3

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

В части первой:
• Создание простого Comet — приложение, которое посылает клиентам сообщение каждые 10 секунд.
• Настройка ядра Linux для поддержки большого количества соединений.
• Создание тестирующей утилиты для создания большого количества соединений.
• Определение необходимого количества памяти.

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

Предполагается, что Вы знакомы с bash, и немного с Erlang.

Совсем немного теории

Исторически сложилось так, что в X Window System (X11, — оконная система для Linux, UNIX) существует два буфера обмена.

Один из них (clipboard) похож на буфер обмена в Windows — при нажатии на Ctrl+Insert или Ctrl+C выделенный фрагмент (текст, картинка, файл) копируется в буфер обмена, а при нажатии на Shift+Insert (или Ctrl+V) — вставляется из него. Следует заметить, что во многих программах эти сочетания зарезервированы для иных целей и приходится пользоваться другими — например, в терминале сочетание Ctrl+C используется для завершения процесса, а для работы с буфером обмена используются сочетания Ctrl+Shift+C для копирования и Ctrl+Shift+V для вставки.

Второй буфер (primary) является специфичным для оконной системы X11. Выделенный текст незамедлительно попадает в буфер primary, и для того, чтобы вставить скопированный текст, достаточно лишь нажать среднюю кнопку мышки (колёсико). У кого в наличии не имеется трёхкнопочной мышки, а так же владельцам ноутбуков с тачпадами следует одновременно нажать левую и правую кнопки мышки для вставки текста.

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(), а также, что оба процесса выполняются параллельно в разных потоках.

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

• действия выполняются вручную, что требует сосредоточенности и аккуратности;
• жёсткие временные рамки.

В нашем случае налицо лимит по времени: релизы формируются, тестируются и выкатываются на продакшн-сервер два раза в день. При ограниченных сроках в жизненном цикле релиза процесс удаления (отката) из релизной ветки задачи, содержащей ошибку, имеет важное значение. Для её выполнения мы используем git rebase. Так как git rebase ― это полностью ручная операция, которая требует внимательности и скрупулезности и занимает продолжительное время, мы автоматизировали процесс удаления задачи из релизной ветки.

Введение

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

Измерить качество обслуживания напрямую мы, конечно, не можем, однако даже такую эфемерную величину в принципе можно свести к набору количественных характеристик, так или иначе косвенно отражающихся на качестве. Прибыль, число клиентов, процент конвертированных лидов (leads – зарегистрировавшиеся или заинтересованные пользователи) и т.д. – все это вполне объективные показатели. Кроме того, эти величины могут быть включены в систему контроля эффективности работы в качестве KPI – ключевых показателей эффективности.

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

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

Разработка

Я расскажу о цикле разработки через Github, который я использую. Он был проверен в течении года на командах разного размера: 3 — 14 человек.

Существует 2 основных ветки: master и dev.

master — стабильная ветка, готовая к выкатыванию на production сервер в любой момент.

dev — ветка, над которой в данный момент работает команда.

Итак, в начале разработки master и dev ветки идентичны.

На момент написания этой статьи в JavaScript еще не существовало официальной модульной системы и все эмулировали модули как могли.

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

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

Дело в том, что раньше не думали, что на JavaScript можно делать огромные проекты, а не просто «пропатчить DOM», поэтому о модулях не думали. Да и вообще не думали о будущем. И тут Внезапно будущее нагрянуло! Все вроде-бы уже есть, а модули в JavaScript, мягко говоря, запаздывают. Поэтому разработчикам приходится крутиться и выдумывать какие-то эмуляторы модульности.

Думаю многие из вас читали прекрасную статью Addy Osmani Writing Modular JavaScript With AMD, CommonJS & ES Harmony, которая стала одной из глав его книги Learning JavaScript Design Patterns в этой статье рассказывается про «современные» JavaScript модули или же читали достаточно старую статью JavaScript Module Pattern: In-Depth 2010 года про «старые» модули.

Я не буду переводить эти статьи и не буду делать из них солянку. В своей статья я хочу рассказать о моем модульном пути. О том как я проделал путь от «старых» модулей к «новым» и что использую сейчас и почему.

Я занимаюсь восстановлением исходников PHP из закодированного вида.
В этой статье я расскажу о том, как обстоят дела с кодированием и декодированием PHP в настоящее время.

Очень краткий ликбез по внутреннему устройству интерпретатора PHP

При выполнении PHP-скрипта, он парсится и компилируется в опкоды внутренней виртуальной машины PHP.
Из каждого файла PHP получаются:
— массив классов: в каждом классе — информация о классе, свойства класса и массив методов класса
— массив функций
— «тело скрипта» — код вне классов и функций

Списки книг

• 25 бесплатных книг по информатике
• Шпаргалки
• CodePlex: Список бесплатных книг
• Бесплатные технические книги
• Galileo Computing (Немецкий)
• How to Design Programs: An Introduction to Computing and Programming
• Microsoft Press: Бесплатные книги
• MindView Inc
• Проект O'Reilly's Open Books
• TechBooksForFree.com
• Theassayer.org
• Wikibooks: Программирование
• Неплохая подборка, редактируемая сообществом (JIghtuse)
• Книги на Русском (telteron)

Программирование графики

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

JavaScript, the winning style

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

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

В отличие от Питона у которого есть единый свод правил «Style Guide for Python Code», у языка JavaScript такого нет. Однако на выбор есть целых 6 популярных гайдов:

• Google JavaScript Style Guide
• npm’s coding style
• Felix’s Node.js Style Guide
• Idiomatic JavaScript
• jQuery JavaScript Style Guide
• Douglas Crockford’s JavaScript coding style

Помимо гайдов, не стоит так же забывать об автоматических анализаторах кода, таких, например, как JSLint и JSHint. И в них уже заложены свои настройки. Вопрос в том, какой же все-таки максимально правильный способ писать код на JavaScript, который был бы актуален и максимально соответствовал бы большинству рекомендаций? Давайте попробуем объединить большинство рекомендаций в этой статье и подумаем как можно оптимизировать процесс проверки качества кода.

PDF — формат, ставший уже стандартом. Он был изначально создан Adobe для представления текста и изображений в документе с фиксированной структурой. Давно не редкость для веб-приложений, поддерживающих скачку данных, таких как счета или отчеты, отдавать их в PDF формате. Так что в этой статье мы пройдем простую генерацию PDF документов используя PHP.

Dompdf — это отличная библиотека, способная генерировать PDF из HTML-разметки и CSS-стилей (в большинстве случаев это стили, совместимые с CSS 2.1 с поддержкой некоторых свойств CSS3). Мы можем определить, как наше содержимое должно выглядеть, используя эти знакомые технологии, и после легко конвертировать его в фиксированный документ. Также эта библиотека имеет и другие полезные и интересные функции.

Как же все-таки работает HTTPS? Это вопрос, над которым я бился несколько дней в своем рабочем проекте.

Будучи Web-разработчиком, я понимал, что использование HTTPS для защиты пользовательских данных – это очень и очень хорошая идея, но у меня никогда не было кристального понимания, как HTTPS на самом деле устроен.

Как данные защищаются? Как клиент и сервер могут установить безопасное соединение, если кто-то уже прослушивает их канал? Что такое сертификат безопасности и почему я должен кому-то платить, чтобы получить его?

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Разрабатывая постоянно сталкиваешься с разнообразными задачами, которые часто решить в лоб не удаётся. Но многие задачи уже были решены кем-то — нужно только найти это решение.

Так, день за днём я насобирал небольшую коллекцию батареек, которые сильно облегчили мне жизнь. Чем и спешу поделиться:

Это перевод 1.17 версии руководства от Rafe Kettler.

Содержание

1. Вступление
2. Конструирование и инициализация
3. Переопределение операторов на произвольных классах
   • Магические методы сравнения
   • Числовые магический методы
4. Представление своих классов
5. Контроль доступа к атрибутам
6. Создание произвольных последовательностей
7. Отражение
8. Вызываемые объекты
9. Менеджеры контекста
10. Абстрактные базовые классы
11. Построение дескрипторов
12. Копирование
13. Использование модуля pickle на своих объектах
14. Заключение
15. Приложение 1: Как вызывать магические методы
16. Приложение 2: Изменения в Питоне 3

Вступление

Что такое магические методы? Они всё в объектно-ориентированном Питоне. Это специальные методы, с помощью которых вы можете добавить в ваши классы «магию». Они всегда обрамлены двумя нижними подчеркиваниями (например, __init__ или __lt__). Ещё, они не так хорошо документированны, как хотелось бы. Все магические методы описаны в документации, но весьма беспорядочно и почти безо всякой организации. Поэтому, чтобы исправить то, что я воспринимаю как недостаток документации Питона, я собираюсь предоставить больше информации о магических методах, написанной на понятном языке и обильно снабжённой примерами. Надеюсь, это руководство вам понравится. Используйте его как обучающий материал, памятку или полное описание. Я просто постарался как можно понятнее описать магические методы.