Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.

В минувшую субботу прошел второй квалификационный раунд олимпиады по программированию Russian Code Cup 2012.



Russian Code Cup — индивидуальное соревнование по спортивному программированию, ежегодно проводимое Mail.Ru Group. Оно традиционно состоит из трех этапов: в начале лета проходят три квалификационных раунда, затем лучшие принимают участие в отборочном туре, первые пятьдесят победителей отборочного тура соревнуются в финале. Личного присутствия потребует только последний из них, остальные же проводятся онлайн. Все финалисты будут отмечены ценными подарками, а приз участнику, занявшему первое место, составит 10 000 долларов. За второе и третье место полагаются 5 000 и 3 000 долларов.

В данной статье я подробно разберу задачи, вынесенные на конкурс, а также поделюсь статистикой раунда. Я постарался разъяснить детали настолько, чтобы решение задач было понятно даже тем, кто еще делает первые шаги. Также данный материал поможет получить представление, какой сложности задачи предлагаются на отборочных этапах чемпионата по программированию Russian Code Cup.

В это воскресенье, 10 июня, в 11:00, будет проходить последний квалификационный раунд, из которого две сотни участников перейдут в «полуфинал» — отборочный раунд. На втором раунде для этого достаточно было решить две задачи — одну простую и одну сложную, и уложиться при этом в половину отведенного времени. Ждем вас в воскресенье и желаем удачи!

Ну а теперь перейдем к задачам.

Перевод статьи Джона Скита, известного гуру языка C#, автора книги C# In Depth, сотрудника Google, человека #1 по репутации на stackoverflow.com и наконец героя Jon Skeet Facts. В этой статье Джон доступно объясняет, что представляют из себя карринг и частичное применение функции, концепции, пришедшие из мира функционального программирования. Кроме того, он подробно поясняет в чём их различие. Признаюсь, что я и сам их путал до прочтения этой статьи, поэтому мне показалось полезным сделать перевод.


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

• Те, кто не интересуются функциональным программированием и находят функции высшего порядка запутанными: вы можете пропустить эту статью полностью.
• Те, кто знают всё о функциональном программировании и хорошо понимают разницу между каррингом (currying) и частичным применением функции (partial function application): пожалуйста, внимательно прочтите этот пост и отпишитесь в комментариях, если найдете неточности.
• Те, кто частично знаком с функциональным программированием, и заинтересован узнать больше: отнеситесь к этому посту скептически и внимательно прочтите комментарии. Прочитайте другие статьи более опытных разработчиков для получения дополнительной информации.

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

В конце апреля я делал доклад на РИФ 2012 про этапы проектирования пользовательского интерфейса. Так как видео нет, попробую представить доклад в виде слайдов с моими комментариями.



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

На прошедшей конференции Appication Developer Days, Роман Елизаров (elizarov) рассказал, как профилировать, т.е. исследовать производительность любых Java-приложений, без использования специализированных инструментов, будь они хоть вендорские, хоть open-source.Оказывается, можно использовать малоизвестные, встроенные в JVM возможности (threaddumps, java agents, bytecode manipulation), и быстро и эффективно реализовать профилирование, которое можно запускать постоянно даже на боевой системе.Вот видео доклада (тут оно косолапо эмбедится, но оно 1280x720, все отлично читаемо):

Но я предлагаю также, взглянуть на 70K текста иллюстрированной статьи-стенограммы под катом, составленной мной по видео и слайдам.

Уровень: начинающим

Опыт использования виртуализации на VirtualBox

Введение

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

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

Размеры объектов в Java уже обсуждались на Хабре, например, здесь или здесь. Мне бы хотелось подробнее остановиться на размерах многомерных массивов — простая вещь, которая для меня стала неожиданной.

Оптимизируя вычислительный алгоритм по памяти, я наткнулся на то, что при определённых (вполне разумных) входных параметрах создаётся массив float[500][14761][2]. Сколько он может занимать в памяти (на HotSpot 1.6.0_26 32bit, если кому интересно)? Я примерно прикинул, что 500*14 761*2*sizeof(float) = 500*14 761*2*4 = 59 044 000 байт плюс какой-то оверхед. Решив проверить, как на самом деле, я воспользовался Eclipse Memory Analyzer (невероятно волшебная вещь, рекомендую!) и обнаружил, что «Retained Heap» для этого массива составляет 206 662 016 байт! Неплохой оверхед — 350%. Посмотрим, почему так получилось.

Предисловие

Я капризный. Я жалуюсь о многих вещах. Многое в мире технологий мне не нравится и это предсказуемо: программирование — шумная молодая дисциплина, и никто из нас не имеет ни малейшего представления, что он делает. Учитывая закон Старджона, у нас достаточно вещей для постижения на всю жизнь.

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

PHP — единственное исключение. Фактически каждая деталь PHP в какой-то мере поломана. Язык, структура, экосистема: всё плохо. И даже нельзя указать на одну убийственную вещь, настолько дефект систематичный. Каждый раз, когда я пытаюсь систематизировать недостатки PHP, я теряюсь в поиске в глубину обнаруживая всё больше и больше ужасных мелочей(отсюда фрактал).

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

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

Уточнение

Так как Sun'a больше нет, то и экзамена SCJP тоже нет. Теперь он значится так:
1Z0-851 Java Standard Edition 6 Programmer Certified Professional Exam.

Зачем?

Вопрос “Зачем?” — самый главный при принятии любого решения. В нашем случае причин было несколько.

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

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

Но в Mail.Ru Group есть целая команда высококвалифицированных людей, знающих JS, способных самостоятельно написать инструмент, а самое главное — они же им и будут пользоваться.

Во-вторых, задачи. Возьмем проект Почта@Mail.ru. Мы не можем отказаться от шаблонизации на сервере – нам нужна быстрая загрузка при первом входе. Мы не можем отказаться от шаблонизации на клиенте – люди должны видеть высокую скорость реакции на их действия, а значит, обязателен AJAX и шаблонизация на клиенте.

Проблема очевидна: два набора совершенно разных шаблонов на сервере и на клиенте. А самое обидное, что решают они одну и ту же задачу. Дублирование логики нас просто измотало.

v8 — это интерпретатор JavaScript, а значит, мы можем получить один шаблон, который работает как на сервере, так и на клиенте.

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

Специалисты компании «Доктор Веб» провели специальное исследование, позволившее оценить картину распространения троянской программы BackDoor.Flashback, заражающей компьютеры, работающие под управлением операционной системы Mac OS X. Сейчас в ботнете BackDoor.Flashback действует более 550 000 инфицированных рабочих станций, большая часть которых расположена на территории США и Канады. Это в очередной раз опровергает заявления некоторых экспертов об отсутствии угроз для пользователей «маков».

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

Аннотация

Эта статья будет интересна тем, кто продвигает свои собственные программные продукты в интернете. Статья исключительно практическая. Она представляет собой отчёт о некоторых действиях, которые мы осуществляли в последнее время для продвижения продукта PVS-Studio. Я расскажу, что работает, что не работает и поделюсь сопутствующими мыслями.

Здравствуйте, хабравчане-маководы!

Сегодня мы с вами попробуем разобраться в азах создания виджета для Dashboard в Mac OS X. Нам понадобится программа Dashcode, предназначенная как раз для этого.

Для начала немного теории. Виджет в Dashboard — это специально сформировання веб-страничка, упакованная в бандл вместе со всем ресурсами. Ну, и немного служебной информации в довесок. Соответственно, используемый язык программирования — JavaScript. Если Вы уже знакомы с ним, а так же с HTML/CSS (хотя это вряд ли понадобится), то Вы уже способны написать простенький виджет. Если же нет, то не стоит расстраиваться, этот язык очень прост и интуитивно понятен, разобраться с ним можно достаточно быстро. Далее я буду считать, что с JS читатель более-менее знаком. Сама же статья рассчитана на новичков, так что прошу не ругать за «слишком простое изложение и детальное разжёвывание элементарных вещей». Кроме того, за дизайн тоже прошу не пинать — ну не дизайнер я, не дизайнер! Если кто хочет помочь с этим делом — welcome =)

Для удобства, все исходники (а так же готовый к использованию виджет) выложены на гитхаб, ссылка в конце статьи. Но не спешите просто скачивать их! Лучше потратить немного времени и разобраться, как создать это всё самому.

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

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

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

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

В этой статье мы рассмотрим архитектуру Android-приложений.

Откровенно говоря, официальную статью Google по этой теме я считаю не очень полезной. Детально отвечая на вопрос «как», она совсем не объясняет «что» и «почему». Итак, вот моя версия, и, я надеюсь, она внесёт некоторую ясность. Да, кстати, я полностью одобряю чтение статей Google, поскольку они содержат полезную информацию, повторять которую я не собираюсь.

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

                                Википедия, свободная энциклопедия.

К концу 1993 года в мире криптографии возникла очень неловкая ситуация. Алгоритм симметричного шифрования DES, со своим слабеньким 56-битным ключом, был близок к фиаско, а существующие
на тот момент альтернативные варианты, такие как Khufu, REDOC II, IDEA были защищены патентами
и не доступны для свободного использования. Алгоритмы RC2 и RC4, разработанные в то время компанией RSA Security, также требовали проведение процедуры лицензирования. И в целом, индустрия криптографии в рамках государственных организаций и крупных корпораций была
обращена в сторону использования секретных алгоритмов, таких как Skipjack.

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

И он появился.

Предисловие

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

В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.

Недавно, в поисках золотой середины между JDBC и ORM, я натолкнулся на интересную open source библиотеку (лицензия Apache Software License), с помощью которой можно строить SQL прямо в Java-коде достаточно удобно и безопасно. Библиотека называется Jooq. Jooq включает в себя генератор кода, который парсит структуру вашей базы данных и создает необходимые Java-классы. На деле получается примерно такой код:

Integer taskId = sqlFactory.select(ID).from(TASK).where(STATUS.equal(TaskStatus.QUEUED)).
    orderBy(LAST_UPDATED).limit(1).fetchOne(ID);

Как видите, конструирование запроса и его выполнение для простых типов занимает одну строку. Немного о jooq: