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

Вместо вступления (перевод начался):

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Тема сегодняшней лекции

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

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

Ищем индекс

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

Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?

Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);

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

Интро

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

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

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

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

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

Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать. Взгляните на эту картинку:



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

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

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

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

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

Совсем недавно издательство No Starch Press подготовило и выпустило печатное издание замечательного учебника Learn You a Haskell for Great Good! (онлайн-версия), написанного Miran Lipovača.

Я хочу представить вам самый актуальный перевод главы 11 Аппликативные функторы, оригиналом для которого послужило именно издание от No Starch Press, адаптированное для печати.

За последнюю неделю появилось несколько топиков с названием «10 однострочников на <MY_LANGUAGE>, которые произведут впечатление на ваших друзей», которые содержат однострочное решение нескольких простых задач, демонстрирующее достоинства и «крутость» любимого языка программирования автора. Я решил перевести их и для сравнения собрать в одном топике. Вся волна началась (вроде как) со Scala.
Итак, поехали!

Привет Хабр! Хочу представить свою С/С++ библиотеку libral, которая с недавних пор стала open source под лицензией GPL3. Возможно кому-то она будет полезна. Библиотека предоставляет единый интерфейс к различным алгоритмам сжатия данных без потерь.
На данный момент поддерживаются библиотеки:

• libc — без сжатия
• zlib — www.zlib.net
• lzo — www.oberhumer.com/opensource/lzo
• snappy — code.google.com/p/snappy
• bzip2 — www.bzip.org

Всем привет.
Сегодня я расскажу вам как с помощью AndEngine написать небольшую игру. Стаья получилась довольно большая и, чтобы не утомлять читателя, пока мы остановимся на первой ее части. Все что нужно от читателя — это знание java, ООП и умение обращаться с Eclipse и Android SDK. Забегая вперед, у нас получится что то похожее на Mirrors Maze либо Laser Logic.
Вторая часть статьи.
Третья часть статьи.

Всем привет!
Как и обещал, вторая часть статьи.
Во избежание недопонимания, перед прочтением ознакомьтесь с первой частью статьи.
Уже ознакомились? Тогда добро пожаловать под кат где я познакомлю читателя с игровыми объектами.

Всем привет!
Вот и долгоданное продолжение цикла статей о том как создать для андроид не очень простую игру с помощью AndEngine.

Уже ознакомились с предыдущими статьями?
Часть 1
Часть 2
Тогда продолжим.

1. Выучить новый язык программирования

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

Среди языков программирования отличный познавательный эффект и наверстывание опыта дают: Lisp (или Scheme), Форт, PostScript или Factor (стековые языки программирования), Haskell (строго типизированный, чистый функциональный язык) либо OCaml (объектно-ориентированный язык функционального программирования), Пролог (логическое программирование), Erlang (отличные паралельные вычисления).

Вот и закончились очередные 72 часа, в течение которых порядка 300 команд пытались решить задание в рамках ежегодного соревнования от ICFP.

Предварительные результаты (замороженные за 12 часов до окончания), можно посмотреть на сайте организатора, там же можно прочитать и задание этого года.

Итак, список русскоязычных отчетов, найденных на просторах интернета:

Доброго времени суток, уважаемые Хабровчане!

Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке Java

Эта статья в (скорее всего, во всяком случае я надеюсь :) ) будет интересна для новичков, или кому-то применить как фундамент для своего решения данной задачи.
Кому интересно — прошу под кат

Межпроцессное взаимодействие (Inter-process communication (IPC)) — это набор методов для обмена данными между потоками процессов. Процессы могут быть запущены как на одном и том же компьютере, так и на разных, соединенных сетью. IPC бывают нескольких типов: «сигнал», «сокет», «семафор», «файл», «сообщение»…

В данной статье я хочу рассмотреть всего 3 типа IPC:

1. именованный канал
2. разделенная память
3. семафор

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

Введение

Так уж сложилось, что моя работа тесно связана с математическим моделированием физических процессов. Математическое моделирование — это совершенно особенная область программирования. Расчет даже относительно простого физического процесса может занимать несколько дней и даже недель. Поэтому на первый план выходит производительность программы, пускай даже в ущерб удобству написания и чтения кода. Однако до недавнего времени быстродействие моих программ меня мало заботило: вполне хватало грубых сеток, для которых расчеты занимали что-то около суток. Но постепенно сетки становились все подробнее, и время работы программ неуклонно росло. Тогда я стал искать узкие места в своей программе. Сначала в алгоритмах. Потом дело дошло до структур данных. И тут меня очень заинтересовал вопрос «а что же лучше использовать для хранения векторов: массивы или контейнеры?»