Сегодня мы завершаем новогоднюю серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».

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

Мы учли то, о чём нас просили в комментариях к прошлым курсам — теперь при желании можно не только смотреть/скачивать лекции по отдельности, но и загрузить всё разом в виде открытой папки на Яндекс.Диске. Кстати — в предыдущих постах тоже появились такие же апдейты (вот ссылки для удобства: «машинное обучение», «дискретный анализ и теория вероятностей», «параллельные и распределённые вычисления»).



Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.

Праздничная неделя подходит к концу, но мы продолжаем публиковать лекции от Школы анализа данных Яндекса для тех, кто хочет провести время с пользой. Сегодня очередь курса, важность которого в наше время сложно переоценить – «Параллельные и распределенные вычисления».

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



Лекции читает Олег Викторович Сухорослов, старший научный сотрудник Центра грид-технологий и распределенных вычислений ИСА РАН. Доцент кафедры распределенных вычислений ФИВТ МФТИ. Кандидат технических наук.

Эта статья навеяна топиком «Как и насколько быстро вы считаете в уме на элементарном уровне?» и призвана распространить приёмы С.А. Рачинского для устного счёта.
Рачинский был замечательным педагогом, преподававшим в сельских школах в XIX веке и показавшим на собственном опыте, что развить навык быстрого устного счёта можно. Для его учеников не было особой проблемой посчитать подобный пример в уме:

Часто возникает задача подсчета количества посещений той или иной страницы портала или подсчета кликов по какой-то ссылке. Например. может быть интересно подсчитать количество просмотров статьи или объявления, число кликов по «показать номер телефона» на странице объявления о продаже и т.д. и т.п.

Главное точно понимать, для чего вы планируете использовать эти счетчики и для чего они могут понадобиться в обозримом будущем. Нужно ли по ним выбирать/сортировать/группировать сущности или вам просто нужны редкие разовые отчеты (например раз в сутки)? А может, вы хотите показывать эти счетчики в админке или в личном кабинете пользователя? Хотите ли вы в реальном времени показывать эти числа или можно ограничиться часовой/суточной отсечкой? В зависимости от этих и, возможно, еще каких-то критериев будет зависеть выбор способа подсчета и хранения счетчиков.

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

Для понимания статьи необходимо немножко уметь программировать, не пугаться слов unix и веб. Основы языка будут изложены в статье.

Знакомимся с RabbitMQ

Переводы на хабре:
RabbitMQ tutorial 1 — Hello World
RabbitMQ tutorial 2 — Очередь задач
RabbitMQ tutorial 3 — Публикация/Подписка

Сразу дополню некоторые недочеты. И кратко повторю основные термины.

Принцип работы архитектуры использующей rabbitMq

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

Несмотря на то, что в интернете на иностранных ресурсах есть полно материала про настройку/развертывание Hadoop, большинство из них либо описывают настройку ранних версий (0.X.X и 1.X.X), либо описывают только настройку в режиме single mode/pseudo distributed mode и лишь частично fully distributed mode. На русском языке материала практически нет вовсе.

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

Всем кому интересно, прошу пожаловать по кат.

Привет, %username%!
Я расскажу и покажу как работает основа генерации денег в криптовалютах — майнинг. Как создается первый блок, новые блоки и как появляются деньги из ниоткуда.
Чтобы было проще понять, мы напишем свой импровизированный майнер для импровизированной криптовалюты HabraCoin.

Этот текст является переводом статьи 'Stop Being Cute and Clever' небезызвестного (по крайней мере, в Python-комьюнити) Армина Ронахера.

Последние дни в свободное время я занимался созданием планировщика. Идея была простой: создать некий клон worldtime buddy c использованием AngularJS и некоторых других JavaScript-библиотек.

И знаете что? Это было отнюдь не весело. Я уже давно так сильно не злился, работая над чем-либо, а это что-то значит, потому что обычно я быстро высказываю своё недовольство (прошу прощения у моих фолловеров в Twitter).

Я регулярно использую JavaScript, но мне редко приходилось сталкиваться с кодом других людей. Обычно я привязан только к jQuery, underscore и иногда AngularJS. Однако в этот раз я пошел ва-банк и решил использовать различные сторонние библиотеки.

Для данного проекта я использовал jQuery, без которого уже нельзя обойтись (да и зачем?), и AngularJS с некоторыми UI-компонентами (angular-ui и биндинги к jQuery UI). Для работы с часовыми поясами использовался moment.js.

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

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

Денис Крючков (deniskin) рассказал Roem.ru о том, что он смог выкупить акции «Тематических медиа» у Mail.Ru Group и теперь сможет управлять компанией единолично. Мы думаем, что это одно из самых эпохальных событий в истории «Хабрахабра» и по такому случаю у Дениса стоит взять интервью



— Привет, позволь тебя поздравить. Как у тебя получилось выкупить долю Mail.ru в «Хабре»? Никто же не будет продавать курицу, несущую золотые яйца
— Спасибо! Да, конечно, для этого пришлось довольно долго искать деньги.

Вторая часть довольно подробного и интересного изложения материала, касающегося кэша и его использования. Часть 1.

Автор, Mark Nottingham, — признанный эксперт в области HTTP-протокола и веб-кэширования. Является председателем IETF HTTPbis Working Group. Принимал участие в редактировании HTTP/1.1, part. 6: Caching. В настоящий момент участвует в разработке HTTP/2.0.

Текст распространяется под лицензией Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.

От переводчика: об опечатках и неточностях просьба сообщать в личку. Спасибо.

Данная статья посвящена объеденению нескольких домашних локальных сетей с предоставлением прозрачного общего доступа к ресурсам сетей с помощью VPN. За реализацию VPN взята openvpn. Клиенты и сервер openvpn установлены на роутерах домашних сетей, в конкретном случае роутеры семейства asus wl500, но данный мануал вполне применим и другим роутерам где есть досуп к OS и можно поставить openvpn.

Хотя подобных руководств в Интернете пруд пруди, они написаны больше для администраторов, которые имеют большой опыт общения с *nix системами, в то время как пользователями домашних роутеров являются в основном не хакеры, а обычные юзеры, может быть впервые увидевшие коммандную строку Linux на том самом роутере. Я постараюсь писать так чтобы было понятно всем.

Для тех кто не любит много букв, чтобы было понятно о чём речь под катом, привожу картинку

Это перевод статьи Джошуа Блоха «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken» 2006 года.

Я живо помню первую лекцию Джона Бентли в университете Карнеги-Меллон, на которой он попросил нас, свежеиспечённых аспирантов, написать функцию двоичного поиска. Он взял одно из решений и разобрал его на доске, и, разумеется, в нём оказалась ошибка, как и во многих других наших попытках. Этот случай стал для меня наглядной демонстрацией к его книге «Жемчужины программирования». Мораль в том, чтобы внимательно расставлять инварианты в программе.

И вот, теперь 2006 год. Я был потрясён, узнав, что программа двоичного поиска, корректность которой Бентли доказывал формально и тестами, содержит ошибку. Не подумайте, что я придираюсь; по правде сказать, такая ошибка вполне может ускользать от тестеров десятилетиями. Более того, двоичный поиск, который я написал для JDK, тоже был багнутым лет девять. И только сейчас, когда она сломала кому-то программу, о ней сообщили в Sun.

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

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

Этом цикле статей «Идеальный www кластер», я хочу передать базовые основы построения высокодоступного и высокопроизводительного www решения для нагруженных web проектов для неподготовленного администратора.
Статья будет содержать пошаговую инструкцию и подойдет любому человеку кто освоил силу copy-paste
Ошибки найденые вами, помогут в работе и мне и тем кто будет читать эту статью позже! Так что любые улучшение и правки приветствуются!

Хочу отметить, что эта инструкция родилась в процессе миграции web-систем компании Acronis в высокодоступный кластер. Надеюсь мои заметки будут полезны и для Вас!.

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

На frontend мы будем использоваться связку из двух службы:

keepalived — реализации протокола VRRP (Virtual Router Redundancy Protocol) для Linux. Демон keepalived следит за работоспособностью машин и в случае обнаружения сбоя — исключает сбойный сервер из списка активных серверов, делегируя его адреса другому серверу.

Другими словами, у нас 2 сервера на которых прописано по одному публичному адресу. Если любой из этих серверов падает, то адрес упавшего подхватывается вторым.
Демоны keepalived общаются по протоколу VRRP, посылая друг другу сообщения на адрес 224.0.0.18.
Если сосед не прислал свое сообщение, то по истечению периода он считается умершим и оба адреса обслуживает оставшаяся нода. Как только упавший сервер начинает слать свои сообщения в сеть, все возвращается на свои места

nginx [engine x] — это HTTP-сервер и обратный прокси-сервер, а также почтовый прокси-сервер, написанный Игорем Сысоевым. Уже длительное время он обслуживает серверы многих высоконагруженных российских сайтов, таких как Яндекс, Mail.Ru, ВКонтакте и Рамблер. Согласно статистике Netcraft nginx обслуживал или проксировал 15.08% самых нагруженных сайтов в октябре 2013 года.

Основная функциональность HTTP-сервера

• Обслуживание статических запросов, индексных файлов, автоматическое создание списка файлов, кэш дескрипторов открытых файлов;
• Акселерированное обратное проксирование с кэшированием, простое распределение нагрузки и отказоустойчивость;
• Акселерированная поддержка FastCGI, uwsgi, SCGI и memcached серверов с кэшированием, простое распределение нагрузки и отказоустойчивость;
• Модульность, фильтры, в том числе сжатие (gzip), byte-ranges (докачка), chunked ответы, XSLT-фильтр, SSI-фильтр, преобразование изображений; несколько подзапросов на одной странице, обрабатываемые в SSI-фильтре через прокси или FastCGI, выполняются параллельно;
• Поддержка SSL и расширения TLS SNI.

Другие возможности HTTP-сервера

• Виртуальные серверы, определяемые по IP-адресу и имени;
• Поддержка keep-alive и pipelined соединений;
• Гибкость конфигурации;
• Изменение настроек и обновление исполняемого файла без перерыва в обслуживании клиентов;
• Настройка форматов логов, буферизованная запись в лог, быстрая ротация логов;
• Специальные страницы для ошибок 3xx-5xx;
• rewrite-модуль: изменение URI с помощью регулярных выражений;
• Выполнение разных функций в зависимости от адреса клиента;
• Ограничение доступа в зависимости от адреса клиента, по паролю (HTTP Basic аутентификация) и по результату подзапроса;
• Проверка HTTP referer;
• Методы PUT, DELETE, MKCOL, COPY и MOVE;
• FLV и MP4 стриминг;
• Ограничение скорости отдачи ответов;
• Ограничение числа одновременных соединений и запросов с одного адреса;
• Встроенный Perl.

Про язык Go от команды Google слышали, наверное, все. А вот пробовали далеко не все, и очень зря — общение с сусликами Go это море удовольствия, в чем я недавно убедился на собственном опыте.
Начинать знакомство с новым языком забавнее всего на жизненном примере, поэтому я, не долго думая, взял первую попавшуюся задачу “из жизни, самой первостепенной важности”:

Есть в интернете сайт http://vpustotu.ru на котором любой желающий может анонимно высказаться о наболевшем. Все высказывания (в дальнейшем буду называть их “цитатами”) сначала попадают в модерацию (аналог “бездны” башорга), где посетители могут оценить полет мысли и проголосовать за цитату в стиле “Ого!” или “Ерунда!”. На странице модерации (http://vpustotu.ru/moderation/) нам показывают случайную цитату, ссылки голосования и ссылку “Еще”, которая ведет на эту же страницу. Пощелкайте, это все очень просто.

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

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

Таким образом нужна программа, которая:

• Должна последовательно обновлять и парсить (разбирать) страницу, записывая цитату.
• Должна уметь отбрасывать дубликаты.

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

• Должна останавливаться не только по команде, но и по достижению определенного числа “повторов”, например 500!
• Так как это, скорее всего, займет некоторое время: необходимо уметь продолжить “с места на котором остановились” после закрытия.
• Ну и раз уж все-таки это надолго – пусть делает свое грязное дело в несколько потоков. Хорошо-бы в целых 4 потока (или даже 5!).
• И отчитывается об успехах в консоль каждые, скажем, 10 секунд.
• А все эти параметры пускай принимает из аргументов командной строки!

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

Используя современный подход к разработке проектов начинаешь пользоваться прелестями менеджера пакетов, в случаe с разработкой на PHP это Composer. В данной статье мы кратко рассмотрим Composer и далее речь пойдёт о настройке локального кэша пакетов.

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

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

Как я могу судить, для людей, которые на практике не столкнулись с некоторыми специфическими проблемами, эти 2 понятия являются довольно трудными для понимания. И не потому, что понятия Promise и Deferred являются с чем-то сложным, а потому, что довольно непросто сходу выдумать подходящую задачу, чтобы попробовать Deferred objects (в JQuery и не только) в действии.

Да, вероятно для тех, кто знаком с этим вопросом он покажется пустяковым и не стоящим и выеденного яйца. Кроме того, вопрос уже многократно обсуждался. Однако, я наберусь смелости еще раз его затронуть и вот почему: 1) Мне кажется, что для некоторых читателей этот пост может оказаться интересным. 2) Я пойду от практики, а не от теории. Моя задача — продемонстрировать работу инструмента. Теорию и другие варианты применения при необходимости вы найдете в ссылках к посту.

Ниже я попробую показать вам что Promise и Deferred это очень и очень просто. Кроме того, для объяснения этой темы, мне придётся затронуть еще несколько интересных моментов JavaScript.

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

На странице есть набор элементов типа А, которые можно по одному или группой перетащить в элемент типа Б. Пользователь должен видеть, перетаскивает он один элемент или несколько. Перетаскивать один элемент просто, достаточно присвоить свойству draggable значение true, наверняка, все это делали.