Перевод третьей лекции из курса «Структура интерпретация компьютерных программ».

Это самый известный курс по программированию за последние 25 лет; с 1980г читается в MIT, а с недавних пор что-то подобное читается и в Беркли.

Курс сменил преподавателей и даже язык программирования Scheme на Python(на мой взгляд совершенно зря) и тем не менее информация, которая дается в этом курсе остается архи актуальной в любое время. Я бы сравнил этот курс с чем-то очень фундаментальным и важным для программистов, типа математики или теории алгоритмов.

Мне бы очень хотелось, чтобы программирование у нас в стране преподавалось таким вот образом.

Приятного просмотра!

Знаете, люблю я книжки про всякие интересные алгоритмы, и вот недавно попалась еще одна такая книжка.

Книга «Программируем коллективный разум» в основном посвящена алгоритмам классификации и кластеризации, хотя есть главы, посвященные другим темам вроде создания собственного поисковика, генетическим алгоритмам и генетическому программированию. Почти все описанные алгоритмы применяются в духе Web 2.0, используя анализ поведения пользователей на разных сайтах, которые предоставляют свой API. Но что особенно приятно удивило, так это то, что все примеры написаны на языке Python.

Вот какие алгоритмы описываются в книге:

• Коллаборативная фильтрация. Или, говоря человечески языком, алгоритмы, которые могут рекомендовать вам какие-то покупки, сайты или музыку в зависимости от оценок, которые вы поставили другим подобным вещам. По таким алгоритмам работает навязывание покупок в интернет-магазинах или подбор музыки на last.fm. В конце главы приводится пример, который будет рекомендовать вам ссылки из сервиса del.icio.us.
• Алгоритмы группировки (кластеризации). Создаваемый пример анализирует RSS-каналы блогов и пытается их автоматически разделить на группы в виде дерева в зависимости от частоты слов, которые попадаются в блоге. Заодно Сегаран рассказывает как можно сделать так, чтобы названия блогов расположились на плоскости кучками в зависимости от их близости в плане рассматриваемых тем.
• Отдельная глава посвящена построению поисковиков – созданию паука и, самое главное, рассматриваются алгоритмы ранжирования ссылок, в том числе и с учетом ссылок страниц друг на друга, создавая, таким образом, аналог Google PageRank. Еще интересно, что в этой же главе есть пример, где для выдачи наиболее релевантных ссылок используется нейронная сеть, которая обучается по мере того как пользователь щелкает на понравившиеся ему ссылки.

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

Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

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

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

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

От переводчика: Я думаю многие читали статью Rey Bango — What to Read to Get Up to Speed in JavaScript, но до хабра обсуждение так и не докатилось. Предлагаю закрыть этот пробел и поговорить о хороших книгах, блогах, тренингах и конференциях, посвященных в первую очередь клиентскому JavaScript и клиентской веб-разработке. Чтобы не копипастить оформляю статью в виде перевода.

Сейчас в рассылке JSMentors JavaScript идет обсуждение книг, который стоит прочитать, чтобы улучшить свои знания. Там было много позитивных отзывов и предложений. Я хочу показать вам те книги и интернет-ресурсы, который я считаю важными и которые помогут вам в обучении. На этой странице я перечислил большое количество источников, разделенных по уровням.

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

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

Недавно у Эльбы вышло обновление, в котором появилась возможность сдать справки 2-НДФЛ за своих работников в налоговую. К нам тут же посыпалась куча испуганных возгласов от предпринимателей: «Что это еще за 2-НДФЛ? Когда сдавать? Почему я про это не знаю? Достали уже эти чиновники». И мы поняли, что немного испугали народ.

Ребята! Все окей — 2-НДФЛ сдается только за ваших сотрудников :)

Но подумав о наемных работниках, мы вспомнили, что не все фрилансеры стали акулами бизнеса и многим была очень интересна тема — как обычному трудяге можно законно изъять отданный государству подоходный налог. Мы решили отойти от своей ПроБизнес-тематики и просветить желающих: сегодня мы раскроем магию налоговых вычетов по НДФЛ.

Собственно столкнулся с проблемой, что при использовании RabbitMQ необходимо мониторить сервер. Системную утилиту rabbitmqctl можно запускать из командной строки, но запустить ее из приложения не получилось. Что-то связанное с окружением эрланга.

После небольшого гугления и общения в целевых форумал получил заветную ссылку

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

далее кр описание…

Xpath — это язык запросов к элементам xml или xhtml документа. Также как SQL, xpath является декларативным языком запросов. Чтобы получить интересующие данные, необходимо всего лишь создать запрос, описывающий эти данные. Всю «черную» работу за вас выполнит интерпретатор языка xpath.
Очень удобно, не правда ли? Давайте посмотри какие возможности предлагает xpath для доступа к узлам веб-страниц.

Привет, Хабрачитатель!
Полнотекстовый поиск данных в InnoDB – это известная головная боль многих разработчиков под MySQL / InnoDB. Для тех, кто не в курсе дела я объясню. В типе таблиц MyISAM есть полноценный полнотекстовый поиск данных, однако сама таблица исторически имеет ограничения, которые являются принципиальными в отдельных проектах. В более «продвинутом» типе таблиц InnoDB полнотекстового поиска нет. Вот и приходится мириться бедным разработчикам либо с ограничениями MyISAM, либо с отсутствием поиска в InnoDB. Я хочу рассказать о том, какие есть способы организовать полноценный поиск в InnoDB без магии и исключительно штатными средствами. Также будет интересно сравнить скоростные характеристики каждого способа.

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

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

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

Много слов сказано о достоинствах юнит-тестов (TDD, BDD — в данном случае неважно), а также о том, почему люди всё-таки их не используют.

Но я думаю, что одна из главных причин заключается в том, что люди не знают, с чего начать. Вот прочитал я статью про юнит-тесты, понравилось; решил, что надо бы когда-нибудь попробовать. Но что дальше? С чего начать? Как придумывать все эти требования, как называть тест-методы?

В последнее время набирает популярность тенденция превращать юнит-тесты в BDD-спецификации, то есть говорится о том, что хороший юнит-тест должен не тестировать что-то, а описывать поведение программы. Но как описать это чёртово поведение; откуда брать вдохновение, чтобы придумать названия для всех этих тест-кейсов?

Об этом и пойдёт речь:

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Поскольку новость не пробежала на Хабре, но однозначно (с) будет интересна многим:

«Видео с пользовательской конференции по Sphinx (~8часов)
http://devconf.tv/user/sphinx».

В этой статье будут описаны различные настройки MySQL, преимущественно те, которые влияют на производительность. Для удобства все переменные разделены по разделам (базовые настройки, ограничения, настройки потоки, кэширование запросов, тайминги, буферы, InnoDB). Сначала уточним имена некоторых переменных, которые изменились в версии 4 MySQL, а в сети продолжают встречаться и старые и новые варианты имен, что вызывает вопросы.

По субботам, в 15:00 MSK проводятся бесплатные удалённые занятия по обучению программированию на Ruby для школьников и студентов. Курс рассчитан на начинающих изучать программирование и может рассматриваться как введение в программирование вообще.

Данный курс родился как дополнение к курсу по выбору «Метапрограммирование на Ruby» на Физтехе и посвящен более простым и базовым вещам. Сложность изложения и темы в значительной степени будут определяться аудиторией курса.

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

Я решил, что неплохо было бы поделиться с Вами алгоритмами, размышления, результатами, а также получить качественную критику моих путей решения задач.
Будем брать задачу, разбирать ее по частям, анализировать, выдумывать различные пути решения, выбирать лучший, а потом нести на суд «великих судей». Для многих, по моему мнению, такой час разгрузки будет очень полезным, а кому-то просто будет интересно посоревноваться и придумать свой алгоритм.

Задачи я буду брать с сайта http://uva.onlinejudge.org/, где располагается достаточно большая коллекция задач на любой вкус, и там же можно проверить свое решение. Выбирать буду случайным образом и всегда доводить начатое до финального решения, которое ознаменуется оценкой «Accepted» (Принято). Для решения этих задач нам потребуется знание одного из языков программирования: c, c++, java, pascal, а также терпение, логика и базовое знание английского языка, т.к. условия задач мы получаем на английском языке.

Итак, начнем мы с простой задачки из набора «Для новичков» для разминки, чтобы проверить свои способности.

Просматривая различный код по выводу на экран какой-нибудь даже примитивной графики, я заметил чрезмерную любовь некоторых программистов к тригонометрии. Часто код пестрит синусами, косинусами и арктангенсами там, где без них можно обойтись. Этим грешат даже хорошие программисты, которые способны спроектировать сложную систему, но почему-то не освоили вектора в объёме школьной программы. Буквально азов векторной алгебры хватает для решения многих насущных проблем. В этом топике я хочу провести краткий ликбез, напомнить основные действия с векторами на плоскости и в качестве примера решить две задачи без тригонометрии: поиск отражённого луча по падающему лучу и произвольно расположенному зеркалу, а также рисование наконечника стрелки. Если вы можете представить в голове рисование произвольно направленной стрелки без синусов и косинусов, смело пропускайте этот топик. Для остальных постараюсь объяснять попроще.

Добрый день!

Как представитель проекта Лекториум рад сообщить — мы опубликовали весь архив Computer Science клуба.
Кроме того, почти год назад мы организовали запись всех лекций на хорошие камеры и микрофоны.
А в этом году планируем подключить вебинары.


Большинство лекций читается на русском языке. Все записи снабжены презентациями и описаниями.

UPD. Кратко. Старые лекции в плохом качестве, а новые с 2010 года с хорошим звуком и в 720p.
UPD 2 Расширили канал, видео грузится теперь без проблем.

Под катом перечень курсов и несколько вопросов касательно вебинаров.

В 1999-м году в браузере IE 5 Микрософт впервые реализовал автозаполнение текстовых полей форм, что позволило вам не вводить текст, который вы уже вводили ранее в поле с данным именем (в том числе на другом сайте). Тогда же появилось нестандартное расширение тега <input>: атрибут autocomplete, установление которого в off позволяло отключить эту функциональность для конкретного поля. Сейчас все популярные браузеры (подсказали, что кроме Оперы) поддерживают автозаполнение и этот атрибут. Он также введён в стандарт HTML 5. Тем не менее, разработчики веб-сайтов зачастую им пренебрегают.

Это даже не статья и не полноценное руководство, а маленький сниппет, который поможет вам в наикратчайшие сроки поднять хорошо защищенный и правильно настроенный роутер на любой GNU/Linux машине. И это при полном отсутствии необходимости знания iptables.

Firehol, в отличие от shorewall, это даже не набор скриптов, а всего лишь один bash скрипт. Поэтому для его использования необходимость в perl и других интерпретаторах отпадает.

Firehol ближе к старому доброму narc (netfilter automatic rule configurator), но последний не обновлялся уже 6 лет и представляет из себя достаточно простой скрипт, который не совместим с последними версиями iptables. Ближе он тем, что позволяет писать правила практически на родном человеческом языке.