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

Что это ?

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

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

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

Я могу ошибаться, но мне кажется что всем хорошо известный Spring Framework достиг своей вершины к версии 2.5 (когда внедрили активное использование аннотаций) и дальше идет по сути дела «полировка» — даже major-релиз 3.0 не сильно отличается от 2.5. Тоже самое можно сказать и про грядущий 3.1 — небольшие улучшения, фишечки — но не более того. Однако одна «фишечка» в 3.1 показалась мне особенно интересной — это кеширование.

С ростом популярности web-приложения его поддержка неизбежно начинает требовать всё больших и больших ресурсов. Первое время с нагрузкой можно (и, несомненно, нужно) бороться путём оптимизации алгоритмов и/или архитектуры самого приложения. Однако, что делать, если всё, что можно было оптимизировать, уже оптимизировано, а приложение всё равно не справляется с нагрузкой?

Введение

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

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

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

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

На вопрос, как сделать AJAX запрос к другому домену, я всегда отвечал, что никак, и предлагал в качестве альтернативы jsonp, прокси, флеш, фреймы. Но, оказывается, большинство современных браузеров (IE8+, FF3.5+, Chrome 6+ и Safari 4+) вполне поддерживает кроссдоменный XMLHTTPRequest.

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

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

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

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

Жизнь была прекрасна и все было в этом мире хорошо, пока почта с моего сайта не стала активно посылаться в спам практически всеми крупными почтовыми серверами. Особенно усердствовал в этом Gmail. Частенько меня принимали за спамера в Yandex, реже в mail.ru и rambler.

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

Привет, Хабрачитатель!
Полнотекстовый поиск данных в InnoDB – это известная головная боль многих разработчиков под MySQL / InnoDB. Для тех, кто не в курсе дела я объясню. В типе таблиц MyISAM есть полноценный полнотекстовый поиск данных, однако сама таблица исторически имеет ограничения, которые являются принципиальными в отдельных проектах. В более «продвинутом» типе таблиц InnoDB полнотекстового поиска нет. Вот и приходится мириться бедным разработчикам либо с ограничениями MyISAM, либо с отсутствием поиска в InnoDB. Я хочу рассказать о том, какие есть способы организовать полноценный поиск в InnoDB без магии и исключительно штатными средствами. Также будет интересно сравнить скоростные характеристики каждого способа.

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

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

Предупреждаю, что статья содержит около 2000 слов (8 страниц А4), но дорогу осилит идущий.

Начиная с версии 5.1 mySQL поддерживает горизонтальное партицирование таблиц. Что это такое? Партиционирование (partitioning) — это разбиение больших таблиц на логические части по выбранным критериям.. На нижнем уровне для myISAM таблиц, это физически разные файлы, по 3 на каждую партицию (описание таблицы, файл индексов, файл данных). Для innoDB таблиц в конфигурации по умолчанию – разные пространства таблиц в файлах innoDB (не забываем, что innoDB позволяет настраивать индивидуальные хранилища на уровне баз данных или даже конкретных таблиц).

Как это выглядит?

В свете нынешней эпохи определения всего и вся аннотациями предлагаю вам статью о Spring Framework и возможностях аннотирования проектов. Прим. перев.
В начале был EJB 2.1, с его огромным количеством XML-файлов везде где только можно. Не будет особым преувеличением, если сказать, что на одну строку кода для бизнес-логики нужно было написать по крайней мере 10 строк кода от фреймворка и две страницы XML. Локальные и удалённые интерфейсы, ручной JNDI-lookup, многоуровневые try-catch, проверки на RemoteException… enterprise, в-общем. Даже инструменты соответствующие были для автоматической генерации всей этой «кухни».

В предыдущей статье я рассказал об основных аннотациях Spring IoC, однако есть еще несколько интересных вещей, о которых хотелось бы поведать.
Для, тех, кто не в курсе, что такое Spring Framework предлагаю почитать вот эту статью.

Вчера начал разбираться со Spring MVC 3.0.Искал статьи на Хабре, нашел пару штук.Правда они были без аннотаций.
Цель этой статьи написать Hello World c использованием возможностей писать конфиги прямо в коде, благодаря аннотациям.Ну что приступим.

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

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

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

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

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

Добрый вечер.
В этом посте я разберу задачу B «Дубы» с практического тура городской олимпиады школьников Санкт-Петербурга по информатике.
Задача эта на динамическое программирование по подотрезкам и идея решения интересна тем, что удобнее посчитать две динамики вместо одной. Если вас заинтересовало (незнание динамики не освобождает, но будет труднее) — добро пожаловать.

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

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

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

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

Сегодня я расскажу о двух алгоритмах подсчёта количества объектов на изображении. Этот топик предназначен в первую очередь для тех, кто только начинает заниматься обработкой изображений. Для профессионалов ничего нового я не скажу.