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

Однажды на пикнике я заметил математиков, толпящихся возле игры, интереса к которой я ожидал меньше всего: крестики-нолики.

Вы могли и сами заметить, что игра крестики-нолики смертельно скучна. В ней нет места творческой идее или внезапному озарению. Хорошие игроки всегда играют вничью. Игра неизбежно идёт примерно так:



Но математики на пикнике играли в более изощренную версию игры. В каждой из клеток на квадратном поле они нарисовали поле поменьше:

От переводчика: Хоть посыл статьи Najaf Ali, переведённой ниже, и носит слегка рекламный оттенок («оставьте криптографию нам, экспертам»), но описанные в ней примеры показались мне довольно интересными и заслуживающими внимания.
Кроме того, никогда не будет лишним повторить прописную истину: не придумывайте свою крипто-защиту. И эта статья отлично иллюстрирует почему.

В этой части попробуем сделать “невозможное”: научимся использовать графический дисплей без операционной системы. На самом деле это задача не из легких, особенно в случае работы в 32-х битном защищенном режиме, и особенно если хочется использовать приличное разрешение экрана а не 320x200x8. Но все по порядку: раз хотим графику – значит нужно работать с видеокартой.

Современные графические карты – это практически полноценные компьютеры по мощности не уступающие основному: тут и декодирование MPEG2 в качестве 1080p, поддержка 3D графики и шейдеров, технологии вроде CUDA, и многое другое. Это все выглядит весьма сложно. С другой стороны видеокарты – это всего лишь очередной PCI девайс, такой же, как и остальные. Это устройство мы даже “нашли” в предыдущей статье с номером класса устройства 0x03 (class_name=graphics adapter). Как и с любым, устройством с видеокартой можно работать при помощи портов ввода-вывода или MMIO областей памяти, а сама видеокарта может использовать DMA и прерывания для взаимодействия с основным процессором. Если посмотреть на диапазон портов ввода-вывода, доступных у видео карт, то мы увидим, что всего ей выделяется менее 50-ти байт – не так уж и много с учетом огромной функциональности, которой обладают современные видеокарты.

Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

Алгоритм Эллера позволяет создавать лабиринты, имеющие только один путь между двумя точками. Сам по себе алгоритм очень быстр и использует память эффективнее, чем другие популярные алгоритмы (такие как Prim и Kruskal), требуя памяти пропорционально числу строк. Это позволяет создавать лабиринты большого размера при ограниченных размерах памяти.

Достаточно давно и долго говорят о том что с использованием высоких скоростей GPU подбор паролей существенно ускорится. Но есть технологии которые позволяют перебор сделать еще
быстрее. Швейцарская компания, специализирующаяся в области безопасности Objectif Sécurité воспользовалась для своей технологии SSD дисками с радужными таблицами.

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

В интернете существует огромное количество описаний и туториалов о для того как написать собственную мини-ОС, даже существуют сотни готовых маленьких хобби-ОС. Один из наиболее достойных ресурсов по этой тематике, который хотелось бы особо выделить, это портал osdev.org. Для дополнения предыдущей статьи про PCI (и возможности писать последующие статьи о различных функциях, которые присутствуют в любой современной ОС), мы опишем пошаговые инструкции по созданию загрузочного диска с привычной программой на языке С. Мы старались писать максимально подробно, чтобы во всем можно было разобраться самостоятельно.

Итак, цель: затратив как можно меньше усилий, создать собственную загрузочную флешку, которая всего-навсего печатает на экране компьютера классический “Hello World”.

Это статья была написана для людей, которым всегда интересно знать как работают разные вещи. Для тех разработчиков которые обычно пишут свои программы на высоком уровне, C, C++ или Java — не важно, но при этом столкнулись с необходимостью сделать что-то на низком уровне. Мы будем рассматривать низкоуровневое программирование на примере работы bootloader-а.

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

Месяц назад здесь было объявлено, что Алексей Брагин теперь читает авторский курс лекций об операционных системах. С тех пор Алексей успел провести уже несколько занятий, которые были записаны на видео. Думаю, вполне логичным шагом будет поделиться этими записями с сообществом. Что нам стоит поступить так же как, к примеру, сделал MIT?

Прошу принять во внимание, что это пилотный проект. А так конструктивная критика приветствуется, пожелания принимаются.
Приносим извинения за качество звука, смотреть лучше в HD и погромче.

Прежде всего отметём возможное недоразумение: сегодня речь у нас пойдёт не о том движке, который известен старожилам джаваскриптового программирования под названием JSDB и до сих пор располагается по адресу JSDB.org. Тот движок, основанный на мозилловском SpiderMonkey, хотя и обладал богатыми возможностями для доступа к базам данных, к электронной почте и к Интернету, но после появления гораздо более резвого «конкурента» (Node.js) постепенно впал в совершеннейшее забвение, так что и сказать о нём мне сегодня нечего.

Вместо него я намерен вдругорядь привлечь ваше внимание к той базе данных о библиотеках джаваскриптов, которая появилась в нынешнем (2013 года) феврале по адресу JSDB.io и открыта для пополнения читателями. (Пишу «вдругорядь» оттого, что на JSDB у вас и ранее была некоторая возможность обратить внимание: сперва mourner упомянул её во твиттере у своей библиотеки Leaflet, а затем alexzfort упомянул её в дайджесте новинок прошлой недели.)

Чем JSDB радует? Продуманностью интерфейса и широким употреблением AJAX для внесения изменений в страницы без перезагрузки. (В итоге интерфейс получается, например, куда более интерактивным и удобным, нежели у тематически сходной вики jswiki или у порождённого этой вики сайта «JavaScript Territory».) Сперва перечисление библиотек с открытым исходным кодом кажется на JSDB простым списком. Однако, так как в JSDB принимаются библиотеки с открытым исходным кодом, на Гитхабе лежащем, то у JSDB есть приятная возможность отреагировать на жмяк мышóю по заглавию той или иной джаваскриптовой библиотеки, автоматически открыв информационную панель с кратким описанием библиотеки, с подсчётом её форков и звёзд и участников её разработки на Гитхабе. (Эта панель развёртывается на месте жмякнутого пункта, раздвигая остальные пункты списка.) Ещё сильнее обрадует обстоятельного читателя вкладка «Readme», позволяющая для справки целиком подкачать с Гитхаба текст Readme-файла выбранной библиотеки, никуда с JSDB не уходя для этого.

А которую пользу сайт JSDB приносит? А вот такую: его содержимое служит расширителем кругозора. Как не следи за развитием современного открытого исходного кода, а всё же упустишь появление пары-тройки-другой библиотек (или отметёшь их в зародыше как бесперспективняк, ан они со временем разовьются в нечто необыкновенно удобное), так что полезно встретить их на JSDB и познакомиться с их продуктивными возможностями.

Понятно, что у каждого из читателей такой список из пары-тройки-другой библиотек, на JSDB с интересом обнаруженных, будет своим. О вкусах и не спорят. Для сведения читателей я счёл, однако, не лишним перечислить и полдесятка моих находок.

После прочтения поста на хабре «Шахматный бот», хотелось сделать свой, но так как посчитал, что шахматы сразу не получатся, то решил потренироваться на шашках (чтоб было больше мотивации взял знаменитые «Русские стрип-шашки»).
В отличии от выше упомянутого поста, где только несколько скринов и видеоролик, постараюсь рассказать подробнее…

Автор статьи — Joe Armstrong, разработчик Erlang

Я, как программист-старожил, люблю иногда вспоминать свою молодость …

Когда, в далеком 1967, я только начинал учиться программировать, я выбирал между языками Fortran и Algol. Про Algol ходило множество слухов, но практически никакой полезной информации нельзя было найти, так что я начал с Fortran.

На написание одной программы в среднем уходило 3 недели:

неделя 1 — написание программы на бумаге и отправка в компьютерный центр, где мне делали перфокарты;
неделя 2 — проверка перфокарт, и загрузка их в компьютер;
неделя 3 — получение и анализ результатов.

Когда компилятор доходил до первой синтаксической ошибки в программе, — он останавливался, и это отбрасывало меня обратно в самое начало, к первой неделе. Для исправления 10 ошибок в программе могло потребоваться 30 недель!

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

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

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

Честно говоря, я не ожидал такого количества решений: за 24 часа было прислано 265 решений, из которых после удаления повторных отправок осталось 183.

Из 183 решений у 11 был превышен допустимый размер решения, в 19 случаях — не удалось скомпилировать (об этих ошибках подробнее ниже). Далее 47 дали неправильные ответы на простых тестах (1..1000000), 8 не успели посчитать ответ за минуту (образец решения из условия задачи для 1млн работал 5 минут 36 секунд).

На сложных тестах — 5 решений выдали неверный ответ, и 12 — не уложились в одну минуту. 86 — успешно прошли все тесты.

Если кто потерял, вот топик о старте соревнования с условиями задачи.

Очередной проект который мне приходится делать, требует этих самых круглых углов. Поговорив с заказчиком и дизайнером пришли к выводу что в Internet Explorer 8 нужны эти самые круглые углы. Что собственно и привело меня к тому что бы реализовать простейший и более быстрый способ организации таких рамочек, кнопочек и прочих фишечек на сайте. Без использования картинок и скриптов. При реализации данного метода, пришлось столкнутся с некоторыми подводными камнями и искать обходные пути. Что из себя представляет мой метод реализации и с чем мне пришлось столкнутся, читайте ниже.

В этой статье я расскажу о внутреннем устройстве популярного сервиса облачного хранения Dropbox. В частности, будет затронуто устройство протокола Dropbox, а также показана статистика его использования в некоторых странах Европы. Кроме этого, я сравню его с другими сервисами, такими как iCloud, Google Drive и SkyDrive.

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

Текст основан на научной статье “Dropbox изнутри: Изучаем сервисы облачного хранения” (Inside Dropbox: Understanding Personal Cloud Storage Services). PDF

На днях в Москве прошла «конференция разработчиков высоконагруженных систем» HighLoad++, участником которой мне посчастливилось стать. Ниже я хочу кратко пройтись по докладам, которые посетил в рамках конференции, выделив в них интересные на мой взгляд моменты.

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

Оптимизация настроек всегда дело тонкое и выставить именно те параметры, которые дадут максимальную производительность, зачастую можно только уже в процессе работы приложения, когда уже есть статистика нагрузки и видны узкие места.
Но очень полезно сделать и первичную оптимизацию при запуске СУБД. В этом посте рассмотрены пути автоматической оптимизации MySQL и PostgreSQL утилитами mysqltuner и pgtune.

Мне очень нравится JavaScript и я считаю его мощным и удобным. Но для большинства начинающих JS-программистов, много проблем создаёт недопонимание аспектов языка. Часто конструкции языка ведут себя «нелогично». В данной статье я хочу привести примеры «граблей», на которые я наступил; объяснить поведение языка и дать пару советов.