opscode chef

Я разобрался с opscode chef. Это система управления однотипными конфигурациями для кучи машин. Законченный кусок конфигурации это «рецепт».

Поставил chef-server на ubuntu 11.04 (кстати они её еще не поддерживают), одну админскую машину и одну виртуалку-клиента. Я использую его для поднятия девелоперского окружения, чтобы наливать машину для разработчика. Получается, что чистая виртуалка на ubuntu готова для разработки проекта за 10 минут. Это удобно.

chef доступен в нескольких версиях, 0.9 и 0.10, а так же через пакеты и через gems. Я ставил версию 0.10 из пакетов и версию 0.9 из них же. 0.10 у меня не заработала. 0.9 встала очень хорошо.

Интернет-магазин

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

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

Админка позволяет настраивать все объекты, в том числе заводить страницы, которые оформляются с помощью разметки MediaWiki.
Бекэнд использует mongodb + MySQL.
Есть система почтовых уведомлений. Я по работе писал генераторы для почтовых уведомлений, и уже потом возникли мысли, как его надо было написать. В этом магазине я переосмыслил почтовые уведомления.

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

Сам магазин устанавливается на Ubuntu и сделан в виде debian пакета, который можно скачать с сайта Народ.Яндекс. Он требует пакет mongodb10gen, который можно установить с сайта разработчика mongo. Я не смог использовать пакет, который идет в поставке с Ubuntu, потому что он не поддерживает UTF-8 без настройки. А разбираться с тонкой настройкой монго я не считаю нужным.

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

Яваскрипт и css сжаты. В качестве вебсервера требуется nginx. Если вы зальете на сервер дамп данных городов и стран из моего прошлого поста, то чудесным образом у вас заработает саджест при вводе страны и города вашего адреса на вашем языке, который передается в Accept-Language и в админке при создании пунктов доставки и самовывоза.

Я выкладываю эту версию без всяких ограничений. Мне стало трудно работать над ним, т.к. я не вижу вот прямо сейчас ни одного магазина, который я мог бы взять, сделать на основе этой разработки и дальше его вести. Я хочу его разрабатывать, получая или удовольствие, или деньги.
Удовольствие медленно заканчивается, потому что в одиночку им заниматься скучно. Есть приватный git репозиторий, в который я готов пустить разработчиков, или перенести его на гитхаб в публичный репозиторий, если от вас увижу какие-то отзывы, и подумаю "Ага, кому-то это нужно".

База городов и стран для mysql

Я сделал урезанную базу с информацией о городах и странах на разных языках.

Структура таблиц такая:

CREATE TABLE `geocoding_geoalternate` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`geoname_id` int(10) unsigned DEFAULT NULL,
`variant` varchar(200) NOT NULL,
`isolanguage` varchar(3) NOT NULL,
`preferred` tinyint(1) NOT NULL DEFAULT '0',
`short` tinyint(1) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`),
KEY `geocoding_geoalternate_variant` (`variant`)
)
CREATE TABLE `geocoding_geomodel` (
`typ` smallint(5) unsigned NOT NULL,
`geonameid` int(10) unsigned NOT NULL,
`name` varchar(100) NOT NULL,
`population` int(10) unsigned NOT NULL DEFAULT '0',
`country_code` varchar(3) NOT NULL,
PRIMARY KEY (`geonameid`),
KEY `geocoding_geomodel_52094d6e` (`name`)
)

Таблица `geocoding_geoalternate` содержит варианты названия пункта на разных языках. Поле preferred означает что это - предпочитаемое родное название. Например, есть Россия и Российская Федерация, второе будет предпочитаемым, зато первое - коротким (short=1).

Она связана с `geocoding_geomodel` через поле geoname_id. В `geocoding_geomodel` содержится информация о населенном пункте . Тип - страна или населенный пункт, количество населения на 2011 год, код страны, например "RU" для России.
База это выжимка с geonames.org. Я сейчас работаю над django приложением которое бы могло ходить в geonames.org и синхронизировать местную базу с их базой, а это - сокращенный вариант (261 MB в распакованном виде), там нет большого количества ненужной для меня информации и нет населенных пунктов с численностью населения меньше 5000 человек.

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

Задача по SQL

Мне была предложена задача:

Игровой сервер. Таблица с двумя полями: id, race. race - строка с расой, их, рас, понятное дело счетное множество. Надо за один запрос, без join, без вложенности, подсчитать долю записей, сделанных людьми, "human".

Скрипт для создания таблицы: mysql, MS SQL Server

CREATE TABLE t(
 ID INT,
        RACE ENUM('ork', 'human', 'troll')
);

Напомню, что такое доля: отношение количества записей которые нас интересуют к общему количеству записей.
Решения: MS SQL (автор Игорь), Oracle (автор Алексей), MySQL

Кусочки кода на питоне

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

Обход прошитого дерева

Элемент бинарного дерева содержит две ссылки: на левое и правое поддерево. Чтобы обойти обычное бинарное дерево требуется алгоритм, использующий стек, т.к. нижележащие деревья не содержат информации о своих предках. Поэтому, чтобы вернуться в узел, в котором возможно ветвление, мы помещаем его в стек. Если же процедура обхода не находит следующего элемента, то мы берем его из стека и повторяем её.
Учитывая то, что многие узлы могут иметь одну из ссылок незанятыми, можно прийти к выводу, что дерево можно представить более эффективно в памяти и сделать обход его более быстрым.
А. Дж. Перлис и Ч. Торнтон предложили использовать эти незанятые ссылки в качестве "нитей", которые связаны с остальными частями дерева. Дерево с такими связями называют "прошитым бинарным деревом".

Прошитое дерево. Из книги Кнут Д. "Искусство программирования."

Чтобы отличать нити от обычных ссылок используются два бита, характеризующие тип связи. Для определенности, если бит RS = 0, то правая связь обычная, если RS = 1, то это связь типа "нить". Аналогично для бита LS. В памяти оба бита естественно представимы в виде одного слова.
Для удобных реализаций алгоритма обхода прошитого дерева вводится ограничение на дерево:

1. корневой элемент имеет правую ссылку на само себя, 
2. построение дерево начинается только влево от корня. 

Корень в таком случае называют "заголовком списка". Для ясности можно делать его значение равным None или Null или любым другим значением, таким которое явно не встречается в элементах дерева, чтобы точно отличать его от остальных элементов дерева и избавить себя от этого искусственного ограничения на построение дерева.

Пример организации прошитого дерева с учетом всех ограничений.

Реализация на Питоне (в виде пакета) включает в себя

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

Скачивайте.

Обход бинарного дерева

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

Разные двоичные деревья.

Типичны задачи обхода этого дерева. Стандартных алгоритмов обхода три.
Прямой алгоритм обхода бинарного дерева

1. Зайти в левое дерево,
2. зайти в корень,
3. зайти в правое дерево.

Центрированный алгоритм обхода дерева

1. Зайти в корень,
2. зайти в левое дерево,
3. зайти в правое.

Обратный алгоритм обхода

1. Зайти в левое дерево,
2. зайти в правое дерево,
3. зайти в корень.

Общее количество вариантов алгоритма обхода вычисляется как размещение без повторений из 3 по 3 (т.е. как перестановка объектов) и оно равно $3! = 6$. Но так как нам не указан приоритет одного из деревьев над другим, то можно считать симметричные относительно выбора левого и правого деревьев алгоритмы обхода одинаковыми.
Реализация на Java бинарного дерева, а так же прямого и центрированного алгоритма обходов, доступна для скачивания. Кстати, мое бинарное дерево использует обобщения (generics) для контейнера данных. А вот алгоритмы обхода реализованы только для Integer.

Осевое преобразование

Картинка по запросу "pivot step"

Осевое преобразование матрицы - очень простое. Пусть дана матрица A
$A = \left( \begin{array}{ccccc} \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & a & \ldots & b & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & c & \ldots & d & \ldots \end{array} \right)$
Операция осевого преобразования c осевым элементом a (англ. pivot step) превращает её в следующую матрицу A₁
$A_1 = \left( \begin{array}{ccccc} \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & 1/a & \ldots & b/a & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & - \frac{c}{a} & \ldots & d - \frac{bc}{a} & \ldots \end{array} \right)$
Строка и столбец матрицы, на которых расположен элемент a называются осевыми строкой и столбцом.
Пошаговое осевое преобразование по главной диагонали используется для получения матрицы идентичности. Это нужно, например, для вычисления обратной матрицы.
В случае больших разреженных матриц имеет смысл задавать матрицу в виде двусвязанных ортогональных списков. Моя реализация алгоритма осевого преобразования на Java работает с матрицами такого вида из предыдущего поста. Мне понравился алгоритм вставки элементов в произвольное место такой матрицы. Он получился красивым, черт возьми. Там ведь по сути идет работа с двумя замкнутыми кольцами из односвязных элементов, в котором мы по определенному правилу меняем связи.
Весь проект для Eclipse (матрица, генератор матриц, алгоритм) можно скачать в ZIP архиве.

Разреженная матрица

Матрица называется разреженной, если в ней относительно много нулей и довольно мало значений. Ниже пример разреженной матрицы.



$\left( \begin{array}{ccccc} 1 & 2 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right)$



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

1. из двух ссылок: на левый и верхний элемент,
2. номера столбца и номера строки
3. хранимого значения (например, высоты участка с соответствующими координатами)

$\begin{array}{cc} LEFT & UP \\ COLUMN & ROW \\ VALUE \end{array} $
Реализация разреженной матрицы на Java. Я еще не тестировал её, т.к. она лишь часть алгоритма для осевого преобразования.
Элементами матрицы являются экземпляры класса MNode - и это всего лишь те самые двусвязанные списки

Основные характеристики дискретной случайной величины

Математическое ожидание ДСВ: $A = \sum\limits_{k} A_k * p_k$
Дисперсия D случайной величины вычисляется как математическое ожидание величины $(A-An)^2$, поэтому
$D = \sum\limits_{k}(k-An)^2p_k$
Среднеквадратическое отклонение $\delta = \sqrt{D}$. Смысл этой величины такой: случайная величина принимает значение не из промежутка $[A-r\delta,A+r\delta]$ с вероятностью не превышающей $1/r^2$. Например, событие $|A-An| > 2\delta$ происходит с вероятностью не больше $1/4$

Приближенное вычисление факториала

В 1730 году Джеймс Стирлинг в своей работе привел формулу приближенного вычисления факториала
$n! \approx \sqrt{2\pi n}*(\frac{n}{e})^n$
Она дает погрешность $\frac{1}{12n}$
Погрешность измерений $\delta x(n)$ это величина характеризующая отклонение приближенного значения от истинного. Т.е. $|I \index n - F\index n| \leq \delta x(n)$

Алгоритм Эвклида

Элегантный алгоритм Эвклида для поиска НОД (наименьшего общего делителя)

Интересное тождество

1+3+...+(2n-1) = n²
То есть, сумма первых n нечетных чисел равна квадрату n.

Последовательность Фибоначчи

Последовательность Фибоначии задается рекурсивным соотношением
Fn = Fn-1 + Fn-2
Формулу Nго члена вывел французский математик Боне.
Fn = [(1 + sqrt(5))/2]^2 + [(1 - sqrt(2))/2]^n / sqrt(5)
Выводится формула благодаря замечательной"золотой пропорции":
t = {1 - sqrt(5)) / 2
и её свойствам:
t² = t + 1
tⁿ = t^n-1 + t ^n-2
Если рассмотреть последовательность {tn}, то можно видеть что коэффициент n-ого члена при иррациональном слагаемом в числителе будет являться n-ым членом последовательности Фибоначчи! Реализация на Питоне этого алгоритма

Простой алгоритм генерации чисел Фибоначчи, реализованный на Питоне. Напомню, числа Фибоначчи, это последовательность, названная в честь математика Леонардо Пизанского, сына Боначчи, который представил её в 2002 году. Первый и второй элементы её заданы и равны 1. Остальные задаются рекурсивным соотношением:
F₁ = 1, F₂ = 1, F_k = F_k-2 + F_k-1

Задачи сортировки

Алгоритм сортировки слиянием
Реализовано на Питоне по книге Шень - программирование. Теоремы и задачи. Сложность алгоритма выражается через O-большое от некоторой функции. Например, если сложность алгоритма - O(n²), значит, что число операций в нем не больше чем C*n², где С - некоторая константа. Сложность же данного алгоритма составляет n*log(n). Для меня еще непонятно, как же выяснить сложность алгоритма. Ну, я понимаю когда сложность выражается степенью n. Сколько вложенных циклов от 1 до n, такова и степень в формуле сложности. Я вижу в формуле только один цикл по n, он как бы состоит из двух вложенных: по t+k и второй по p0, q0. Вместе они по-моему представляют из себя цикл по n. Значит, цикл верхнего уровня вносит в формулу сложности log(n).
http://pastebin.com/1mZ8vuZk
Есть еще реализация алгоритма сортировки пузырьком: http://pastebin.com/E5CvSdzz самая простая, поэтому сложность её O(n²).
Сортировка вставками, или Insert Sort
В основе лежит индекс i. В любой момент времени мы можем сказать, что массив a[1]..a[i] является упорядоченным. Но не более того.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Реализация использует сторожевой элемент, который ставится в начало алгоритма - чтобы исключить одно из условий проверки. Он гарантированно меньше всех элементов. Сложность алгоритма приводится в среднем и в худшем случае: O(n²)
Быстрая сортировка
Метод основан на выборе опорного элемента, который делит массив на две части. После выбора начинаем двигаться с разных концов к опорному элементу, если в левой части встречается элемент который больше опорного элемента, а правая - аналогично, меньше, то меняем их местами. Это называется разделение. Потом рекурсивно запускаем процедуру для обеих частей массива.
Каждое разделение требует n шагов, а глубина рекурсии в среднем равна log(n). Поэтому сложность алгоритма равна n*log(n). Но он неустойчив. Например, выбирая максимальный элемент из каждой части опорным элементом при процедуре разделения, получим O(n²). Но такая ситуация редкая, её вероятность 2/n. Алгоритм естественен, в случае частичной упорядоченности входного массива, показывает более хорошие результаты.

Подпространства линейных пространст

Подмножество W элементов линейного пространства V называется его линейным подпространством, если
1) для a,b из W a+b тоже принадлежит W
2) для ф из W kW тоже принадлежит W
Из определения линейного пространства следует, что W тоже содержит 0, а так же все противоположные векторы.
Для всякого 0 < k < n в пространстве Vn существуют линейные подпространства размерности k. Достаточно взять подпространство, порожденное системой k линейно независимых векторов.
Размерность суммы линейных подпространств равна сумме размерностей линейных подпространств минус размерность пересечения линейных подпространств.

Линейные пространства, изоморфизм

Пусть дано множество V, для элементов которого задана операция сложения a+b, и умножения на число, alpha * a, которые не выводят за пределы этого множества.
Множество V называется линейным пространством, если выполнены условия:
1) a + b = b + a
2) a + (b + c) = (a + b) + c
3) существует 0 из V: a + 0 = a
4) существует -a: a + (-a) = 0
5) alpha (a + b) = alpha*a + alpha*b
6) (alpha + beta) * a = alpha * a + beta * a
7) alpha*(ab) = (alpha*a)*b
8) 1*a = a

Два пространства V и V' называются изоморфными, если каждому элементу a из V единственным образом поставлен в соответствие его образ a' из V' и выполняются следующие равенства:
1) (a+b)' = a' + b' образ суммы равен сумме образов
2) (alpha * a)' = alpha * a'

Если два линейных пространства V и V' изоморфны, то система a1, a2, ... ,ak из V линейно зависима тогда и только тогда, когда линейна зависима система образов a1', a2', ...., ak'
Следствием отсюда является утверждение, что система векторов {a} из пространства V линейно независима, когда линейно независима система её образов из некоторого изоморфного V пространства V'.

Базой линейного пространства называется максимальная линейно независимая система векторов этого пространства.

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

Из трех утверждений выше следует, что при изоморфном переходе база переходит в базу.

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

Scala

Scala крута и интересна. В частности тем, что она функциональна в смысле что каждая функция представлена как значение, а значит может быть передана как аргумент. И тем, что она позволяет реализовывать модель конкурентности малой ценой (как утверждают доки), то есть распараллеливание на несколько процессоров будет дешевым. Ну и байт код, который получается, совместим с JVM и даже с .NET. Т.е. можно писать веб приложения, используя например библиотеки Java. Но нипанятна, насколько хорошо она покажет себя в production, реально работающих проектов на фреймворка lift я не увидел, гиганты типа Google и Yandex используют python или perl для фронта и часто даже для бека. Фреймворк вообще туманный. Красив сам по себе но обвязок с Lucene, Memcached нет. Непонятно, как она себя покажет в вычислениях.. Вообще, все это функциональное программирование выглядит интересным, но будет ли от него плюс в карьере, неясно.

Система векторов линейно выражается через другую систему векторов, если каждый её вектор является линейной комбинацией векторов другой системы.
Две системы n-мерных векторов называются эквивалентными, если каждая из них линейно выражается через другую.
Если в n-мерном векторном пространстве даны две системы векторов размерности r и s, и первая из них линейно независима и линейно выражается через вторую, то число векторов в ней не больше чем во второй, т.е. r<=s.
Две системы векторов называются эквивалентными если каждая из них линейно выражается через другую.
Всякие две эквивалентные между собой линейно независимые системы векторов содержат равное число векторов.
Любые две максимальные линейно независимые системы n-мерных векторов эквивалентны. Возьмем в n-мерном пространстве систему векторов, состоящую из двух любых макимальных линейно независимых систем векторов. Получим, по определению максммальной линейно независимой системы, что каждый вектор второй системы выражается из первой системы. И наоборот. Утверждение доказано.
Поэтому, в n-мерном векторном пространстве все максимальные линейно независимые системы векторов имеют размерность n.
Если в данной линейно зависимой системе векторов есть две максимальные линейно независимые системы векторов, то они содержат равное число векторов.
Если в данной линейно зависимой системе векторов содержатся две максимальные линейно независимые системы векторов, то они содержат равное число векторов.
Рангом системы векторов называется число векторов, входящих в максимальную линейно независимую подсистему векторов этой систему.
Пусть в n-мерном векторном пространстве дано две системы векторов a и b, необязательно линейно независимых, ранги которых k и l соответственно. Если a линейно выражается из b, то k<=l, если эти системы эквивалентны, то k=l.