Search
Write a publication
Pull to refresh
28
0
Константин Некрасов @knekrasov

User

Send message

Рандомизированные деревья поиска

Reading time8 min
Views58K

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

Russian Code Cup 2012: Разбор задач второго квалификационного раунда

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



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

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

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

Ну а теперь перейдем к задачам.
Читать дальше →

Карринг vs Частичное применение функции

Reading time7 min
Views22K

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


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

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

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

User experience design: как построить сайт для клиентов, а не для себя

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

UX

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

Читать дальше →

Do It Yourself Java Profiling

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

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

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

Reading time14 min
Views219K
Уровень: начинающим

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


Введение


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



Я хочу попробовать что-нибудь виртуализовать

Очередная схватка с веб-вирусами

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

Размеры массивов в Java

Reading time2 min
Views32K
Размеры объектов в 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: фрактал плохого дизайна

Reading time32 min
Views207K

Предисловие


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

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

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

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

Java сертификация. Подготовка к SCJP

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

Уточнение


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

JavaScript на сервере, 1ms на трансформацию

Reading time8 min
Views32K

Зачем?



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

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

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

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

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

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

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

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

«Доктор Веб» обнаружил ботнет из более чем 550 000 «маков»

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

Читать дальше →

Linux, безопасность и все такое… (вдогонку)

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

Изучение способов привлечения на сайт программного продукта

Reading time11 min
Views4K

Аннотация


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

Создаём простейший виджет для Mac OS X Dashboard

Reading time6 min
Views11K
Здравствуйте, хабравчане-маководы!
Картинка поста
Сегодня мы с вами попробуем разобраться в азах создания виджета для Dashboard в Mac OS X. Нам понадобится программа Dashcode, предназначенная как раз для этого.

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

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

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

16 инструментов для создания прототипов

Reading time5 min
Views496K


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

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

16 инструментов со ссылками и их краткое описание

Архитектура Android-приложений. Часть I — истоки

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

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

На пути к Skein: просто и понятно про Blowfish

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


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

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

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

И он появился.
Читать дальше →

Написание компилятора LALR(1)-парсеров. Описание LR-генераторов

Reading time10 min
Views15K

Предисловие


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

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

Jooq — «LINQ» для Java, типобезопасный построитель SQL запросов в Java коде

Reading time5 min
Views26K
Недавно, в поисках золотой середины между 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:

Читать дальше →

Information

Rating
8,437-th
Location
Воронеж, Воронежская обл., Россия
Date of birth
Registered
Activity