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

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

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

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

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

Логарифмы

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

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

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

Сложность

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

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

Введение

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

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

Правильное использование CSS свойства float может стать непростой задачей даже для опытного верстальщика. В этой статье собраны варианты применения float, а также некоторые ошибки, с наглядными примерами.

Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

Несколько недель назад, 15 февраля, мы проводили нашу первую конференцию для тестировщиков LoveQA. Спасибо всем тем, кто пришел и кто смотрел online трансляцию. У нас есть видео докладов и мы с удовольствием ими с вами делимся. Сегодня выкладываем первые 4 доклада и в конце недели опубликуем остальные.
Если у вас остались какие-то вопросы, то их можно задавать в комментариях к посту.
Фото с конференции в FB и Вконтакте.

Доклады

«Есть ли жизнь после релиза? Наш опыт тестирования мобильных приложений»
Александр z3us Хозя & Николай Козлов, Badoo.

Еще одна? Зачем? Есть же CommonJS и AMD? Страждующие могут пройти под кат.

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

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

Со временем возможно появятся похожие таблички с правилами расстановки пробелов, знаков препинания и по оформлению текста в целом.

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

Мы также не будем касаться вопросов проверки смысловой точности цитирования, правильного использования купюр, сокращений и дополнений — всех интересующихся ждёт «Справочник издателя и автора» А. Э. Мильчина и Л. К. Чельцовой.

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

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

Не претендуя на библию или «настольную статью программиста» я хочу поделиться полезными находками в моей любимой IDE, не скатываясь в тупую копипасту мануалов и скучных списков хоткеев, только то, что я сам использую постоянно и над чем удивляются коллеги: «о! а так можно?»

PhpStorm — повышаем производительность (плагины и темы оформления). Часть 2

У всех нас есть любимые IDE или редакторы в которых мы пишем код. Для меня это PhpStorm, и потребовалось некоторое время, чтобы освоить все клавиатурные сокращения и ускорить свой рабочий процесс. В этой статье я поделюсь с вами некоторыми сочетания клавиш и советами, которые возьмут на себя часть рутинной работы, если вы тоже делаете свою работу в этой IDE. Эта статья была частично вдохновлена этим Reddit тредом, и я буду упомянать и демонстрировать некоторые трюки найденные там.

Обратите внимание, что я разрабатываю на Linux в Vagrant, размещенном в Windows, я буду использовать клавишу CTRL вместо CMD. Если вы работаете в OS X, замените CTRL на CMD.

Клавиатурные сокращения и хаки

PhpStorm позволяет настроить себя практически до бесконечности — вы можете заточить этот инструмент под себя так, что постороннему может показаться, что это совсем другая IDE.

(осторожно, много gif изображений)

Как получить работу инженера?

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

# x = количество компаний, в которых ты проходил собеседования

# y = количество предложений о работе, которые ты получил

рейтинг = 100 * log(x) * y / x


Если твой рейтинг < 90, обязательно прочти это. Если > 120, возможно, тебе это не нужно, но, все равно прочти.

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

Перевод pdf файла с сайта http://www.mcdonaldland.info/ с описанием 23-х шаблонов проектирования GOF. Каждый пункт содержит [очень] короткое описание паттерна и UML-диаграмму. Сама шпаргалка доступна в pdf, в виде двух png файлов (как в оригинале), и в виде 23-х отдельных частей изображений. Для самых нетерпеливых — все файлы в конце статьи.

Под катом — много картинок.

Наткнувшись на занятную головоломку на тему регулярных выражений, конечно же я не смог пройти мимо:

regex.alf.nu

В честь наступающего Нового года я набрал в ней 2014 очков. Кто больше?

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

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

Привет, %username%

Хабра-АДМ 2014 набирает обороты. Уже более 100 человек отправили подарки. И, что очень круто, 3 уже получили.

А это значит, что наступила пора показать всем, что вам прислал ваш Дедушка Мороз.

С НАСТУПАЮЩИМ НОВЫМ 2014 ГОДОМ!

UPD: Ссылка для обращения к новогодним эльфам.

Проблемы контроля версий баз данных и миграций между версиями уже не раз поднимались как на Хабре (1, 2, 3 и др.), так и в Интернете (преимущественно, англоязычном).

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

В ходе тестирования некоторых продуктов компании Positive Technologies возникла необходимость проведения быстрых стресс-тестов одного веб-сервиса. Эти тесты должны были быть простыми и быстрыми в разработке, нетребовательными к аппаратным ресурсам и одновременно с этим давать значительную нагрузку однотипными HTTP-запросами, а также предоставлять статистические данные для анализа системы под нагрузкой.

Для их реализации мы исследовали и опробовали некоторое количество инструментов, среди которых были Apache JMeter и написанный нами на Python скрипт LogSniper, который выполнял реплей заранее подготовленных серверных логов с HTTP-запросами на цель.