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

В этой части: компоненты пользовательского интерфейса. Предыдущая часть тут.

IntelliJ IDEA включает в себя большое количество пользовательских Swing-компонентов. Использование этих компонентов в ваших плагинах гарантирует, что они будут выглядеть и работать согласовано с остальным пользовательским интерфейсом IDE и часто позволяет уменьшить размер кода, по сравнению с использованием стандартных Swing-компонентов.

Меню и панели инструментов

Меню и панели инструментов (тулбары) строятся с использованием системы действий (как уже было описано во второй части).

За последнее время у меня накопилось достаточно материалов по разработке плагинов для IntelliJ IDEA, чем и собираюсь поделиться с хабрасообществом.

Среда разработки и инфраструктура

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

Для разработки плагинов подойдет любая современная версия Intellij IDEA – она уже включает в себя полный набор необходимого инструментария.

На прошедшем неделю назад чемпионате мира по командному программированию ACM ICPC 2013 было 11 задач, одну из которых за отведённое время не смогла решить правильно ни одна из команд.

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

В этом году на ACM ICPC был 21 аналитик из Швеции, Нидерландов, США, Словакии, Беларуси и России. И 10 из них были из Яндекса. Все они в разные годы были призёрами ICPC. Специально для Хабра они разобрали все задания чемпионата.

Введение

Данная статья является продолжением цикла статей: Использование паттерна синглтон [1], Синглтон и время жизни объекта [2], Обращение зависимостей и порождающие шаблоны проектирования [3], Реализация синглтона в многопоточном приложении [4]. Сейчас я хотел бы поговорить о многопоточности. Эта тема настолько объемна и многогранна, что охватить ее всю не представляется возможным. Здесь я заострю внимание на некоторых практичных вещах, которые позволят вообще не думать о многопоточности, ну или думать о ней в крайне минимальном объеме. Если говорить точнее, то думать о ней только на этапе проектирования, но не реализации. Т.е. будут рассмотрены вопросы о том, как сделать так, чтобы автоматически вызывались правильные конструкции без головной боли. Такой подход, в свою очередь, позволяет значительно уменьшить проблемы, вызванные состояниями гонок (race condition, см. Состояние гонки [5]) и взаимными блокировками (deadlock, см. Взаимная блокировка [6]). Этот факт уже сам по себе представляет немалую ценность. Также будет рассмотрен подход, который позволяет иметь доступ к объекту из нескольких потоков одновременно без использования каких-либо блокировок и атомарных операций!

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

Борьба за выход в финал была непростой, но честной: за время раунда не выявлено ни одного списывальщика.
Под катом — статистика по победителям и подробный разбор задач отборочного раунда:

• Задача A: Две башни
• Задача B: Депозит
• Задача C: Кеплер
• Задача D: Тест
• Задача E: Лазеры
• Задача F: Колесо

Заголовок, выраженный словами, понадобился только для поисковой находимости. Но речь пойдёт о роли символьной конструкции «|0» в JavaScript.

Впервые на неё я обратил внимание, когда переводил FAQ про asm.js и читал спецификации этого подмножества языка JavaScript. Там «|0» служит, например, для указания типа значения, возвращаемого из функции: увидели «|0» после значения — значит, перед нами знаковое целое.

Вдругорядь я заметил конструкцию «|0» в примере кода на Гитхабе, где происходило преобразование к целому числу результата деления на 1024².

Тогда глаза мои открылись, и я увидел прекрасные возможности:

( 3|0 ) === 3;       // целые числа не изменяет
( 3.3|0 ) === 3;     // у дробных чисел отбрасывает дробную часть
( 3.8|0 ) === 3;     // не округляет, а именно отбрасывает дробную часть
( -3.3|0 ) === -3;   // в том числе и у отрицательных дробных чисел
( -3.8|0 ) === -3;   // у которых Math.floor(-3.3) == Math.floor(-3.8) == -4
( "3"|0 ) === 3;     // строки с числами преобразуются к целым числам
( "3.8"|0 ) === 3;   // при этом опять же отбрасывается дробная часть
( "-3.8"|0 ) === -3; // в том числе и у отрицательных дробных чисел
( NaN|0 ) === 0;     // NaN приводится к нулю
( Infinity|0 ) === 0;     // приведение к нулю происходит и с бесконечностью,
( -Infinity|0 ) === 0;    // и с минус бесконечностью,
( null|0 ) === 0;         // и с null,
( (void 0)|0 ) === 0;     // и с undefined,
( []|0 ) === 0;           // и с пустым массивом,
( [3]|0 ) === 3;          // но массив с одним числом приводится к числу,
( [-3.8]|0 ) === -3;      // в том числе с отбрасыванием дробной части,
( [" -3.8 "]|0 ) === -3;  // и в том числе с извлечением чисел из строк,
( [-3.8, 22]|0 ) === 0    // но массив с несколькими числами вновь зануляется
( {}|0 ) === 0;                // к нулю также приводится пустой объект
( {'2':'3'}|0 ) === 0;         // или не пустой
( (function(){})|0 ) === 0;    // к нулю также приводится пустая функция
( (function(){ return 3;})|0 ) === 0;    // или не пустая

Итак, во-первых, перед нами удобное средство отбрасывания дробной части.

• По отношению к отрицательным числам оно полезно тем, что дробное число превращается не в ближайшее меньшее целое число (возрастая по модулю), как это случилось бы после «Math.floor()», а в ближайшее меньшее по модулю целое число (возрастая по значению). Нередко именно это и требуется.
   
• По отношению к положительным числам оно полезно уж тем одним, что конструкция «|0» более чем на порядок короче по сравнению с «Math.floor()». Поэтому она может и должна вызывать у разработчиков привыкание не меньшее, чем та принятая в jQuery запись «$()», о которой я говорил четыре дня назад, что с неё никто добровольно не перейдёт обратно на «document.getElementsByClassName()», например.

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

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



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

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

Изначально для основного освещения одной из комнат, где шёл капитальный ремонт, планировалась обычная люстра. Но недавно мне на глаза попалась суперяркая светодиодная лента Ultra 5000 со светодиодами smd 5630 торговой марки Arlight. Решение было принято быстро, окончательно и бесповоротно — хочу такую ленту в качестве основного света в комнате.

В последнее время появилось довольно много инструментов для создания сайтов в духе Metro UI. К сожалению, лично у меня, использовать что-то из этого в реальных проектах не получилось: либо страдает качество и приходится вставлять «костыли», либо с качеством все нормально, но нет стилей для нужных компонентов приложения (например, нигде нет стилей для datepicker-а).



Я попробовал написать свое с блэкджеком и шлюхами. Сначала это был просто набор стилей для компонентов, которые были нужны мне в первую очередь. Cейчас все становится похожим на довольно большой CSS framework.

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

Стили в архиве и документация лежат здесь: milk.ecm7.ru, есть .LESS и CSS версии.

Недавно мой студент и я пытались понять одну тонкость в стандарте C. Самый простой способ прояснить подобные вопросы — это узнать, учли ли её разработчики компиляторов, то есть написать код и посмотреть, что с ним будут делать разные компиляторы.

Я написал такую функцию:

int foo (char x) {
  char y = x;
  return ++x > y;
}

Так как ++x увеличивает на 1 значение x, очевидно, что функция должна возвращать "1" для большинства значений x. Вопрос состоит в том, что она вернет для значения CHAR_MAX?

CSS3 и HTML5 развиваются всё быстрее и быстрее, браузеры начинают поддерживать всё больше новых фишек и плюшек. В связи с этим, мне хотелось бы заглянуть в наш будущий рай верстальщиков и сделать цикл обзорных статей по новым плюшкам и фишкам этих технологий.
В этом цикле мне хотелось бы рассмотреть такие свойства CSS3, как transition, animate, opacity и модель rgba().

Использование CSS3.

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

На Хабре в свое время было несколько статей «Очень много полезных штук для AS3». Автор попытался собрать ссылки на самые полезные и интересные библиотеки. И т.к. в последнее время я разрабатываю под iOS, решил последовать его примеру и сделать то же самое, но для своей платформы. Описания почти прикладывать не буду, все есть на страничках проектов.

Топик — вольный перевод статьи Vim Plugins You Should Know About, Part I: surround.vim Петериса Круминса.

UPD: вторая часть

Что такое плагин surround.vim? Вот что говорит о нем автор, Тим Поп (Tim Pope):

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

В оригинале название звучит как «How Not To Sort By Average Rating». Я подумал, что дословный перевод «Как не сортировать по усреднённому рейтингу» будет малопонятен и хуже отражает содержание статьи.

Постановка проблемы

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

Неправильное решение №1

Рейтинг= (Число положительных оценок) - (Число отрицательных оценок)

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

Введение

Начнем с определения. Пусть у нас есть строка s_0..n-1. Полиномиальным хешем этой строки называется число h = hash(s_0..n-1) = s₀ + ps₁ + p²s₂ +… + p^n-1s_n-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а s_i — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

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

Многие из нас выросли на «Танчиках», «Марио» и прочих нетленных шедеврах времён рассвета игровой индустрии. Приятно порой вспомнить, как днями напролёт резались с друзьями у экранов телевизоров, меняя джойстики как перчатки. Но время не стоит на месте, и одни интересы сменяются другими. Однако, порой любовь к старым-добрым игрушкам не угасает.
Я отношу себя к людям именно таким, и мой интерес к старым играм пошёл в сторону реверс-инжиниринга, что и привело меня в IT-сферу, где я и осел с концами.

Я хочу рассказать вам о том, что же под капотом у железных монстров из знаменитой игры Battle City (в простонародье «Танчики») с не менее знаменитой приставки Nintendo Entertainment System (сокращённо NES, в России более известен её китайский клон «Dendy»). Мне в своё время эта информация показалась довольно любопытной — надеюсь, такой же она покажется и вам.

Первая часть.

Во второй части будут рассмотрены арифметическое кодирование и преобразование Барроуза-Уилера (последнее часто незаслуженно забывают во многих статьях). Я не буду рассматривать семейство алгоритмов LZ, так как про них на хабре уже были неплохие статьи.

Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.