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

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

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

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

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

Ищем индекс

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

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

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

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

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

Введение

В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

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

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

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

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

Любовь к HTML5 продолжает вдохновлять Поля Айриша. Во-первых, он подарил нам Modernizr, а сейчас он объединился с Divya Manian для создания шаблона HTML5, который использует передовые техники, чтобы Вы могли начать использовать его в своей практике.

Он, в сущности, является хорошей отправной точкой, состоящей из HTML и CSS, предлагающим также и структуру папок, которая работает. Но созданным с учётом многих лет передового опыта профессионалов в разработке клиентской части. Загляните в исходные тексты, чтобы почувствовать, что находится внутри. А если вы думаете, что этого слишком много, просто удалите лишнее.

Написал небольшой мануал по настройке и масштабированию PostgreSQL. Сподвигло меня на это то, что материала по этой теме мало, он устарел или его просто нет.

Скачать можно здесь:
http://github.com/le0pard/postgresql_book/raw/master/postgresql.pdf
Исходники:
http://github.com/le0pard/postgresql_book/

Страница:
http://postgresql.leopard.in.ua/

При разработке баз данных зачастую требуется обеспечить поддержку версионности и хранения истории объектов. Например, у работника может изменяться должность, у должности в свою очередь может меняться оклад — в многомерном моделировании это называется Slowly changing dimensions(далее SCD) — редко изменяющиеся измерения, то есть измерения, не ключевые атрибуты которых имеют тенденцию со временем изменяться. Всего существует 6 основных типов(методов) SCD, которые определяют как история изменений может быть отражена в модели.

В продолжение сегодняшнего топика Версионность и история данных — поделюсь простеньким инструментом, который мы используем.

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

Преимущества:

• Версионирование добавляется к любой таблице за 1 минуту с использованием 1 SQL-команды.
• Можно указать, какие колонки надо сохранять, а какие — нет (что экономит место). При этом запись в лог добавится только в случае, если хотя бы одна из указанных колонок изменилась.
• Можно указать колонку, которая будет трактоваться как «ID автора изменения».
• Можно задать колонки, которые будут логироваться в любом случае, независимо от того, менялись они или нет.

Примеры использования

Предположим, нам нужно логировать изменения вот в такой табличке:

Сегодня утром я зашёл на Google Maps и с радостью увидел там слой «Пробки». Сразу же глаз зацепился за интересное интерфейсное решение для выбора времени, на которое будет показана ситуация с пробками.

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

Самое время вспомнить, как пишутся плагины под jQuery.

Итак, уже давно уважаемый Евгений писал нам о хаках QtCreator, а также указывал в своем блоге документ с подробной инструкцией по созданию плагина. И вот на этих выходных, будучи на даче, оторванным от цивилизации и интернета, я решил попробовать написать свой плагин. Плагин достаточно прост, он выводит список все TODO, FIXME и т. д. комментариев в текущем открытом документе. Ниже я расскажу про то, как написан этот плагин, и вообще про написание плагинов для QtCreator.

Сегодня мне кинули ссылку на прикольный сервис для быстрого генерирования изображений-заглушек. Может пригодиться для html-верстки. На мой взгляд, это удобно тем, кто и так использует заглушки — экономит время при вёрстке, т.к. сами заглушки уже готовы. Можно цвета/размеры подбирать, меняя только числа/буквы в коде, не отвлекаясь на сам файл картинки — и сразу видеть эффект. И сами размеры видеть написанными, если нужно, чтоб к коду не возвращаться для проверки. Или вместо размеров можно текст добавить, чтоб всегда знать, для чего эта заглушка (типа «Бан(н)ер» или там «Лого», или «Фотография»).

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

<img src="http://placehold.it/350x50" />

и получаете:


Update. Благодаря усилиям k0rv1n, найден вариант этого сервиса, только лучше :)
Во-первых, там поддерживается кириллица. Во-вторых, там даны ссылки на исходники для разных языков.
Автор dummyimage.com — тот же Russell Heimlich, что и у placehold.it. У placehold.it есть ещё один автор, но будем считать, что он делал дизайн (дизайн там правда круче, но видимо как раз из-за понтового шрифта Unicode и не выходил).

Примеры (см. под хабракатом) я поменял с placehold.it на dummyimage.com, раз уж он функциональнее…

Часто ли у так бывает, что вы встречаете плохой код и мысленно ругаете автора?
А потом приходите к выводу, что код не так уж и плох, и автора ругали зря… Но осадок-то остался!

В общем, медитировал я давеча перед монитором, и посетил меня

Предисловие

Столкнулся с насущной проблемой, которая автоматически становится задачей:
Как реализовать универсальный механизм перевода контента сайта, который удовлетворял бы потребности как маленьких сайтов, так и больших порталов?


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

Совершенно случайно наткнулся на интересный и ранее не освещенный на Хабра-хабре проект — Vizerra.com. Скачав и установив небольшой клиент появляется возможность попутешествовать по 3D моделям известных мест мира.



Доступен режим свободного перемещения, так и режим интерактивного гида (с русской или английской озвучкой).

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



   Ниже — краткий экскурс в историю метеорологии и то, как работает Росгидромет и другие современные метеорологические службы.

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

Это была бы рядовая и унылая статья про nginx и opcode-кеширование, если бы сервер не был до этого «прооптимизирован» техподдержкой хостера :-)

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

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

И тут на помощь приходит django-admin-tools. С этим приложением минут за 20 можно получить «приборную панель» с произвольной группировкой приложений/моделей, вкладками, любым числом колонок, различными блоками, которые каждый пользователь сможет расставить, как ему удобнее, скрывать и сворачивать по желанию, закладками, настраиваемым меню и удобным способом добавления во все это хозяйство всего, чего только можно придумать.

Вот так, например, сейчас выглядит админка к сайту НадоВместе:


(это только часть, вот скриншот целиком)

Разберемся поподробнее.

Присказка или зачем нужен еще один плагин?

Давным-давно в тридесятом царстве в тридевятом государстве когда web был совсем не 2.0 никому и в голову не приходила мысль о стилизации форм. Сейчас же перед нами очень много решений на чистом CSS, которые кардинально меняют внешний вид элементов. К сожалению, для некоторых элементов это не работает. Особую сложность в этом плане представляет собой input[type=file].

С этим элементом, средствами CSS, мы можем разве что изменить размер шрифта. Все мы любим власть. Ты ведь хочешь полностью контролировать этот неподатливый file? Тут нам на помощь приходит волшебная связка современного интернета — JavaScript + CSS.

В нашем проекте используется jQuery, поэтому первым делом я принялся искать решение с помощью готового плагина, но быстро разочаровался. Найденные плагины либо не соответствовали требованиям нашего заказчика, либо предоставляли дополнительный функционал, который нам совершенно не нужен. Что из этого следует? Правильно – надо написать свой велосипед плагин.

Однажды на просторах Хабра встретил плагин FormNavigate (требующий у пользователя подтверждения на закрытие вкладки или переход по ссылке, когда данные в форме заполнены, а-ля gmail), а однажды потребовалось его даже применить.

Но тот вид в котором плагин был меня не устроил и я позволил себе немного его переписать.

Так, например, мне неудобно было выбирать те ссылки, на которых следует отлавливать подтверждения, а наоборот требовалось указывать ссылки на которые действие плагина не будет распространяться. Тут продвинутые разработчики начнут меня закидывать помидорами, что я не знаю правильную работу селекторов в jQuery. Но это не так, сами можете проверить как работает прошлая версия плагина, например, для: $('a:not([class~="ajax"])') (предложенный автором прошлого топика $('a:[class!="ajax"]') вообще вытворяла чудеса).

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

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

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

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

P. S. Зато как радовались этой штуке наши двоечники в конце семестра…

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

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

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