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

Постановка задачи

Пусть нам задан массив A[i], на который поступают запросы вида:

• посчитать сумму на отрезке [L; R] (позже, мы поймем, что аналогично можно вычислять функции min, max, gcd и др.
• добавить к элементу A[i], delta

Наивная реализация

Мы можем предрасчитать массив частичных сумм, а именно:

 for(int j = 0; j < i; j++) B[j] += A[i];

и тогда на запрос суммы [L; R], мы будем возвращать B[R]-B[L-1] за . Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка , что не есть хорошо.

При сортирование в Python 2 есть как минимум два способа это сортирование «настроить»: это параметры key и cmp. Первый был добавлен только в Python 2.4, а второй был удален в Python 3.0. Эти факты как-бы наводят на мысль что key действительно лучше. Кто с этим не согласен или не уверен — прошу под кат.

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

1. Отображайте нажатия кнопок и кнопкоподобных ссылок

Мой излюбленный совет. Когда стиль кнопки задаётся в CSS, или когда для отображения необычной кнопки используется рисунок (либо как фон, либо как элемент <img />), то кнопка не реагирует на нажатие во всех или в некоторых браузерах (зависит от ситуации). Вот какой простой уловкою вы можете дать знать посетителю сайта, что он и впрямь нажал на нечто нажимаемое:

.mybutton:active {
   position: relative;
   top: 1px;
   left: 1px;
}

Этим кодом кнопка смещается на 1 пиксел направо и на 1 пиксел вниз, когда её нажимают. Испробуйте: выглядит весьма убедительно.

Есть другие, не менее быстрые варианты: придать границе свойство inset, указать свойству text-indent значение 1px, изменить направление градиентного фона (что можно сделать быстро, если для этого не придётся прибегнуть ко графическому редактору, то есть если где-то ещё на сайте используется готовый перевёрнутый градиент), или комбинация нескольких из них.

2. Плавные переходы (CSS3 transitions)

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

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

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

Кому интресно, прошу под кат.

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.

На тему оптимизации MySQL запросов написано очень много, все знают как оптимизировать SELECT, INSERT, что нужно джоинить по ключу и т.д. и т.п.

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

The Little Redis Book — это бесплатная книга про Redis.

Книга была написана Karl Seguin, при поддержке Perry Neal. Karl Seguin является также автором книги The Little MongoDB Book, которую часто рекомендуют для быстрого старта с MongoDB. Первая версия повилась около недели назад.

Сегодня я сделал первую версию перевода этой книги. Исходные тексты доступны в репозитории на GitHub. Там же можно найти и готовый PDF.

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

Я благодарен следующим людям за помощь в переводе оригинального текста и вычитке результата:

• Dmitry Scriptin
• Денис Веселов
• polinom

Я прошу все неточности и опечатки отправлять для коррекции перевода.