Сегодня предложу Вашему вниманию симпатичный алгоритм, который хоть и придумали совсем недавно (11 лет назад), но «прототипом» послужило счётное устройство с трёхтысячелетней историей.

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

Суть алгоритма заключена в использование структуры данных — бора и построения по нему конечного детерминированного автомата. Важно помнить, что задача поиска подстроки в строки тривиально реализуется за квадратичное время, поэтому для эффективной работы важно, чтоб все части Ахо-Корасика ассимптотически не превосходили линию относительно длинны строк. Мы вернемся к оценке сложности в конце, а пока поближе посмотрим на составляющие алгоритма.

Предлагаю обсудить такую интересную, но мало используемую возможность python, как сопрограммы (coroutines).
Сопрограммы в питоне основаны на генераторах (ими, они, собственно и являются).
Поэтому, предлагаю начать именно с генераторов, в общем понимании. А потом разберём как написать свою сопрограмму.

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

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

Логарифмы

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

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

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

Сложность

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

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

Введение

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

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

На прошлой неделе (19 августа — прим.пер.) у вас был шанс задать вопрос Гвидо ван Россуму, Великодушному Пожизненному Диктатору Python, касательно любых аспектов Python, а также его переезда в Dropbox. Гвидо не теряя времени ответил на некоторые ваши вопросы.

Эта статья задумана мной как сборник некоторых интересных моментов по использованию и оптимизации SQL запросов в БД MySQL, на мой взгляд, плохо освещенных в интернете. Так, из статьи вы узнаете о конструкции with rollup, и о том, как переписать подзапросы in и not in на join'ы, а так же обновление и удаление данных в нескольких таблицах — одним запросом, и многое другое. Начнем по порядку.

Предисловие

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

Здравствуйте, хабрачеловеки! Многие из Вас сталкивались с вынесением бизнес-логики в СУБД в виде хранимых функций/процедур, облегчая клиент. В этом есть как и преимущества, так и недостатки. Сегодня я бы хотел рассказать Вам как создавать хранимые функции в PostgreSQL, написанные на языке C. В статье будут самые основы, которые необходимо знать для начала работы с ними.

Здравствуйте, хабрачеловеки! Не так уж давно вышел релиз PostgreSQL 9.3 и я хотел бы ознакомить Вас с наиболее важными новшествами, касающимися клиентской части, которые, возможно, пригодятся Вам. В этой статье рассмотрено следующее:

• материализированные представления
• обновляемые представления
• триггеры к событиям
• рекурсивные представления
• латеральное присоединение
• изменяемые внешние таблицы
• функции и операторы для работы с типом JSON

UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

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

Периодически нам в редакцию приходят письма с вопросом будет ли новый тираж книги «Программируем на Python» М.Доусона. Несмотря на то, что оригинал «Python Programming for the Absolute Beginner, 3rd Edition» вышел в 2010г., он до сих пор в бестах на amazon.com. Содержание книги построено на практических примерах программирования простых игр. Нам очень интересно узнать мнение профессионалов, что позволит принять решение издавать ли книгу.

Полное оглавление можно посмотреть здесь.

Отрывок из Главы 5. Списки и словари. Игра «Виселица»

Предисловие

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

Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.

Такая разница в скорости заставила меня разобраться, как решается эта задача и ещё целый класс подобных.

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

Волокна заряжены в сварочный аппарат

Здравствуйте, читатели Хабра! Все слышали про оптические волокна и кабели. Нет нужды рассказывать, где и для чего используется оптика. Многие из вас сталкиваются с ней по работе, кто-то разрабатывает магистральные сети, кто-то работает с оптическими мультиплексорами. Однако я не встретил рассказа про оптические кабели, муфты, кроссы, про саму технологию сращивания оптических волокон и кабелей. Я — спайщик оптических волокон, и в этом (первом своём) посте хотел бы рассказать и показать вам, как всё это происходит, а также часто буду в своём рассказе отвлекаться на прочие смежные с этим вещи. Опираться буду в основном на свой опыт, так что я вполне допускаю, что кто-то скажет «это не совсем правильно», «вот тут неканонично».
Материала получилось много, поэтому возникла необходимость разбить топик на части.
В этой первой части вы прочтёте про устройство и разделку кабеля, про оптический инструмент, про подготовку волокон к сварке. В других частях, если тема окажется вам интересной, я расскажу про методы и покажу на видео сам процесс сращивания самих оптических волокон, про основы и некоторые нюансы измерений на оптике, коснусь темы сварочных аппаратов и рефлектометров и других измерительных приборов, покажу рабочие места спайщика (крыши, подвалы, чердаки, люки и прочие поля с офисами), расскажу немного про крепёж кабелей, про схемы распайки, про размещение оборудования в телекоммуникационных стойках и ящиках. Это наверняка пригодится тем, кто собирается стать спайщиком. Всё это я сдобрил большим количеством картинок (заранее извиняюсь за paint-качество) и фотографий.
Осторожно, много картинок и текста.

Часть 2 здесь.

Рассмотрены примеры таких конструкций + некоторые очевидные, но не менее опасные конструкции, которых в коде желательно избегать. Статья рассчитана на python программистов с опытом 0 — 1,5 года. Опытные разработчики могут в коментах покритиковать или дополнить своими примерами.

1. Введение
2. Объекты. Голова
3. Объекты. Хвост
4. Структуры процесса

Помимо изучения стандартной библиотеки, всегда интересно, а иногда и полезно, знать, как язык устроен изнутри. Андрей Светлов (svetlov), один из разработчиков Python, советует всем интересующимся серию статей об устройстве CPython. Представляю вам перевод первого эпизода.

Мой друг однажды сказал мне: «Знаешь, для некоторых людей язык C — это просто набор макросов, который разворачивается в ассемблерные инструкции». Это было давно (для всезнаек: да, ещё до появления LLVM), но эти слова хорошо мне запомнились. Может быть, когда Керниган и Ритчи смотрят на C-программу, они на самом деле видят ассемблерный код? А Тим Бёрнерс-Ли? Может он сёрфит интернет по-другому, не так, как мы? И что, в конце концов, Киану Ривз видел в том жутком зелёном месиве? Нет, правда, что, чёрт побери, он там видел?! Эм… вернёмся к программам. Что видит Гвидо ван Россум, когда читает программы на Python?

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

Краткий список того, о чём пойдёт речь в статье:

• hg serve (hgweb) — встроенный веб-сервер
• расширения pager, progress и color
• hg [c]record — выбор отдельных изменений для коммита
• revsets и filesets — поиск коммитов и файлов с запросами любой сложности
• hg evolve — Changeset Evolution или же «изменяемая история»