...

суббота, 2 августа 2014 г.

Алгоритмы расщепления и числа Ван-дер-Вардена

Привет, Хабр! Решил побаловаться графоманством и поделиться результатом развлечения прошедших выходных (только эти выходные прошли давно и статья писалась гораздо дольше, чем развлечение. Как говорится, делу время — потехе час).

Я расскажу про так называемые алгоритмы расщепления (в частности, про DPLL-алгоритм), про теорему и числа Ван-дер-Вардена, а в заключение статьи мы напишем свой собственный алгоритм расщепления и за полчаса вычислений докажем, что число w(2; 5) равно 178 (первооткрывателям в 1978 году на это потребовалось более 8 дней вычислений).



Алгоритм расщепления




Это достаточно общий алгоритм, который решает следующую задачу: есть некоторое конечное множество S и мы хотим разделить его на два подмножества A и B, обладающими некоторыми свойствами, или же определить, что нужным способом множество S разделить нельзя.

Делается это следующим образом: заводятся и на каждом шаге поддерживаются 3 не пересекающихся подмножества A, B, C, которые полностью покрывают множество S, где C — это множество тех элементов, которые мы еще не распределили между A и B. Изначально C=S, а A и B пусты. На каждой итерации в множестве C произвольно выбирается элемент a, который можно поместить либо в множество A, либо в множество B. На самом деле, мы делаем и то, и другое, а затем рекурсивно обрабатываем оба возможных варианта.


image

В итоге получается дерево расщепления, в листьях которого находятся всевозможные разделения множества S на A и B, а множество C пусто. Теперь нам нужно просто для всех листьев проверить выполнение интересующих нас свойств.


«Позвольте!», — скажете вы, — «чем это лучше очевидного перебора из 2|S| вариантов?». А все дело в отсечениях, которые весьма удобно добавлять к предложенному выше костяку алгоритма!


Список отсечений:



  1. Если частично построенные A и B не подходят — откат

  2. Перемещение элемента из S в A или B может повлечь перемещение других элементов из S в A или B

  3. Грамотный выбор элемента a из S на каждом шаге может существенно сократить размер дерева перебора




С применением отсечений размер дерева сильно сокращается, число листьев заметно уменьшается, иногда до 0 (это означает, что разделить S на A и B нужным образом нельзя). Хотя сложность алгоритма все равно остается экспоненциальной в худшем случае.

Общий алгоритм расщепления и все предложенные отсечения удобно пояснить на примере классического DPLL-алгоритма.


DPLL-алгоритм




Алгоритм Дэвиса–Патнема–Логемана–Лавленда (DPLL) был разработан в 1962 году для определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме, т.е. для решения задачи SAT. Алгоритм оказался настолько эффективным, что спустя уже более 50 лет представляет собой основу для большинства эффективных решателей SAT.

Давайте разберем подробнее, что же делает алгоритм DPLL. Он берет булеву формулу и пытается разделить все переменные, входящие в нее, на два множества A и B, где A — множество всех переменных со значением true, а B — множество всех переменных со значением false.


На каждом шаге некоторым образом выбирается переменная, которой еще не присвоено значение (назовем такие переменные свободными) и присваивается значение true (эта переменная заносится в множество A). После этого решается полученная упрощенная задача. Если она выполнима, то и исходная формула выполнима. Иначе — выбранной переменной присваивается значение false (она заносится в B) и задача решается для новой упрощенной формулы. Если она выполнима, то и исходная формула выполнима. Иначе — увы, исходная формула невыполнима.


После каждого присваивания формула дополнительно упрощается при помощи следующих двух правил:



  1. Распространение переменной (unit propagation). Если в какой-либо дизъюнкте осталась ровно одна переменная, то ей необходимо присвоить такое значение, чтобы дизъюнкта в итоге стала истинной (переместить в A или B в зависимости от того, есть отрицание или нет).

  2. Исключение «чистых» переменных (pure literal elimination). Если какая-либо переменная входит в формулу только с отрицаниями, либо всегда без отрицаний — она называется чистой. Этой переменной можно присвоить такое значение, что все ее вхождения будут иметь значение true, что уменьшит число свободных переменных.




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

Если после упрощения мы получили пустую дизъюнкту (все ее простые конъюнкты ложны) — текущая формула не выполнима и следует откатиться. Если же свободных переменных не осталось — то формула выполнима и работу алгоритма можно закончить. Также закончить работу алгоритма можно в том случае, если дизъюнкт не осталось — неиспользованные свободные переменные можно назначить произвольным образом.


Небольшой C-подобный псевдокод, поясняющий что происходит:



bool DPLL( eq F, set A, set B, set C )
{
while(1)
{
// проверка на допустимость
if (F is empty)
{
// формула допустима!
write A, B, C;
return true;
}
if (F contains an empty clause) return false; // формула не допустима
// упрощения
bool flag = false;
if (unit_propagation(&F, &A, &B, &C)) flag = true;
if (pure_literal_elimination(&F, &A, &B, &C)) flag = true;
if (!flag) break; // упрощений не произошло
}
// ветвление
x = choose_literal(F, С);
if (DPLL(F ∧ (x), A^x, B, C^x)) return true;
if (DPLL(F ∧ (¬x), A, B^x, C^x)) return true;
return false;
}


Символом & показано, что в функции unit_propagation и pure_literal_elimination переменные F, A, B и C передаются по ссылке, т.е. они могут меняться внутри. Если что-нибудь изменилось, данные функции возвращают true. При рекурсивном спуске — напротив, создаются копии объектов. Значок ^ исключает объект из множества, если он есть или добавляет, если его нет.


Рассмотрим следующую формулу и на ее примере посмотрим как работает DPLL-алгоритм:


image



К этой формуле не применимы правила упрощения, поэтому придется ветвить наше дерево. В качестве элемента для ветвления возьмем x1 и, для начала, присвоим ему значение true. Получим следующую цепочку упрощений:
image



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

К сожалению, данная ветвь ведет к невыполнимой формуле, т.е. в этой ветви мы зря старались. Откатываемся и пробуем присвоить переменной x1 значение false. Это приведет к следующей цепочке упрощений:


image



Тройные стрелки показывают, что мы применяем второе правило упрощения. В этой ветви нас ждет успех — найдено целых 2 решения!

Дерево обхода целиком:


image



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

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


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


Теорема и числа Ван дер Вардена




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

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


Пусть множество всех натуральных чисел покрашено в 2 различных цвета. Можно ли утверждать, что найдется сколько угодно длинная арифметическая прогрессия, числа которой покрашены в один и тот же цвет?


imageЗадача кажется очень простой и положительное решение представляется почти очевидным. Однако, попытки доказать это утверждение поначалу ни к чему не приводили. Спустя несколько лет задача наконец поддалась молодому голландскому математику Бартелю Леендерту Ван дер Вардену. Он доказал более общий вариант в немного другой формулировке:


Для любых r и k найдется такое число n(r; k), что при любом раскрашивании множества натуральных чисел S={ 1, 2, ..., n(r; k) } в r различных цветов данное множество S будет содержать арифметическую прогрессию из чисел, покрашенных в один и тот же цвет.


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


Минимальное из чисел n(r; k) обозначим за w(r; k). Числа w(r; k) принято называть числами Ван дер Вардена. Доказательство теоремы Ван дер Вардена не дает точных значений чисел w(r; k), только верхнюю границу. И поверьте, эта верхняя граница просто огромна! Оказалось, что даже для двух цветов оценка на число w(r; k) растет как функция Аккермана! Эта оценка сверху постепенно улучшалась. Последний результат, полученный Тимоти Гауэрсом в 2001 году, гласит:


w(r; k) ≤ 22r22k+9 .


Результат чуть менее страшный, чем первоначальный, но все равно немного пугающий. И все равно эта граница очень далека от точных значений w(r; k).


Отдельная ветвь исследований — определение точных значений чисел w(r; k) для различных r и k. Эта задача весьма ресурсозатратна (это свойственно большинству задач Теории Рамсея). Википедия говорит, что на данный момент точное значение w(r; k) известно только для 7 пар чисел r и k.































r / k3456
2 цвета9351781132
3 цвета27293
4 цвета76



Тривиально получается ответ для w(2; 3):
Доказательство того, что w(2; 3)=9
Другое доказательство с аналогичной идеей и в чуть более развернутом виде приведено здесь.

Пример покраски 8 чисел в 2 цвета так, что среди нет одноцветной арифметической прогрессии длины 3 выглядит так:


1 2 3 4 5 6 7 8


Это означает, что w(2;3)>8. Для 9 же цветов давайте рассмотрим числа 4 и 6. Без ограничения общности, возможны два случая: либо эти два числа покрашены в один цвет, либо в разные.


1) Пусть 4 и 6 покрашены в красный цвет:


1 2 3 4 5 6 7 8 9


Тогда мы обязаны покрасить 5 в синий цвет, поскольку иначе образуется тройка красных чисел 4 5 6. Аналогичные рассуждения для 2 и 8. В итоге получаем синюю тройку 2 5 8:


1 2 3 4 5 6 7 8 9


2) Пусть 4 синяя, а 6 красная:


1 2 3 4 5 6 7 8 9


Тогда, без ограничения общности, 5 можно покрасить в синий цвет. Из этого следует, что 3 следует покрасить в красный цвет, чтобы избежать синих 3 4 5. Далее, 9 следует покрасить в синий, чтобы избежать красных 3 6 9. Промежуточный итог:


1 2 3 4 5 6 7 8 9


Число 1 должно быть красным, чтобы избежать синих 1 5 9. Из этого следует синяя 2, поскольку иначе получим красные 1 2 3. Чтобы избежать красных 2 5 8, красим 8 в красный цвет и в итоге получаем:


1 2 3 4 5 6 7 8 9


Теперь, если мы покрасим 7 в красный цвет, то получим красную тройку 6 7 8. Если же 7 покрасить в синий цвет, то выйдет синяя тройка 5 7 9.




Для чуть больших значений w(r,k) доказательство обычно сводится к следующему: фиксируется длина раскрашиваемой цепочки чисел n, после чего строится булева формула в конъюнктивной нормальной форме для проверки того, что эти n чисел можно раскрасить с учетом ограничений r и k, и проверяется ее выполнимость с помощью SAT-солвера. Если решение нашлось, то число n+1 — нижняя граница для w(r; k), иначе — число n следует считать верхней границей для w(r; k).


Учитывая, что многие SAT-солверы построены на основе DPLL-алгоритма, числа w(r; k) ищутся с использованием алгоритмов расщепления.


Приведем простой способ построения нужной булевой формулы для количества цветов r=2. Заведем n переменных xi, означающих, в какой цвет покрашены соответствующие числа. Значение true будет означать 1й цвет, false — второй. Нам нужно ввести ограничения на то, чтобы любая арифметическая прогрессия содержала оба цвета. Делается это очень просто: дизъюнкция вида (xa1 ∨xa2 ∨…∨xak ) гарантирует присутствие первого цвета, а дизъюнкция вида (¬xa1 ∨¬xa2 ∨…∨¬xak ) — второго. Ну и, собственно, все — для каждой арифметической прогрессии строим 2 формулы и склеиваем все, что получилось, в одну большую КНФ.


Пример формулы для r=2, k=3 и n=9:


(x1∨x2∨x3) ∧ (¬x1∨¬x2∨&notx3) ∧ (x2∨x3∨x4) ∧ (¬x2∨¬x3∨&notx4) ∧ (x3∨x4∨x5) ∧ (¬x3∨¬x4∨&notx5) ∧

(x4∨x5∨x6) ∧ (¬x4∨¬x5∨&notx6) ∧ (x5∨x6∨x7) ∧ (¬x5∨¬x6∨&notx7) ∧ (x6∨x7∨x8) ∧ (¬x6∨¬x7∨&notx8) ∧

(x7∨x8∨x9) ∧ (¬x7∨¬x8∨&notx9) ∧ (x1∨x3∨x5) ∧ (¬x1∨¬x3∨&notx5) ∧ (x2∨x4∨x6) ∧ (¬x2∨¬x4∨&notx6) ∧

(x3∨x5∨x7) ∧ (¬x3∨¬x5∨&notx7) ∧ (x4∨x6∨x8) ∧ (¬x4∨¬x6∨&notx8) ∧ (x5∨x7∨x9) ∧ (¬x5∨¬x7∨&notx9) ∧

(x1∨x4∨x7) ∧ (¬x1∨¬x4∨&notx7) ∧ (x2∨x5∨x8) ∧ (¬x2∨¬x5∨&notx8) ∧ (x3∨x6∨x9) ∧ (¬x3∨¬x6∨&notx9) ∧

(x1∨x5∨x9) ∧ (¬x1∨¬x5∨&notx9)


В предыдушем спойлере доказано, что эта формула невыполнима.


Применяем знания на практике




Давайте теперь напишем свой собственный алгоритм расщепления для поиска чисел w(2; k), не использующий всякой мишуры вроде SAT-солвера. Писать будем на C++ (я использую MS Visual Studio). Основа алгоритма выглядит следующим образом:

#pragma comment(linker,"/STACK:64000000")
#include <iostream>
#include <bitset>
#include <time.h>
#include <memory.h>

using namespace std;

#define N 178
#define K 5

#define BSET bitset< N >

bool dfs( BSET & A, BSET & B )
{
int i = choice( A, B );
if (i<0)
{
for (int a=0; a<N; a++)
if (A[a]) cout << "A";
else if (B[a]) cout << "B";
else cout << "?";
cout << "\n";
return true;
}

A[i] = true;
if (check(A, B))
{
BSET A1 = A, B1 = B;
if (reduce( A1, B1 ))
if (dfs( A1, B1 ))
return true;
}
A[i] = false;

B[i] = true;
if (check( A, B ))
{
BSET A1 = A, B1 = B;
if (reduce( A1, B1 ))
if (dfs( A1, B1 ))
return true;
}
B[i] = false;

return false;
}

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

BSET A, B;
if (!dfs( A, B )) cout << "No counterexamples\n";
cout << "n=" << N << " k=" << K << "\n";
cout << "time=" << clock() << "\n";

return 0;
}




Процедура dfs, собсвенно, и является костяком алгоритма. Константы N и K (длина последовательности и длина арифметической прогрессии соответственно) будут вставляться в код препроцессором в виде чисел, иногда это помогает компилятору лучше оптимизироать код. Множества A и B (элементы последовательности, покрашенные в первый и во второй цвет соответсвенно) задаются битовой маской длины N. Теперь на предложенный костяк следует навесить функции

  1. choice — выбор элемента, по которому мы будем ветвить наше дерево.

  2. check — проверка того, что в последовательности нет арифметической прогрессии длины K.

  3. reduce — покраска дополнительных элементов, для которых цвет можно определить однозначно.


Функция choice — одна из самых интересных:



int cost[N];

int choice( BSET & A, BSET & B )
{
memset( cost, 0, sizeof(cost) );
for (int a=0; a<N; a++)
for (int d=1; a+d*(K-1)<N; d++)
{
int cnt1=0, cnt2=0;
for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++;
for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++;

if (cnt1==0 || cnt2==0)
for (int c=0; c<K; c++)
if (!A[a+c*d] && !B[a+c*d])
cost[a+c*d] += cnt1+cnt2+1;
}

int mx = 0;
for (int a=0; a<N; a++) mx = max( mx, cost[a] );

if (mx > 0)
for (int a=0; a<N; a++)
if (cost[a] == mx)
return a;

return -1;
}




Стратегия выбора элемента, заложенная в choice, следующая: выбирается тот элемент, который входит в наибольшее число потенциальных одноцветных арифметических прогрессий. Но и это еще не все: чем больше в потенциальной прогрессии покрашенных чисел, тем больший вклад она вносит в оценку. Как правило, в алгоритмах расщепления всегда нужно выбирать тот элемент, который делает все как можно хуже и быстрее приводит к конфликту (когда функция check возвращает false). Такая стратегия чаще отсекает ненужные ветви, уменьшая пространство вариантов.

Теперь рассмотрим процедуру check:



bool check( BSET & A, BSET & B )
{
for (int a=0; a<N; a++)
for (int d=1; a+d*(K-1)<N; d++)
{
bool f1=true, f2=true;
for (int c=0; c<K; c++) f1 &= A[a+c*d];
for (int c=0; c<K; c++) f2 &= B[a+c*d];
if (f1 || f2) return false;
}
return true;
}




Данная процедура маленькая, простая и понятная, поэтому нет смысла на ней останавливаться.

Наконец, процедура reduce:



bool reduce( BSET & A, BSET & B )
{
while ( 1 )
{
bool flag = false;
for (int a=0; a<N; a++)
for (int d=1; a+d*(K-1)<N; d++)
{
int cnt1=0, cnt2=0;
for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++;
for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++;
if (cnt1+cnt2<K)
{
if (cnt1 == K-1)
for (int c=0; c<K; c++)
if (!A[a+c*d])
{
B[a+c*d] = true;
flag = true;
}
if (cnt2 == K-1)
for (int c=0; c<K; c++)
if (!B[a+c*d])
{
A[a+c*d] = true;
flag = true;
}
}
}
if (!flag) break;
if (!check( A, B )) return false;
}
return true;
}




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

Результаты




Код тестировался на ноутбуке Core i5 4Gb RAM. При значениях параметров N=177 K=5 за 2 минуты нашелся следующий пример:

BBBABBBBABB?BAAABABBBA?AABAAAABAAAABBBABAAABBBBABBBBABB?BAAABABBBAAAABAAAABAABABBBABAAABA BBABBBBABBABAAABABBBAAAABAAAABAABABBBABAAABABBABBBBABB?BAAABABBBABAABAAAABAABABBBABAAAB?


A и B — цвета. Вопросик означает, что нам не важно, какой именно цвет в данной позиции. Т.е., на самом деле, мы нашли аж 32 примера длины 177, в которых нет одноцветной арифметической прогрессии длины 5.


На параметрах N=178 K=5 код проработал 20,5 минут и показал, что искомых арифметических прогрессий нет. Неплохо для 2178 вариантов в общем случае.


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


Конечно же, код работает и для вычисления w(2; 3) и w(2; 4) (на них все это дело тестировалось изначально).


Что можно сказать насчет случая K=6? Совсем недавно (в 2008 году) было доказано, что w(2; 6)=1132 и на это ушло около 250 дней вычислений на кластере из 200 ядер. Кстати, реализация их алгоритма доказывает, что w(2; 5)=178, менее чем за 3 секунды на одном ядре. Для случая K=7 вопрос остается открытым.


Почитать





  1. Алгоритмы расщепления на Лекториуме (видео, слайды лекции)

  2. Алгоритм Брона-Кербоша поиска всех клик в графе (по сути алгоритм расщепления)

  3. DPLL-алгоритм на Википедии (рус, eng)

  4. Теорема и числа Ван дер Вардена (eng)

  5. А. Я. Хинчин. Три жемчужины теории чисел

  6. Библейский код, теория Рэмзи и существование Бога

  7. Рональд Л. Грэм, Джоуэл X. Спенсер. Теория Рамсея

  8. R. S. Stevens, R. Shantaram. Computer-Generated van der Waerden Partitions (eng, pdf)

  9. Michal Kouril, Jerome L. Paul. The van der Waerden Number W(2,6) Is 1132 (eng, pdf)




P.S. Не по всем ссылкам с глубоко вчитывался, поэтому если какая ссылка на самом деле не по теме — уберу.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


От идеи до Google Play за 30 часов



Приветствую, хабражители!

Сегодня хочу поделиться с вами историей о том, как я делал много всяких правильных вещей, чтобы довести проект по созданию небольшой игрушки от начала и до конца. Такими вещами были: анализ, планирование, дизайн, TDD разработка и тестирование. И все это шло по scrum'у. Да-да, именно в таком составе и порядке. Вообще все это должно быть правилом, идеальным маршрутом ведения проекта, но не все и не всегда это понимают. Ну как минимум я часто ленюсь и бросаюсь в код, забывая про остальное. Не сложно догадаться что из этого выходит. Но не в этот раз, — сказал я себе, и отложив клавиатуру, взял листок и ручку.


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



Мотивы



Основной причиной, которая подстегнула меня к этому проекту, было желание пройти весь путь разработки игр, пусть даже в контексте столь маленького проекта и пусть даже в вакууме. Но в итоге хотелось все же проникнуться каждым аспектом game dev'а. Для себя я решил, что в прошлом уже достаточно наошибался с домашними проектами, и на этот раз все должно быть как у взрослых.
Идея



Тип предстоящего ПО уже был заранее определен — игра (тут как-то и думать не о чем было, подсознательно все было решено уже давно). Целевая платформа первой версии предполагала собой Android, но лишь из-за того что она ближе по духу и не требует дополнительных знаний. Далее я задумался над жанром. Не смотря на всплывающие в моей фантазии шутеры и стратегии реального времени, я, пессимистично оценив свои силы, решил следовать принципу quick win и нацелился на несложный пазл. Среди обилия пазлов первым в памяти возник филлер, поле из ромбиков разных цветов и единственная цель: захватить больше половины всех ячеек. На этом и остановился. Конечно, как и ожидалось, поиск дал схожие результаты, но тем не менее не так и много, и выбор был утвержден.
Разбиение на задачи и их планирование



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

Первым делом на листке бумаги (а точнее пара десятков А4) были созданы предварительные мокапы. Затем их же было решено в полной мере изобразить в фотошопе, таким образом появлялся шанс предотвратить визуальные неточности еще при проектировании. Художник из меня никакой, так что в итоге пришлось искать уроки на просторах интернета (на сколько успешно все получилось судить вам). Зато эскизы было решено строить из финальных версий ресурсов, таким образом я старался убить сразу двух зайцев, и уже по завершении проекта могу сказать, что это решение было удачным.


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


Дух экспериментатора подсказывал, что нужно опробовать что-то новенькое. Так я и познакомился с cocos2d-x. Перечислять преимущества я не буду. Пытливые пользователи уже ушли в гугл, а те, кто знаком с данной платформой, поймут меня в моем выборе. От себя лишь замечу — и функциональные возможности и производительность, и лицензия подходили под мои требования отлично. Теперь, когда был известен фреймворк, стало легче с оценкой трудозатрат.


А код то писать все еще рано, но опираясь на имеющуюся информацию, можно заняться UML'ем. Настоятельно рекомендую обложиться всеми материалами, собранными на данный момент и строить-строить-строить диаграммы классов. Я целый вечер потратил на эту активность. Первый вариант был как и ранее, тяп-ляп, и справился. Но ведь диаграмма классов должна избавить разработчика от проектирования архитектуры на ходу. Поэтому все квадратики ушли в мусор и начался второй виток. Где-то на его середине я повторно допустил ошибку излишнего упрощения и лишь с третьего раза получилось составить весьма приличный документ. Забегая вперед скажу, что он более чем на 80% соответствует реальному коду.


Подрезюмировав и пробежавшись по всей писанине, я с запасом определил 10 часов на работу с ресурсами (музыку кстати брал готовую, уж чего не умеют того не умею), 20 часов чистого программирования, и 10 часов на тестирование и багофиксинг.


Приступаем!



Итак, список задач составлен, переходим к выполнению. На календаре было начало отпуска, а руки, не отвыкшие от клавиатуры на работе, уже чесались и рвались в бой. Но дабы продолжать соблюдать best practices, я засел за фотошоп. И, о чудо, мне не требовалось выдумывать себе работу. У меня все было четко декомпозировано и расписано:

— Всего, 5 экранов.

— 1-й день, экран меню, и выбора режима игры. На них изображены ...,… кнопки,… элементы и тд.

— 2-й день, игровое поле, на котором изображены ...,… и тд.

— 3-й день, экран паузы и завершения игры.

Орудуя scrum'ом, я выделял себе задачи, приоритизировал их, устанавливал лимиты и управлял беклогом, короче был царь и бог. Все вкуче очень неплохо систематизировало мою работу. Для себя я вынес небольшое правило — не брать в разработку более 2-х взаимозаменяемых задач. Застопорился на одной, перехожу к другой, а позже вернусь к первой.

Подготовка ресурсов отобрала три вечера, суммарно 7 часов. Такое опережение графика грело душу.

Переходим к разработке. У нас 20 часов. Как же следить за прогрессом и хоть косвенно понимать успеваю ли? А вот как: 20 часов это округленное число, состоящее из суммы трудозатрат на реализацию каждого элемента диаграммы классов. Теперь, чтобы понять какие части программы готовы, и какой общий прогресс выполнен, был придуман следующий способ:

— реализовываем все-все классы/методы, но внутрь кладем пустышки, нам нужна лишь успешная компиляция;

— для каждого метода набрасываем Unit тесты (3-5 штук для каждого);

— теперь при сборке видно сколько тестов прошло, и это % завершенности проекта, и сколько тестов упало, а это та часть, которая еще не реализована.

Таким образом у нас есть индикатор продвижения проекта.


Отдельного абзаца заслуживает информация про монетизацию. Конечно же за потраченные время и усилия хочется вознаграждения. Поэтому было решено прикрутить немного рекламы. У Google AdMob есть разные виды рекламных сообщений. Я же выбрал вот такую стратегию: во время игры — никакой рекламы, а лишь полностраничный баннер после выхода из игры. Тут так же хочу рассказать про небольшой архитектурный финт (это из 20% кода несоответствующего диаграмме классов). Cocos2dx при завершении игры, не идет нормальным путем финализации работы приложения, он не вызывает onDestroy и т.д., он просто kill'яет текущий поток с приложением. В то же время впихать рекламу в native библиотеку — задача тоже нетривиальная.

Решение вот такое:

1) после того как пользователь закрывает игру (нажав Exit), основное поле игры скрывается и на помощь приходит JNI который дергает отображение новой Activity с рекламой;

2) когда реклама то-ли закрывается пользователем, то-ли сворачивается, то-ли еще какой вариант (Back/Home/Menu кнопки и т.п.), опять таки JNI, но уже в обратную сторону отправляет вызов финализации игры и все закрывается.


Тестирование



Для тестирования я применил две стратегии (опять таки, даже на этом этапе у меня все было расписано и шло по плану):

1) ручное тестирование. Благо жена — QA инженер. Отдельная благодарность за помощь.

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

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


Продакшен



Лучше один раз увидеть нежели семь раз услышать.



Get it on Google Play
Итог



— Бесценный опыт!

— 18 часов разработки + 7 часов подготовки ресурсов + 5 часов тестирования = 30 часов реальной работы, за которую не стыдно.

— Гордость за проект который доведен до конца! И дикое желание поделиться достижением (именно поэтому, не выспавшись, я наяриваю эту статью).

— Надежда на то, что из этого что-то да получится (может пустая, так как опыта мини-коммерческого game dev'а ранее у меня не было).

— Мотивация/советы для читающих.

Что еще предстоит сделать (если проект начнет подавать признаки популярности):

1) Зарелизить игру для iOS и Windows Phone 8, ну и скорее всего десктопную версию для Windows.

2) Прикрутить google-аналитику для анализа поведения игроков.

3) Расширить функционал: уровни сложности, размеры поля/ячеек, общий top (где-то в облаке).


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


Полезные ссылки:

http://ift.tt/XsMs38 — собственно мой «шедевр»

appthwack.com — сервис массового тестирования

http://ift.tt/XsMpnY — сервис тестирования производительности приложения

testobject.com — возможность запуска приложения на множестве устройств с последующим взаимодействием

http://ift.tt/1zHl4fF — межстраничные объявления



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





Спасибо за прочтение!

Как видите, серьезный подход даже к мелким проектам дает свои плоды. И экономия времени, и финальный результат, все это указывает на негативные стороны наплевательского отношения к pre-coding/post-coding этапам, которые must have везде. Уж теперь-то я это усвоил.

P.S. Спасибо reenboog за советы по графике и ресурсам и coder1cv8 за советы по монетизации.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Memory management в ядре Linux. Семинар в Яндексе

Привет! Меня зовут Роман Гущин. В Яндексе я занимаюсь ядром Linux. Некторое время назад я провел для системных администраторов семинар, посвященный общему описанию подсистемы управления памятью в Linux, а также некоторым проблемам, с которыми мы сталкивались, и методам их решения. Большая часть информации описывает «ванильное» ядро Linux (3.10), но некоторая часть специфична для ядра, использующегося в Яндексе. Вполне возможно, семинар окажется интересен не только системным администраторам, но и всем, кто хочет узнать, как в Linux устроена работа с памятью.

Основные темы, затронутые на семинаре:



  • Задачи и компоненты подсистемы управления памятью;

  • Аппаратные возможности платформы x86_64;

  • Как описывается в ядре физическая и виртуальная память;

  • API подсистемы управления памятью;

  • Высвобождение ранее занятой памяти;

  • Инструменты мониторинга;

  • Memory Cgroups;

  • Compaction — дефрагментация физической памяти.




Под катом вы найдете более подробный план доклада с раскрытием основных понятий и принципов.



Задачи подсистемы управления памятью и компоненты, из которых она состоит




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

Основные компоненты:



  • Buddy allocator занимается менеджментом пула свободной памяти.

  • Page replacent («LRU» reclaim model) решает, у когда отобрать память, когда закончилась свободная.

  • PTE management — блок управления таблицами трансляции.

  • Slub kernel allocator — внутренний ядерный аллокатор.

  • и др.




Аппаратные возможности платформы x86_64




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

Как описывается в ядре физическая и виртуальная память?




Физическая память в ядре описывается тремя структурами: ноды (pg_data_t), зоны (struct zone), страницы (struct page). Виртуальная память у каждого процесса своя и описывается при помощи структуры struct mm_struct. Они, в свою очередь, делятся на регионы (struct vm_area_struct).

API подсистемы управления памятью




Ядро взаимодействует с подсистемой memory management при помощи таких функцций функций, как __get_free_page(), kmalloc(), kfree(), vmalloc(). Они отвечают за выделение свободных страниц, больших и малых участков памяти, а также их высвобождение. Существует целое семейство подобных функций, отличающихся небольшими особенностями, например, будет ли занулена область при высвобождении.

Пользовательские программы взаимодействуют с mm-подсистемой при помощи функций mmap(), munmap(), brk(), mlock(), munlock(). Также есть функции posix_fadvice() и madvice(), которые могут давать ядру «cоветы». Но учитывать их в своих эвристиках оно строго говоря не обязано.


Высвобождение ранее занятой памяти (memory reclaim)




Система всегда старается поддерживать некоторый объем свободной памяти (free pool). Таким образом, память выделяется гораздо быстрее, т.к. не приходится высвобождать ее в тот момент, когда она уже действительно нужна.

Те страницы в памяти, которые используются постоянно (системные библиотеки и т.п), называются working set. Вытеснение их из памяти приводит к замедлению работы всей системы. Общая скорость потребления памяти в системе называется memory pressure. Эта величина может очень сильно колебаться в зависимости от того, насколько загружена система.


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


Модель «LRU»




LRU расшифровывается как list recently used. Это абстракция, которая предлагает выкидывать страницы, к которым мы дольше всего не обращались. Реализовать ее в Linux полноценно невозможно, т.к. все что нам известно — было ли когда-либо обращение к той или иной странице. Чтобы как-то отслеживать частоту обращений к страницам используются списки active, inactive и unevictable. В последнем находятся залоченные пользователем страницы, которые не будут выбрасываться из памяти ни при каких условиях.

Существуют четкие правила перемещения между списками inactive и active. Под воздействием memory pressure, страницы из неактивного списка могут быть либо выброшены из памяти, либо перейти в активный. Страницы из активного списка перемещаются в неактивный, если к ним давно не было обращений.


Инструменты мониторинга




Утилита top демонстрирует статистику потребления памяти в системе. Програмка vmtouch — показывает какая часть определенного файла находится в памяти. Исчерпывающую информацию по количеству файловых, активных и неактивных страниц можно найти в /proc/vmstat. Статистика buddy allocator есть в /proc/buddyinfo, а статистика slub allocator, соответственно, в /proc/slabinfo. Часто бывает полезно посмотреть на perf top, где отлично видны все проблемы с фрагментацией.

Memory cgroups




Сигруппы зародились из желания выделить группу из нескольких процессов, объединить их логически и ограничить их суммарное потребление памяти определенным. При этом, если они достигнут своего лимита, память должна высвобождаться именно из выделенного им объема. В этом случае нужно освободить память, принадлежащую именно этой сигруппе (это называется target reclaim). Если в системе просто закончилась память и нужно пополнить free pool — это называется global reclaim. C точки зрения аккаунтинга каждая страница принадлежит только одной сигруппе: той, которая ее первой прочитала.

Compaction




Compaction — это механизм дефрагментации физической памяти. Механизм этот был достаточно долго сломан, примерно с версии 3.3 до версии 3.7. Это проявлялось в том, что на некоторых машинах с мощным фрагментирующим моментом спустя две недели работы все процессоры были заняты исключительно compaction и никакого полезного действия не совершали.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


AppVeyor

Привет, хабр.

Я разрабатываю плагин под Java приложения для запуска кода на .Net. Проект открытый, выложен на GitHub. И в какое-то время я решил, что хорошо бы найти Continious Build & Test такой, чтобы я смог в нем собирать продукт.


После небольших поисков мне попалось на глаза довольно интересное и простое решение.


Disclaimer: я не имею никакого отношения к разработке этого продукта, не знаю автора и т.д. Мне просто понравился этот сервис, и я решил написать пост.



Итак, задача: найти SaaS сервис, который бы решил следующие задачи:



  • Простая интеграция с GitHub

  • Простая настройка системы

  • Возможность запуска произвольного скрипта для тестов (мне требовалось запустить Java приложение, чтобы проверить, что плагин прижился и так далее)

  • Наличие бесплатного тарифного плана (с ограничениями, естественно)




Естественно, сначала я перебрал парочку вариантов. Не могу сказать, что искал досконально, однако одной из идей было найти Team City SaaS решение и воспользоваться им. Это логично, так как сам Team City написан на Java, и он умеет запускать MS Build. Мои поиски не увенчались успехом, однако я нашел ответ на StackOverflow, где автор AppVeyor немного рекламировал свой сервис.

Я попробовал его погонять, и мне понравился интерфейс данного решения:


Скрин




Для работы с ним хватит аккаунта на GitHub. Система поставит хуки на push-операции и будет внимательно следить за репозиторием. В целом, у сервиса есть немало плюсов (с моей точки зрения):


  • Легкая начальная конфигурация. Подключаем аккаунт; говорим, где sln файлы. Всё, билды у Вас уже будут.

  • Несколько режимов тестов: Вы или запускаете стандартные Unit-тесты, или запускаете свой скрипт, что мне и хотелось/

  • Несколько вариантов Deployment'а, в частности Вы можете обновлять beta-версию Вашего сайта (в т.ч. в облаке) автоматически. А главное — это можно легко и быстро настроить. Вы можете даже автоматически выкладывать NuGet пакет после успешного билда.

  • Как видно на картинке, эта система может проставлять версию билда в файлы автоматически, так сказать, из коробки.

  • Конфигурацию можно хранить в самом репозитории с помощью YAML файлов.


Как я сказал выше, мне требовалась Java для запусков тестов. На билд-машинах её не было. Я написал пожелание на сайте, и уже через пару часов на машинах стояла Java. Очень классный сервис в этом отношении.


Естественно, всё это подходит скорее для небольших «домашних» проектов, так как, в отличии от Team City, TFS и подобных систем, здесь у Вас нет полного контроля над процессом сборки, Вы не сможете, например, делать Build какого-нибудь Solution'а после выполнения тестов от предыдущего. Однако же, если есть желание быстро настроить билд, то его легко удовлетворить с помощью этой системы.


И еще раз: я не имею никакого отношения к данному сервису и к его разработке. Цель поста: показать еще один простой способ настроить билд для Вашего репозитория.


Ссылка:


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Минфин РФ готовит законопроект для запрета операций с криптовалютами

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



В настоящий момент на территории России выпуск денежных суррогатов запрещен. Однако Минфин указывает, что определение понятия «денежный суррогат» в законах отсутствует.

«Неподконтрольность национальным органам власти привлекает к „виртуальным валютам“ теневой сектор экономики. Благодаря анонимности владельцев так называемые денежные суррогаты получили популярность при покупке нелегальных товаров, легализации доходов, полученных преступным путем», — поясняет Минфин.


Поэтому министерство предлагает установить запрет на выпуск денежных суррогатов, в том числе в электронном виде. Также предлагается уточнить нормы закона о Центральном банке РФ, распространив запрет не только на выпуск денежных суррогатов, но и на осуществление операций с ними.


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


Конкретные предложения Минфином пока не озвучены. Банк России в январе текущего года предостерег население и юрлица от использования виртуальных валют, рассматривая такие операции как потенциально сомнительные. Вскоре регулятор совместно с Генпрокуратурой наметил действия по предотвращению возможных нарушений имущественных прав граждан и организаций, связанных с использованием криптовалют.


РИА Новости http://ift.tt/1tFW8EK


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Гаджет-переключатель между версиями Java

Приветствую, хабражители!

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



А начнем, пожалуй, с конца и взглянем на готовый результат:

image


Перейду к сути. Разрабатывая для Java платформы, я не ограничиваюсь одной ее версией. Причин тому много: целевая hardware платформа, наличие legacy и т.д… И в связи с этим мне часто приходится подправлять переменные среды JAVA_HOME/JRE_HOME/PATH.


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


Для нетерпеливых, давайте пробовать:

1) В пользовательских переменных среды нужно создать: JAVA_HOME и JRE_HOME

2) В PATH добавить %JAVA_HOME%\bin

3) Скачать и установить гаджет — http://ift.tt/1ksbc6e

4) Но, чтобы все заработало как нужно, мне пришлось сделать еще один весьма нестандартный шаг: в windows/system32 уже лежит java.exe и приоритет этой папки выше того, что указано в PATH. Поэтому пришлось переименовать файл из system32 в "_java.exe"


Все, можно конфигурировать пути к установленным JDK/JRE и пользоваться.


А теперь для тех кому интересны детали.

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


Разработка гаджетов базируется на стандартном наборе web технологий — HTML/CSS/JS. Конечно, можно и C# использовать (к примеру используя вот этот шаблон — http://ift.tt/1scDpO5), но в данной заметке я не буду усложнять простые вещи и выберу native путь.


Базовый каркас гаджета состоит из двух файлов — html страничка с визуальной частью и xml дескриптор.

Полное описание тегов дескриптора можно найти тут http://ift.tt/1ksbb27(v=vs.85).aspx

Дескриптор для моего гаджета (приводить код не буду, так как примечательного там ничего нет), вместе с остальными исходниками доступен тут http://ift.tt/1ksbb29


Теперь перейдем к главной страничке гаджета. Тут есть несколько моментов которые хочу пояснить:

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



document.onreadystatechange = function() {
if(document.readyState == 'complete') {
System.Gadget.settingsUI = 'settings.html';
}
}




— для работы с настройка используется простенькое API:

var val = System.Gadget.Settings.read(key);




— и самое интересное, работа с переменными среды:

var shell = new ActiveXObject('WScript.Shell');
var vars = shell.Environment('User');
vars('JAVA_HOME') = jdk;
vars('JRE_HOME') = jre;




На страничке параметров есть лишь одно место, на котором хотелось бы сделать акцент — сохранение этих самых параметров:

System.Gadget.onSettingsClosing = applySettings; // указываем функцию которую нужно вызывать при закрытии окна параметров

function applySettings(event) {
if (event.closeAction == event.Action.commit) {
// сохраняемся...
}
}




На этом все, реализация готова. Теперь можно приступить к сборке. Гаджет в готовом виде представляет собой zip архив, только с расширением .gadget.

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

del JavaEnvSwitchGadget.gadget
"C:\Program Files\7-Zip\7z.exe" a -tzip -x!.idea -x!.git -x!_stuff -x!build.cmd -r JavaEnvSwitchGadget *.*
move JavaEnvSwitchGadget.zip JavaEnvSwitchGadget.gadget
pause




А теперь немного про отладку (детально можно прочесть тут http://ift.tt/1scDpO8(v=vs.85).aspx)

Для начала плохие новости: по-быстрому отладить с помощью alert-ов не получится, так как в Sidebar нету их имплементации (workaround — использовать MsgBox).

Но давайте сделаем все правильно.

1) Прежде всего настраиваем Internet Explorer, в разделе Advanced убираем галочки возле «Disable script debugging»

2) Настраиваем Visual Studio, в Tools — Options — Just-In-Time ставим галку возле Script.

3) Последнее, чтобы прервать выполнение работы гаджета и позвать на помощь отладчик, нужна всего одна строчка в коде

debugger;




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

Спасибо за прочтение, надеюсь кому-то да пригодится.


Полезные ссылки:

1) http://ift.tt/1ksbb29 — исходники и сборка

2) http://ift.tt/1ksbc6g(v=vs.85).aspx — пошаговое руководство для разработки

3) http://ift.tt/1scDpO8(v=vs.85).aspx — описание метода отладки

4) http://ift.tt/1ksbb27(v=vs.85).aspx — описание xml дескриптора

5) http://ift.tt/1scDpOc — еще одна статья про разработку, но более старая и для Vista

6) http://ift.tt/1ksbb2b — работа с переменными среды из JS


P.S. По вопросу версий, между которыми предлагается переключение, я, пожалуй, ничего говорить не буду. Если кому нужно урезать/расширить список, то делается это быстро.

P.S.2. По аналогии (да что там, copy-paste'ом) можно реализовать переключатель для Python 2/3.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Jimcast — простой подкаст-клиент для ios



Я слушаю подкасты уже 5 лет, 4 из них делаю это с помощью своих ios девайсов, за это время я перепробовал все возможные подкаст-клиенты, но так и не нашел удобного для себя, все они слишком сложные, а мне всегда хотелось чего-то простого и одновременно удобного. Поэтому я взял и реализовал своё виденье правильного подкаст-клиента в приложении Jimcast.



Возможности Jimcast 1.0




+ Плеер для аудио и видео подкастов

+ Воспроизведение подкастов без загрузки (Стриминг)

+ Airplay

+ Шоуноты с внутренним браузером

+ Таймер сна

+ Управление плеером через экран блокировки

+ Загрузка подкастов в бекграунде

+ Автозагрузка новых эпизодов

+ Автоудаление воспроизведенных загрузок

+ Отключение загрузок через 3G для экономии трафика

+ Поиск подкастов в iTunes по названию и автору подкаста

+ Каталог подкастов с выбором страны и типом контента

+ Синхронизация подписок через Dropbox, в дальнейшем планирую добавить синхронизацию эпизодов

+ Экспорт и импорт подписок в OPML (Instacast, Downcast, Pocket Casts)

+ Обновление каналов в бекграунде, не нужно открывать каждый раз приложение для обновления

+ Добавление подкаста по ссылке RSS канала

+ Сортировка подписок по дате добавления, дате последнего эпизода, названию.

+ Шаринг эпизода на почту, sms, twitter, facebook

+ Список всех невоспроизведенных эпизодов

+ Восстановление плеера

+ Воспрозведение подкастов в бекграунде (даже видео)

+ Универсальная версия для iPhone и iPad

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


Технологии




MagicalRecord 3.0 (CoreData) — для работы с данными

AFNetworing (NSURLSession) — для загрузок и сетевых запросов

Masonry — для автолаяутов

AVPlayer (AVFoundation) — для плеера

Dropbox Datastore sdk — для синхронизации подписок

Промокоды




Конечно же я пришел не с пустыми руками, и раздам 50 промокодов первым кто попросит. Если этот абзац зачеркнут, то промокоды закончились.




Jimcast 1.0

Купить в iTunes

Мин. версия ios: 7.0

Универсальная версия для iphone и ipad

Цена: 66 р.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Моделирование процедуры соединения bluetooth устройств и есть ли потребность в моделях такого рода

Здравствуйте! В этом году начинаю учиться в аспирантуре, на данный момент мне поставлена следующая задача: смоделировать взаимодействие узлов самоорганизующейся сети на основе соответствующих технологий.

И здесь возникают следующие вопросы:


  • есть ли смысл в таком моделировании;

  • какой язык моделирования выбрать (на данный момент мне известны наиболее подходящие языки SDL и UML);

  • на каком уровне абстракции строить модель; строить модель работы конкретно каждого протокола или достаточно построить модель определенной процедуры взаимодействия устройств в самоорганизующейся сети;


В виде пробного варианта смоделировал процедуру соединения между устройствами bluetooth на языке UML с использованием диаграммы последовательности. Далее приведены текстовое описание данной процедуры и модель построенная по этому описанию.


Этап 1

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

1.1 Посылаются пакеты inquiry и получаются отклики.

1.2 Если адресат, получивший пакет inquiry, находится в состоянии inquiry scan, тогда он способен принимать такие пакеты

1.3 Получатель переходит в состояние inquiry response и посылает отправителю пакет-отклик.

После того как процедура inquiry завершена, соединение может быть установлено с помощью процедуры paging.

Этап 2

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

2.1 Посылается пакет paging

2.2 Адресат получает этот пакет (находится в состоянии page Scan)

2.3 Получатель посылает отправителю пакет-отклик (находится в состоянии Slave Response)

2.4 Инициатор посылает адресату пакет FHS (находится в состоянии Master Response).

2.5 Получатель посылает отправителю второй пакет-отклик (находится в состоянии Slave Response)

2.6 Получатель и отправитель устанавливают параметры канала заданные инициатором (находятся в состоянии Master Response & Slave Response)

После установления соединения основной узел (master) посылает пакет POLL, чтобы проверить, синхронизовал ли клиент свои часы и настроился ли на коммутацию частот. Клиент при этом может откликнуться любым пакетом.


Исходя из этого описания построена следующая модель в виде диаграммы последовательности.



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


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


20 отличных цитат о конверсии от «гуру»

image

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

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


1 Брайан Айзенберг


Брайан Айзенберг – специалист в сфере поисковой оптимизации и маркетинга, автор New-York Times, один из самых востребованных авторов.



Там, где есть трение, есть возможности. Либо вы что-то сделаете с этим сегодня, либо это сделают ваши конкуренты.







2. Гай Кавасаки

Гай Кавасаки – соучредитель Alltop.co и один из основателей Garage Technology Ventures.



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



3. Ян Лурье


Ян Лурье имеет пятнадцатилетний опыт в SEO. Он является генеральным директором компании Portent Interactive.



Никогда не пишите больше, чем 3-4 строки текста. Просто поверьте мне. Люди не хотят читать Войну и Мир. Они даже не прочитают полностью сегодняшний USA Today. Делайте описания короткими и захватывающими.



4. Майкл Аагард


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



Меня не беспокоят лучшие практики, меня беспокоит конверсия. Вот почему я много тестирую.



5. Тим Эш


Тим Эш является генеральным директором компании SiteTuners, автором книги Оптимизация целевых страниц и председателем Конференции по конверсии.



Удалите изображения и интерактивный контент если они не имеют непосредственного отношения к вашим услугам. Спокойные целевые страницы часто более эффективны.



6. Пип Лая


Пип-Лая предприниматель и Seoшник. Он управляет уникальным агентством Markitekt и является лицом блога ConversionXL.



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



7. Оли Гарднер


Соучредитель и креативный директор Unbounce, и автор многих статей о конверсии, целевых страницах и социальном маркетинге.



Сначала поцелуи, а потом секс. Имейте немного терпения, не просите ничего у посетителя, до момента совершения покупки.



8. Карлос-дель-Рио


Карлос имеет более чем 7-летний опыт проектирования, анализа веб-стратегий и их реализации. Он участвовал в лучших блогах SEOmoz.



Покажите свою целевую страницу кому-то, кто ничего не знает о вашем бизнесе. Если, через 10 секунд он ничего не поймет – вам есть, что исправлять.



9. Брайан Мэсси


Брайан Мэсси – ученый, специальностью которого является научное обоснование конверсии. Его точка зрения формировалась в течение 20 лет, пока он работал программистом, предпринимателем, корпоративным маркетологом и писателем.



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



10. Джон Коррелл


Джон Коррелл является генеральным директором и соучредителем Conversion Voodoo. Он является одним из основных авторов их блога.



Начните тестирование и перестаньте спорить.



11. Крис Говард


Крис Говард является соучредителем и генеральным директором WiderFunnel и является ведущим экспертом в вопросах конверсии.



Мы прислушиваемся к нашей интуиции и проверяем то, что она подсказала нам. Мы анализируем маркетинговые исследования и проверяем их данные. Мы анализируем лучшие практические примеры и ПРОВЕРЯЕМ их. Мы прислушиваемся к мнениям и ПРОВЕРЯЕМ ИХ. Мы слушаем мнение экспертов и ПРОВЕРЯЕМ ЕГО.



12. Энджи Шотмаллер


Энджи Шотмаллер – эксперт в области поисковой оптимизации, конверсии и адаптивности.



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



13. Рэнд Фишкин


Рэнд Фишкин является генеральным директором компании SEOmoz. Он был соавтором The Art of SEO и соучредителем Inbound.org.



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



14. Стив Круг


Стив Круг имеет 20-летний опыт в качестве юзабилити-консультанта для широкого круга клиентов, таких как Apple, Bloomberg.com, Lexus.com и т.д.



Удалите 50% вашего контента. Возьмите половину оставшегося содержания и тоже ее удалите.



15. Роберта Розенберг


Роберта Розенберг является президентом и главным исполнительным директором MGP Direct, Inc. Она имеет более чем 25 летний опыт работы в области маркетинга.



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



16. Авинаш Кошик


Авинаш Кошик является соучредителем Market Motive Inc и Digital Marketing Evangelist for Google.



Никогда не позволяйте своей компании обещать то, что не сможете выполнить.



17. Джен Гордон


Джен Гордон — дизайнер пользовательского интерфейса и писатель для Smashing Magazine. Ее страсть – это посадочные страницы и дизайн мобильных приложений.



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



18. Грегори Циоти


Грегори Циоти является основателем Sparring Mind, а также работает в HelpScout.



Самым лучшим способом повысить конверсию является практическое использование понимания того, почему люди говорят «да».



19. Наоми Найлис


Наоми Найлис является партнером ShiftFWD.



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



20. Брэндон Хесс


Брэндон Хесс является менеджером по входящему маркетингу в ReadyTalk. Он отвечает за рекламу, A/B тестирование, дизайн LP и аналитику.



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



This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Руководство по использованию sbt

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

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

Статья является началом перевода документации с сайта проекта scala-sbt.org и так как это мой первый опыт перевода — буду рад любым замечаниям и правкам.

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



Предисловие




sbt, используя небольшое число концепций, предлагает гибкие решения сборки проектов.

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

Данное руководство, очень рекомендовано к прочтению. Но, если вам некогда читать все, то самую важную информацию вы можете прочитать в разделах “Параметры .sbt сборки”, “Области сборок”, “Дополнительные параметры сборок”. Но, мы не обещаем, что эта хорошая идея поможет вам пропустить все страницы данного руководства.

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

Спасибо, что используете sbt! Желаем вам получить от этого максимум удовольствия!

1. Установка sbt




Для создания sbt проекта вам нужно сделать следующие шаги:


  • Установить sbt и создать скрипт запуска

  • Создать простой проект “Hello world”

  • Создать директорию проекта с исходными файлами внутри

  • Описать параметры сборки

  • Прочитать как запустить sbt

  • Продолжить чтение руководства о параметрах sbt сборки




В конечном счете, установка сводиться к запуску JAR файла и shell скрипта. Но, мы опишем несколько путей для разных платформ, которые могут сделать установку менее утомительной.

Если у вас появились проблемы с запуском sbt, смотрите раздел “Примечания к установке”.
1.a. Установка под Mac



С помощью Macports

$ port install sbt

Homebrew

$ brew install sbt
1.b. Установка под Windows



Просто скачайте инсталятор msi и запустите его.
1.c. Установка под Linux



Официально поддерживаемые дистрибутивы:

RPM пакет

DEB пакет

В дальнейшем я расскажу о том, как можно скачать и настроить sbt вручную. А пока что, самое интересное.


2. Hello, World




Создаем директорию проекта с исходным кодом



Одним из корректных вариантов sbt проекта, может быть директория, содержащая один файл с исходным кодом. Попробуйте создать директорию hello с файлом hw.scala, со следующим содержимым:

object Hi {
def main(args: Array[String]) = println("Hi!")
}




Теперь, в самой директории запустите sbt и наберите команду run в интерактивной консоле. В Linux или OS X это выглядить примерно так:

$ mkdir hello
$ cd hello
$ echo 'object Hi { def main(args: Array[String]) = println("Hi!") }' > hw.scala
$ sbt
...
> run
...
Hi!




При создании проекта, sbt работает в соответствии со следующими правилами:


  • Исходник лежит в корневой директории

  • Исходники лежат в директории src/main/scala или src/main/java

  • Тесты лежат в src/test/scala или src/test/java

  • Файлы ресурсов в src/main/resources или src/test/resources

  • Файлы jar в директории lib




По умолчанию, sbt соберет проект той версией scala, с помощью которой sbt был запущен сам.

Кроме запуска консоли, проект можно сразу запустить на выполнение командой sbt run.
Параметры сборки



Большинство проектов, все же нуждаются в более сложной настройке процесса сборки. В sbt основные параметры сборки хранятся в файле build.sbt в корневой директории проекта.

Например, если для нашего проекта hello создать файл настроек, то выглядеть бы он мог примерно так:

name := "hello"

version := "1.0"

scalaVersion := "2.10.3"




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



Вы можете принудительно установить версию sbt если пропишете в файле hello/project/build.properties указав там следующую строчку:

sbt.version=0.13.5

Теперь, будет использоваться версия sbt 0.13.5. Хранить версию sbt следует именно в файле project/build.properties для избежания возможных колизий.

В качестве заключения




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

P.S. Буду очень признателен, за указанные неточности и замечания перевода. Спасибо!


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Маленький шаг для книгоиздания — огромный скачок для краудсорсингового космоса

(ДИСКЛЕЙМЕР: Данный пост не является агитацией на сбор средств. Цель поста — вдохновить читателей на создание собственных краудсорсинговых проектов)


На Хабре уже писали про проект Павла Шубина (shubinpavel).

Павел планирует издать книгу про историю освоения Венеры.


Проект по сбору средств успешно завершился 31 июля.



Еще за 2 суток до дэдлайна сумма сборов была 500 000 рублей и как в голливудском фильме за последние часы «включился форсаж» и взносы выросли почти в 2 раза.


Спешу поздравить Павла с успехом.


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

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


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


Без сомнений, Павел первопроходец.

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

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


— Но что, если никто не поверит в это?

— Но ведь один уже поверил.


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

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


«Люди будут летать в космос по профсоюзным путевкам» С. Королёв




Павел написал:



Вот проект и завершен. Условная черта, заданная полтора месяца назад, успешно пройдена, а рядом с проектом горит надпись «Успешный».


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


Я всем Вам очень благодарен. Очень и очень сложно выразить словами все мои чувства. Я рад, что серьезная научно-популярная литература востребована в нашей стране. Очень рад. Спасибо всем Вам. Только благодаря Вашей помощи книга увидит свет.



image


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


пятница, 1 августа 2014 г.

Дайджест фото-новостей #8: лучшие материалы конца июля


сегодня в 20:07


Photography News DigestПривет, Хабр. Восьмая подборочка интересных материалов на фото-тематику. Конец июля завалит вас вдохновением и новыми нестандартными идеями, которые можно воплотить уже на этих выходных. Если кто-то хочет получать дайджест на почту – подписаться на рассылку можно у нас в блоге.

Материалы, представленные в дайджесте, на английском языке.


Вдохновение






Лучшие видео




Последнее от DigitalRev




Техника




Съемка




Работа со светом




Разное




Предыдущий дайджест (№7 – начало июля)


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

Войдите, пожалуйста.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Нефункциональные требования к программному обеспечению. Часть 1

Введение




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

В этой статье я расскажу о следующем:



  • какими бывают нефункциональные требования,

  • как определять нефункциональные требования,

  • откуда берутся численные значения для нефункциональных требований.





Нефункциональные требования: какие они бывают




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

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



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




Примеры ограничений: «Разработка должна вестись на платформе вендора X», «При аутентификации пользователя должны использоваться биометрические методы идентификации».

  • Бизнес-правила — политика, руководящие принципы или положения, которые определяют или ограничивают некоторые аспекты бизнеса, в т.ч. правила, определяющие состав и правила выполнения определенных бизнес-процессов. К бизнес-правилам относятся корпоративные политики, правительственные постановления, промышленные стандарты и вычислительные алгоритмы, которые используются при разработке продукта или системы либо непосредственно влияют на разработку.




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

  • Внешние интерфейсы — описание аспектов взаимодействия с другими системами и операционной средой. К ним относятся требования к API продукта или системы, а также требования к API других систем, с которыми осуществляется интеграция.




Примеры внешних интерфейсов: «Обеспечить запись в журнал операционной системы следующих событий: сообщения о запуске и остановке сервиса XX»; «Обеспечить запись в журнал параметров модулей программы: сканера, ядра, антивирусных баз (информация должна заноситься в журнал при запуске программы и при обновлении модулей)»

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



  • Предложения по тестированию разрабатываемого ПО — дополнения к требованиям, указывающие, каким образом то или иное требование должно быть протестировано.



  • Юридические требования — требования к лицензированию, патентной чистоте, etc.


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


Нефункциональные требования: как их определять


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


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


Книга Карла Вигерса "Разработка требований к программному обеспечению" — в разделе «Приложение Г» этой книги находятся примеры документации требований.


Материалы ГОСТ 34 серии .


Нефункциональные требования: работа над определением



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

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



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

  • Системный аналитик — собирает, анализирует и документирует и систематизирует нефункциональные требования.

  • Системный архитектор, ключевые разработчики — участвуют в определении и анализе нефункциональных требований и проверяют их на реализуемость.

  • Группа тестирования — участвует в определении и анализе нефункциональных требований и разрабатывает сценарии тестирования для проверки нефункциональных требований.


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



1. Система получает оповещение о событии, инициирующем рассылку уведомлений.

2. Система осуществляет рассылку оповещений по адресам из списка рассылки X, используя шаблон Y. Для рассылки сообщений используется сервис Z.

3. В случае невозможности завершения рассылки, система предпринимает повторные попытку рассылки.


Требования к времени оповещения о событии, инициирующем рассылку уведомлений: система должна получать оповещение не позднее чем через XX секунд после возникновения события.

Требования к времени отправки уведомлений: все уведомления должны быть отправлены не позднее YY минут после получения оповещения о событии

Требования к повторной отправке рассылки после неудачной попытки: число повторных попыток должно быть равным 10, с интервалом в 10 мин после каждой неудачной попытки отправки.





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



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

Ниже приведены основные характеристики качественных требований.



  • Полнота (отдельного требования и системы требований) — требование должно содержать всю необходимую информацию для его реализации. В него включается вся информация об описываемом параметре, известная на момент описания. Система требований также не должна содержать невыявленных и не определенных требований. Причины неполноты описания следует явно объявлять.

  • Однозначность — требование должно быть внутренне непротиворечиво и все работающие с ним должны понимать его одинаково. Требования следует выражать просто, кратко и точно, используя известные термины. Обычно базовые знания читателей спецификации требований к ПО различаются. Поэтому в ее состав нужно включить раздел с определением понятий прикладной области, используемых при определении требований. Пример, неоднозначного требования. «Период обновления экрана должен быть не менее 20 сек.»

  • Корректность отдельного требования и согласованность (непротиворечивость) системы требований — требование не должно содержать в себе неверной, неточной информации, а отдельные требования в системе требований не должны противоречить друг другу.

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

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

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


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


Атрибуты качества


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


Характеристики качества и модель качества ПО

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


В индустрии ПО есть несколько моделей качества, принятых в качестве стандарта. Эти модели были разработаны в 70-е-80-е годы прошлого века и продолжают совершенствоваться.


Среди них можно выделить следующие:




Также можно назвать еще два стандарта, которые могут послужить источником для определения вашей модели качества:

  • 1061-1998 IEEE Standard for Software Quality Metrics Methodology

  • ISO 8402:1994 Quality management and quality assurance


Характеристики качества с точки зрения влияния на архитектуру системы



Все атрибуты качества с точки зрения архитектуры системы можно разделить на две большие группы: первая группа (runtime) – это атрибуты, относящиеся ко времени работы приложения или системы; вторая группа (design time) определяет ключевые аспекты проектирования приложения или системы. Многие из этих атрибутов взаимозависимы.

Рассмотрим более подробно каждую из этих групп.


Группа runtime



К этой группе относятся следующие атрибуты качества:


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

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

  • Требования к времени хранения данных (например, использование БД в качестве постоянного хранилища данных, продолжительность хранения данных)

  • Масштабируемость — требования к горизонтальному и/или вертикальному масштабированию приложения или системы. Говоря о вертикальной масштабируемости, мы определяем требования к вертикальной архитектуре системы или приложения. К требованиям вертикальной масштабируемости могут относиться, например, возможность переноса приложений на более мощные SMP-системы, поддержка большого объема памяти и файлов. Говоря о горизонтальной масштабируемости, мы определяем требования к горизонтальной архитектуре системы или приложения. К требованиям горизонтальной масштабируемости могут относиться, например, возможность использования технологий кластеризации. Следует особо заметить, что вертикальное масштабирование обычно направлено на повышение производительности системы. Горизонтальное масштабирование, помимо производительности, позволяет повысить отказоустойчивость системы. Более подробно о вертикальном и горизонтальном масштабировании можно прочитать, например, здесь.

  • Требования к удобству использования системы/приложения (с точки зрения пользователя) и требования к удобству и простоте поддержки (Usability)

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

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

    1. конфигурируемость на основе предопределенного набора параметров (predefined configurability), когда необходимый уровень модификации достигается путем изменения значений параметров из предопределенного набора;

    2. конфигурируемость на основе предопределенного набора базовых объектов (framework constrained configurability), когда необходимый уровень модификации достигается путем перекомпоновки предопределенного набора процессов, сущностей и служебных процедур;

    3. конфигурируемость путем реализации новых базовых объектов (basis reimplementation), когда обеспечивается расширение набора процессов и сущностей;

    4. конфигурируемость путем новой реализации системы (system reimplementation), когда система должна устанавливаться и настраиваться с нуля.

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

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


Группа design time



К этой группе относятся следующие атрибуты качества:


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

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

  • Требования к переносимости (Portability) приложения или системы на другие платформы.

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

  • Требования к поддержке системы или приложения (Supportability). Среди этих параметров могут быть названы такие как, напрмер, дешевизна и скорость разработки, прозрачность поведения приложения, простота анализа ошибок и проблем в работе

  • Требования к модульности приложения или системы (Modularity). Обычно такие требования указывают, каким образом система должна быть разделена на модули, или перечисляют список обязательных модулей, которые должны входить в состав системы.

  • Требования к возможности тестирования (Testability) приложения или системы определяют объем требований к автоматическому и ручному тестированию, наличие необходимого инструментария

  • Требования к возможности и простоте локализации (Localizability) приложения или системы определяют возможности и специфические архитектурные требования, накладываемые процессом локализации. Эти требования содержат также перечень языков, на которые предполагается выполнять локализацию приложения или системы


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


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.