Про Unsafe в Java не слышал только ленивый, однако это не единственный магический класс в Sun/Oracle JDK, стирающий границы Java платформы и открывающий тропинки, не нанесенные на карту публичного API. Я расскажу про некоторые из них, принесшие пользу в реальных проектах. Но помните: недокументированные возможности лишают ваше приложение переносимости на другие Java платформы и, кроме того, являются потенциальным источником нетривиальных ошибок. Я даже зря написал слово «приложение». Лучше сказать, что описанные ниже классы вовсе не годятся для приложений! Скорее, они представляют интерес лишь для системного ПО и для любознательных программистов, т.е. для вас :)

Реализованное нами в прошлый раз атомарное умножение является примером более общей модели, которую Реймонд назвал «сделай, запиши,(попытайся снова)».

for (;;) {
 // берём начальное значение общей переменной,
 // которую мы собираемся изменять
 oldValue = sharedVariable;

 ... берём начальные значения других параметров ...

 newValue = ... вычисляем новое значение, используя
                oldValue и копии остальных параметров ...

 // вместо Xxx может быть Acquire, Release, или ничего
 if (InterlockedCompareExchangeXxx(
            &sharedVariable,
            newValue, oldValue) == oldValue) {
  break; // запись удалась
 }

 ... удаляем newValue ...

} // попытаемся снова

Мы вычисляем новое значение, и затем вызовом InterlockedCompareExchange записываем его в общую переменную только в том случае, если её значение не изменялось. Если оно изменилось, значит другой поток нас опередил; в этом случае попытаемся выполнить операцию по-новой, с самого начала, — в надежде, что в следующий раз никто нас не «подрежет».

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

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

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

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

Задача

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·10⁹.

Технические условия

Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.

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

_{«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.}
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.

В прошлый раз мы говорили о том, что число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.


Распространённый ответ на этот вопрос я получу сразу: «Разумеется, произвольных деревьев больше, т.к. бинарное дерево – это частный случай произвольного дерева». Можете ли вы сказать, почему это неверно? Бинарных деревьев больше, чем произвольных деревьев! Существует два бинарных дерева из двух вершин: одно с левым потомком ребёнком корня, а другое – с правым потомком корня. Но есть только одно произвольное дерево с двумя вершинами, в нём нет разницы между «левым» и «правым» потомком.

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.

Заранее предупреждаю, для тех кто в теме, интересного будет не очень много. :)

У меня появилась актуальная задача реализовать базовые примитивы синхронизации(мьютекс, семафор и read/write lock), используя только синхронную очередь — единственный доступный примитив. Заодно по пути я расскажу как устроены спинлоки и мы даже соберём маленького франкенштейна.

Часть 1: Всё — очереди

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

Что это ?

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

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

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

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

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

1. Вместо вступления.

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

Собственно, главное отличие алгоритма от, например, «наивного сравнения», заключается в том, что в его основе лежит логические операции, а именно логическое умножение (оно же AND, оно же конъюнкция).

Довольно часто программисты в своей работе встречаются с необходимостью работать со случайными числами. Чаще всего случайные числа требуются в задачах моделирования, численного анализа и тестирования, но существует и множество других весьма специфических задач.
Конечно, во всех современных языках программирования есть функция random или её аналоги. Эти функции чаще всего дают действительно хорошие псевдослучайные числа, но мне всегда было интересно, как эти функции работают.
В этом топике я постараюсь объяснить, как работает линейный конгруэнтный метод (который чаще всего используется в функции random), и метод получения случайных чисел с помощью полиномиального счётчика (который часто используется для тестирования аппаратуры).

В апреле-мае 2011 года компания Яндекс проводила очередной тур конкурса Яндекс интернет математика. Тема тура: «Определение визуальной схожести изображений».
Я публиковал новость про объявление победителей и обещал в скором времени описать решение поставленной задачи нашей командой — LookLikeIt, которая заняла 12-е место в финальном рейтинге.

И вот, не совсем скорое время наступило!

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

Классификация

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

Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в Facebook пытается подтвердить теорию шести рукопожатий. Для тех кто не в курсе, эта теория заключается в том, что все жители земли в среднем знакомы друг с другом через цепочку из пяти друзей (т.е. шести рукопожатий). Подробнее об истории этой теории можно прочитать в википедии, там же можно узнать о том, что Майкрософт несколько лет назад пыталась подтвердить эту теорию на основе данных о контакт-листах мессенджера MSN — в результате у них получилось 6,6 рукопожатий, что вполне вписывается в теорию.

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

1. На каких данных это все расчитывать.
2. Где эти данные взять.
3. Как эти данные сохранять.
4. Каким алгоритмом воспользоваться для расчетов.

Сколько я себя помню, всегда мечтала сделать процессор. Наконец, вчера я его сделала. Не бог весть что: 8 бит, RISC, текущая рабочая частота — 4 кГц, но он работает. Пока что в программе моделирования логических цепей, но все мы знаем: «сегодня — на модели, завтра — на деле!».

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

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

Описание тестовой лаборатории:

• Сервер виртуализации Xen. Dom0 под SLES11
• 3 Xen DomU виртуальных сервера под quorum-ноды с двумя дополнительно проброшенными блочными устройствами
• 2 Xen DomU виртуальных сервера под client-ноды

Тестовый стенд, основанный на технологии Xen, крайне удобен, ибо позволяет на ходу подцеплять/отцеплять диски от виртуалок, добавлять в них память и процессоры.

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

Давайте каждый попробует ответить на вопрос: как установить apache на сервер? Этот вопрос порождает ещё десяток: какая ОС стоит на сервере, какую версию ставить, где лежат конфиги по-умолчанию и т.д. и т.п.

А теперь давайте попробуем ответить на вопрос: как установить apache на 1000 серверов? Тут, при стандартном подходе, вопросов возникнет ровно в 1000 раз больше. Часть из вас наверняка подумали, что можно написать скрипт на shell/perl/python/ruby, который будет обходить все сервера и устанавливать apache, другая часть подумала о distributed shell'ах (PDsh, dsh, etc), кто-то же подумал монтировать rootfs серверов по NFS.

В ряде случаев выше предложенные варианты решений удовлетворительны, но на практике я нигде не видел полностью гомогенных систем (зачастую, внутри компании можно встретить не только разные версии ОС, но и различные дистрибутивы. Также в России/СНГ очень распространена каша из FreeBSD/Linux в ядре проектов), так что вряд ли за адекватное время будет возможно написать скрипт, который установит и настроит apache на зоопарке в 1000 машин под CentOS, Debian, Ubuntu, FreeBSD всевозможных версий.

По моим наблюдениям, очень мало IT подразделений, даже очень крупных компаниий, используют в своей работе SCM (Software Configuration Management). В этом посте я постараюсь описать все преимущества использования Chef в IT инфраструктуре на простых примерах и больших масштабах.

Если же, после столь короткого вступления, вы не прониклись идеей Chef, да и времени читать длинный технический пост у вас нет, то рекомендую вам пролистать до конца и посмотреть как используем Chef мы, Engine Yard, 37signals и подумать, можете ли вы переложить на него часть своей работы.