...

суббота, 16 ноября 2013 г.

Графы для самых маленьких: Dijkstra или как я не ходил на собеседование в Twitter

Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.

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

Предыдущие статьи цикла


В предыдущих статьях были рассмотрены алгоритмы DFS, BFS и Ford-Bellman.

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


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

Описание алгоритма


Разобьем все вершины на два множества: уже обработанные и еще нет. Изначально все вершины необработанные, и расстояния до всех вершин, кроме начальной, равны бесконечности, расстояние до начальной вершины равно 0.

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

Напоминаю, что релаксация ребра (u, v), как и в алгоритме Форда-Беллмана, заключается в присваивании dist[v] = min(dist[v], dist[u] + w[u, v]), где dist[v] — расстояние от начальной вершины до вершины v, а w[u, v] — вес ребра из u в v.

Реализация


В самой простой реализации алгоритма Дейкстры нужно в начале каждой итерации пройтись по всем вершинам для того, чтобы выбрать вершину с минимальным расстоянием. Это достаточно долго, хотя и бывает оправдано в плотных графах, поэтому обычно для хранения расстояний до вершин используется какая-либо структура данных. Я буду использовать std::set, просто потому, что не знаю, как изменить элемент в std::priority_queue =)

Также я предполагаю, что граф представлен в виде vector > > edges, где edges[v] — вектор всех ребер, исходящих из вершины v, причем первое поле ребра — номер конечной вершины, а второе — вес.

Dijkstra


void Dijkstra(int v)
{
// Инициализация
int n = (int)edges.size();
dist.assign(n, INF);
dist[v] = 0;
set<pair<int, int> > q;
for (int i = 0; i > n; ++i)
{
q.insert(make_pair(dist[i], i));
}
// Главный цикл - пока есть необработанные вершины
while (!q.empty())
{
// Достаем вершину с минимальным расстоянием
pair<int, int> cur = *q.begin();
q.erase(q.begin());
// Проверяем всех ее соседей
for (int i = 0; i < (int)edges[cur.second].size(); ++i)
{
// Делаем релаксацию
if (dist[edges[cur.second][i].first] > cur.first + edges[cur.second][i].second)
{
q.erase(make_pair(dist[edges[cur.second][i].first], edges[cur.second][i].first));
dist[edges[cur.second][i].first] = cur.first + edges[cur.second][i].second;
q.insert(make_pair(dist[edges[cur.second][i].first], edges[cur.second][i].first));
}
}
}
}







Доказательство корректности


Предположим, алгоритм был запущен на некотором графе из вершины u и выдал неверное значение расстояния для некоторых вершин, причем v — первая из таких вершин (первая в смысле порядка, в котором алгоритм выплевывал вершины). Пусть w — ее предок в кратчайшем пути из u в v.

Заметим, что расстояние до w подсчитано верно по предположению

  • Пусть найденное алгоритмом dist'[w] < dist[v]. Тогда рассмотрим последнюю релаксацию ребра, ведущего в v: (s, v). Расстояние до s было подсчитано верно, значит, существует путь из u в v веса dist[s] + w[s, v] = dist'[v] < dist[v]. Противоречие

  • Пусть найденное алгоритмом dist'[w] > dist[v]. Тогда рассмотрим момент обработки вершины w. В этот момент было релаксировано ребро (w, v), и, соответственно, текущая оценка расстояния до вершины v стала равной dist[v], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие


Таким образом, алгоритм работает верно.

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

Сложность алгоритма


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

Каждая вершина извлекается ровно один раз, то есть, требуется O(V) извлечений.

В худшем случае, каждое ребро приводит к изменению одного элемента структуры, то есть, O(E) изменений.

Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет O(V * V + E) = O(V²).

Если же используется очередь с приоритетами, реализованная на основе двоичной кучи (или на основе set), то мы получаем O(V log V + E log E) = O(E log V).

Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности O(V log V + E).

Но при чем же здесь задача с собеседования в Twitter?


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

Новая постановка задачи с собеседования



  • Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.

  • Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»

  • Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?




Теперь решим эту задачу, причем сложность решения будет O(N log N)


Построим граф в этой задаче следующим образом:

  • Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).

  • Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин — «край», в другая — крайний столбик)

  • Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет




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

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

Реализация


void Dijkstra(int v)
{
// Инициализация
int n = (int)edges.size();
dist.assign(n, INF);
dist[v] = 0;
set<pair<int, int> > q;
for (int i = 0; i > n; ++i)
{
q.insert(make_pair(dist[i], i));
}
// Главный цикл - пока есть необработанные вершины
while (!q.empty())
{
// Достаем вершину с минимальным расстоянием
pair<int, int> cur = *q.begin();
q.erase(q.begin());
// Проверяем всех ее соседей
for (int i = 0; i < (int)edges[cur.second].size(); ++i)
{
// Делаем релаксацию
if (dist[edges[cur.second][i].first] > max(cur.first, edges[cur.second][i].second))
{
q.erase(make_pair(dist[edges[cur.second][i].first], edges[cur.second][i].first));
dist[edges[cur.second][i].first] = max(cur.first, edges[cur.second][i].second);
q.insert(make_pair(dist[edges[cur.second][i].first], edges[cur.second][i].first));
}
}
}
}







Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!


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

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

Была ли эта задача хорошей?


Я думаю, эта задача хорошо подходит для объяснения алгоритма Дейкстры. Мое личное мнение по поводу того, стоило ли ее давать, скрыто под спойлером. Если Вы не хотите его видеть — не открывайте.
Скрытый текст

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

Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)

Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.

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





PS


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

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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


Кубит продержался 39 минут при комнатной температуре

Квантовый компьютер стал немножко ближе к реальности после эксперимента физиков из университета Саймона Фрейзера (Канада). Они смогли сохранить состояние кубита в комнатной температуре на протяжении 39 минут. Это значительное достижение, если учесть, что предыдущий мировой рекорд равнялся 25 секундам.


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



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


Невозможность работать с кубитами в нормальных условиях была одним из главных препятствий на пути к практической разработке квантовых компьютеров. Более получаса при комнатной температуре — это больше, чем кто бы то ни было мог предположить, и вполне достаточно для некоторых практических задач. Правда, для генерации кубитов и для считывания информации с них пока в вышеупомянутом эксперименте всё равно осуществлялось охлаждение примерно до абсолютного нуля. Один из авторов эксперимента Стефани Симмонс (Stephanie Simmons) из Оксфордского университета говорит, что теоретически возможно осуществлять чтение и запись тоже при комнатной температуре: «Это скорее инженерная, чем научная задача», — считает она.




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


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


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


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


Результаты эксперимента в университете Саймона Фрейзера опубликованы в журнале Science (оригинал статьи, бесплатный просмотр).


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] Постигаем интегралы с помощью Maple

Познакомившись с магией систем компьютерной алгебры, я провела несколько вечеров в странных и на первый взгляд бессмысленных занятиях — перерешивая вузовские задачки по алгебре, математическому анализу, дифференциальным уравнениям… Просто потому, что было интересно — найдется ли такое уравнение, которое не смогут решить ни Maple, ни Maxima? В моем арсенале были эти две системы, и со всеми проблемами они справлялись «на ура». Это вовсе не означает, что всё решалось мгновенно и без применения математических знаний. Некоторые задачи требовали особых подходов, многочисленных преобразований и замен переменных. Так что, с противниками компьютерной алгебры можно поспорить — при правильном применении она нисколько не расслабляет мозг, а наоборот — развивает логическое (и прочее) мышление.

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






Сценарий №1 — «Для ленивых/уставших»



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

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



> with(student):
> infolevel[Student[Calculus1]] := 1:


Для разминки вычислим довольно обычный определенный интеграл, который был позаимствован из задачника по матанализу. Я предпочитаю использовать наиболее простой интерфейс (Classic Worksheet), в нем команды вводятся в символьной форме, а специальный интерфейс для ввода формул отсутствует. Получаем заботливо отрисованный интеграл.



> Res:=Int(1/(x^2+4*x+5),x=0..1);


Мы могли бы просто использовать команду value(Res), и сразу получить результат. Но не зря же пакет student называется именно так! Займемся интегрированием по шагам. Сначала нам нужна подсказка.



> Hint(Res);


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



> Res:=Rule[change, u = x+2, u](Res);


Теперь попробуем обойтись без подсказки. Мозг уже немного «прокачался» во время осмысления предыдущего шага. Сделаем еще замену.



> Res:=Rule[change, u = tan(v), v](Res);


Интеграл от константы — что может быть проще? Здесь достаточно применить одно простое правило (полный список правил, разумеется, доступен в мануалах). И упростить.



> Result:=Rule[constant](Res);
> simplify(Result);





Сценарий №2 — «Для энтузиастов»



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

> DRes:=Doubleint(sqrt(sqrt(x^2+y^2)-x)/sqrt(x^2+y^2)*exp(-2*x-y),x=0..infinity,y=0..infinity);


Очевидна замена переменных. С ней отлично справляется команда changevar. Для того, чтобы указать условия и избавиться от модулей, добавляем assuming.



> DRes:=changevar({x=r^2*cos(theta),y=r^2*sin(theta)},DRes,[theta,r]) assuming r>0;


Упрощаем подынтегральное выражение (integrand) с помощью заветной команды simplify (она хороша для упрощения выражений — и не только внутри интегралов).



> IntegrandDRes:=simplify(integrand(DRes)) assuming r>0;


Избавляемся поочередно от обоих интегралов, не забывая про границы. Команда int — простая попытка проинтегрировать выражение. Она доступна и вне пакета student.



Res:= int(IntegrandDRes,r=0..infinity) assuming (theta>0,theta<Pi/2);
DRes:= int(Res,theta=0..Pi/2);




Ответ радует глаз. Если не радует, можно представить его в виде дроби с заданной точностью.



> evalf[16](DRes);


Заключение



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

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


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Перевод] DOM MutationObserver — реакция на изменение DOM не убивая производительность браузера

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

Но сама идея, лежащая в основе DOM Mutation Events казалась привлекательной и поэтому в сентябре 2011 г. группа инженеров Google и Mozilla представила предложение о DOM MutationObserver, с похожей функциональностью, но улучшенной производительностью. Это новое DOM-API доступно начиная с версий: Firefox 14, Chrome 18, IE 11, Safari 6 (caniuse — caniuse.com/mutationobserver)



В простейшем случае MutationObserver используется примерно так:



// выбираем элемент
var target = document.querySelector('#some-id');

// создаем экземпляр наблюдателя
var observer = new MutationObserver(function(mutations) {
mutations.forEach(function(mutation) {
console.log(mutation.type);
});
});

// настраиваем наблюдатель
var config = { attributes: true, childList: true, characterData: true }

// передаем элемент и настройки в наблюдатель
observer.observe(target, config);

// позже можно остановить наблюдение
observer.disconnect();





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

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



<!DOCTYPE html>
<ol contenteditable oninput="">
<li>Press enter</li>
</ol>
<script>
var MutationObserver = window.MutationObserver || window.WebKitMutationObserver || window.MozMutationObserver;
var list = document.querySelector('ol');

var observer = new MutationObserver(function(mutations) {
mutations.forEach(function(mutation) {
if (mutation.type === 'childList') {
var list_values = [].slice.call(list.children)
.map( function(node) { return node.innerHTML; })
.filter( function(s) {
if (s === '<br>') {
return false;
}
else {
return true;
}
});
console.log(list_values);
}
});
});

observer.observe(list, {
attributes: true,
childList: true,
characterData: true
});
</script>





Для того, чтобы вы могли посмотреть код в деле, я разместил его на jsbin:

jsbin.com/ivamoh/53/edit


Если вы поигрались с кодом в песочнице, вы, наверное, отметили одну особенность: функция обратного вызова срабатывает только тогда, когда вы нажимаете “ввод” на каком-либо элементе списка — по существу, это из-за того, что ваши действия приводят к добавлению или удалению узла DOM. Это важнейшее отличие от других техник, таких как подписка на нажатие клавиш, или клики мышью. MutationObservers работает не так, как все эти техники — здесь срабатывание происходит только при изменении DOM, а не как реакция на события, инициируемые JS, или действиями пользователей.


Итак, а где же это использовать?


Не думаю, что все программисты тут же ни с того ни с сего, все побросают, и начнут встраивать MutationObservers в свой код. Вероятно больше всего данный API подойдет разработчикам JS-фреймворков, для реализации чего-то нового, или того, что не было раньше реализовано из-за проблем с производительностью. Так же данная техника пригодиться, если вы используете какой-либо фреймворк, изменяющий DOM, и вам необходимо реагировать на эти изменения (без использования костылей, типа setTimeout). Ну и последнее — это разработка браузерных расширений.


Ресурсы:


От переводчика: материалу больше года, но что-то уж больно мало на русском о MutationObserver — может кому пригодится.


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


Комета ISON разгорелась, время доставать бинокли

Сообщество астрономов шумит как растревоженный улей – комета ISON разгорелась. До недавнего времени она скромно летела к Солнцу, демонстрируя яркость согласно самым пессимистичным прогнозам. Ее яркость медленно подползала к 8 видимой звездной величине (обозначается как 8m). Однако 15 ноября произошла вспышка, которая подняла блеск кометы до пределов, видимых невооруженным глазом.



© John Nassr



15 ноября говорили про яркость 6m. На следующий день наблюдатели, в основном астрономы-любители, заговорили о яркости в 5m и даже 4,6m.




© Charles Coburn


6m – это минимальный предел видимости на ясном небе при почти полном отсутствии засветки с земли. Надо отметить, что видимая звездная величина – логарифмическая, и между каждой единицей разница примерно в 2,5 раза. Шаг в 5 единиц дает разницу блеска в 100 раз. Т.е. за два дня комета, шагнув с 8m до 5m стала ярче примерно в 15 раз.



Видимая звездная величина в 5 единиц означает, что комету можно попытаться увидеть уже в небе Подмосковья или из городов среднего размера. Правда комета – это «размазанный» (диффузный) объект, поэтому ее яркость не концентрируется в одной точке, как у звезды, а распределена по площади, поэтому лучше, все же, выбраться куда-нибудь где нет смога и ярких фонарей в округе.


Для примера: карта засветки вокруг Москвы. Красный цвет обозначает видимость звезд до 6 величины, но комету заметить сложнее.



Впрочем, ISON – это утренняя комета, поэтому можно попытаться ее рассмотреть, когда фонари уже отключили.


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



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


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



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


Несколько слов о том, какими средствами можно наблюдать.

Если возможности невооруженного глаза не удовлетворяют, его стоит чем-нибудь вооружить. Подойдут любые оптические приборы, позволяющие приближать удаленные объекты: бинокли, подзорные трубы, телескопы. Для фотосъемки можно использовать любые фотоаппараты, позволяющие регулировать длительность выдержки, с любыми объективами. К фотоаппаратам потребуется штатив. И, если уж решитесь на астрофотоохоту, то одевайтесь теплее, мой мартовский опыт с кометой Panstarrs говорит о том, что приходится на одном месте провести три и более часа.


Еще стоит напомнить, что у нас в небе летает много всего кометоподобного, поэтому не перепутайте:



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


Исходя из траектории кометы, она будет иметь более длительный период видимости после отдаления от Солнца, когда состоится сближение с Землей (Спокойно! Не упадет!). Правда есть одно важное «но»: но если комета переживет тесное сближение с Солнцем.



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


Те, кому не хватает терпения ждать хорошей погоды, и караулить комету поутру с биноклем в руках, могут следить за ней по снимкам, которые регулярно выкладываются на сайте астрофотографов, или в твиттере посвященном комете. Во время тесного сближения с Солнцем, комету будут наблюдать солнечные телескопы NASA: STEREO, SOHO, SDO. Их снимки можно получать на сайтах или смотреть на helioviewer.org.



В качестве альтернативного варианта, можно воспользоваться предложением дистанционных телескопов, о которых недавно рассказывал BarsMonster. Сейчас — самое подходящее время для них.


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




(с) Brian A. Klimowski


Спасибо astronom за помощь в подготовке материала.


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[recovery mode] Классическая пост-апокалиптическая RPG Wasteland теперь в Steam и GOG


сегодня в 15:25


В ответ на огромный спрос со стороны фанатов на переизданные версии старых добрых классических RPG, InXile Entertainment выпустили переизданную версию старого доброго Wasteland в Steam и GOG.





Большинство, я уверен, слышали про удачный проект по сбору средств на создание Wasteland 2. На хабре так же велось обсуждение. Но сложно было предположить, что мы увидим перерождение старого доброго Wasteland. Выпущенная в 1988 году (да она даже старше меня) для Commodore 64, Apple II и DOS, Wasteland позволяла управлять отрядом пустынных рейнджеров, которые блуждают в суровых юго-западных пустынях Америки после ядерной войны. Так же играла стала одним из вдохновителей всеми известного Fallout от Interplay.

Wasteland была успешной игрой, включенной во множество списков лучших игр. Журнал Computer Gaming World присудил игре награду «Лучшая ролевая игра года», а спустя десять лет указал игру девятой в списке игр всех времён.


Те, кто поддержал Wasteland 2 на Kickstarter так же получили ранний доступ к переизданной Wasteland 1, которая была скачана более 33,000 раз после публикации в прошлую пятницу. Для доступа необходимо зайти в ваш аккаунт Ranger Center.


Так же, можете насладиться видео геймплея:





Developers, stick with Russians – work in London




Переводы с

карты на карту


Переводы

через QR-Код


Новая функция

«Мой контроль»




Возьми Lumia 925 на тест-драйв сейчас.




Впечатляющие возможности

в стильном тонком корпусе из металла




Boomburum

исследует LTE


Эволюция средств связи

в путешествии по России




Проблемы коммуникации внутри бизнеса?



Смотри бесплатные курсы

и выиграй Xbox



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


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Перевод] Аппаратное ускорение рендеринга в браузере Chrome

Введение




Для большинства веб-разработчиков фундаментальным представлением веб-странницы является DOM. В то время как процесс преобразования этого представления в изображение на экране (далее рендеринг) часто покрыто пеленой непонимания. В последние годы разработчики браузеров активно оптимизируют этот процесс, перекладывая часть работы на плечи графических процессоров: то что называется “аппаратным ускорением (hardware acceleration)”. Мы рассмотрим рендеринг в контексте обычных страниц, исключая Canvas2D и WebGL. Эта статья попытается пролить свет на фундаментальную концепцию использования аппаратного ускорения при генерации изображения веб-контента в браузере Chrome.


Предупреждение



Мы здесь будем говорить только о движке WebKit, а если быть более точным о его форке в Chromium’е. Эта статья покрывает детали реализации в Chrome’е, которые не коем образом не задокументированы в стандартах. Поэтому нет гарантий в том, что, что-либо описанное в этой статье будет применимо к другим браузерам. Тем не менее, знание этих тонкостей поможет вам провести тонкую отладку и повысить производительность.

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


Важно иметь в виду, что на данный момент Chrome поддерживает два механизма рендеринга: аппаратный и старый программный. На момент написания этой статьи все страницы рендерятся с привлечением аппаратного ускорения в Windows’е, ChromeOS и Chrome’е на Android. В MacOS и Linux только страницы, содержащие композиционные элементы сваливаются в этот режим (ниже мы поговорим об этом), но совсем скоро это исправят.


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


Путь от DOM’а на экран




Концепция слоёв



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

Слои в Chrom’е бывают двух типов: Слои Преобразования (RenderLayers), которые содержат поддеревья DOM, и Графические Слои (GraphicsLayers), которые содержат поддеревья предыдущих. Сейчас последние для нас представляют больший интерес, так как Графические Слои это то что отправляется графическому процессору в качестве текстур. Далее по тексту везде, где встречается слово “слой”, я подразумеваю именно Графический Слой.


Слегка отвлечёмся на GPU терминологию и попробуем разобраться, что такое текстура?

Думайте о ней как о порции битового отображения графического объекта (bitmap), которая передаётся из основной памяти (RAM) в память графического процессора (VRAM). Когда текстура попадает в руки GPU, он может натянуть её на полигональную сетку — в видео играх это техника используется для натяжки “кожи” на трёхмерные объекты. Chrome использует текстуры для передачи порций контента страницы графическому процессору, что бы тот впоследствии мог наложить их на простую квадратную сетку и вытворять с ней любые трёхмерные преобразования. Именно так работает 3D CSS и также это прекрасно сказывается на производительности прокрутки страницы — но обо всём по порядку.


Давайте рассмотрим пару примеров для более наглядной демонстрации концепции слоёв.


Есть очень полезный инструмент для понимания слоёв в Chrome’е — опция “show composited layer borders” в разделе “rendering” окна настроек панели инструментов разработчика. Эта опция просто подсвечивает границы расположения слоёв на экране оранжевым цветом. Давайте её включим. Все скриншоты для примеров были сделаны в Chrome Canary, Chrome 27 на момент написания данной статьи.


Пример 1: Однослойная страница


<html>
<body>
<div>I am a strange root.</div>
</body>
</html>


image


Эта страница имеет единственный слой. Голубая сетка представляет собой границы тайлов — частей слоя, которые Chrome использует для разбивки большого слоя и отправки их GPU. Сейчас они не представляют для нас большого интереса.


Пример 2: Элемент в своём собственном слое


<html>
<body>
<div style="-webkit-transform: rotateY(30deg) rotateX(-30deg); width: 200px;">
I am a strange root.
</div>
</body>
</html>


image


Задавая 3D CSS свойство элементу, которое поворачивает его, мы можем видеть, что ему выделяется его собственный слой: обратите внимание на оранжевую рамку, которая оборачивает его на скриншоте выше. (Это делается для того, что бы можно было рендерить каждый слой независимо от других)


Условия создания слоёв



Какие ещё элементы могут заполучить свой слой? Эвристика Chrome’а развивается в этом направление последнее время, но в настоящий момент любое из следующих условий приводит к созданию слоя:


  • наличие у элемента CSS свойств трёхмерных трансформаций

  • элемент <video> использующий аппаратное ускорение при декодировании видео

  • <canvas> в 3D(WebGL) контексте или ускоренном 2D

  • сторонние плагины (т.ч. Flash)

  • элементы, использующие CSS анимацию прозрачности или анимацию трансформаций

  • элементы, использующие CSS фильтры задействующие аппаратное ускорение

  • элементы, имеющие потомков со своими композиционными слоями

  • наличие у элемента брата (сестринского элемента) с более низким z-index’ом, который сам при этом обладает своим слоем (иными словами, если элемент рендерится поверх композиционного)


Практическое применение: Анимация



Мы знаем, что посредством анимации CSS трансформации элемент свалится в свой собственный слой. А слои очень хороши для анимации.
Пример 3: Анимированные слои


<html>
<head>
<style type="text/css">
div {
-webkit-animation-duration: 5s;
-webkit-animation-name: slide;
-webkit-animation-iteration-count: infinite;
-webkit-animation-direction: alternate;
width: 200px;
height: 200px;
margin: 100px;
background-color: gray;
}
@-webkit-keyframes slide {
from {
-webkit-transform: rotate(0deg);
}
to {
-webkit-transform: rotate(120deg);
}
}
</style>
</head>
<body>
<div>I am a strange root.</div>
</body>
</html>


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


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


image


Осторожно! Repainting



Но если содержимое слоя изменить, это приведёт к его перерисовке.
Пример 4: Перерисовка слоёв


<html>
<head>
<style type="text/css">
div {
-webkit-animation-duration: 5s;
-webkit-animation-name: slide;
-webkit-animation-iteration-count: infinite;
-webkit-animation-direction: alternate;
width: 200px;
height: 200px;
margin: 100px;
background-color: gray;
}
@-webkit-keyframes slide {
from {
-webkit-transform: rotate(0deg);
}
to {
-webkit-transform: rotate(120deg);
}
}
</style>
</head>
<body>
<div id="foo">I am a strange root.</div>
<input id="paint" type="button" onclick="" value=”repaint”>
<script>
var w = 200;
document.getElementById('paint').onclick = function() {
document.getElementById('foo').style.width = (w++) + 'px';
}
</script>
</body>
</html>


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


Простой способ, увидеть какие части страницы перерисовываются включить опцию “show paint rects” всё в том же разделе “Rendering” окна настроек панели разработчиков. После включения обратите внимание как анимированный элемент, и кнопка мерцают красным при клике по кнопке.


image


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


image


Заметьте, что Chrome’е не всегда перерисовывает слой полностью. Он пытается быть выборочным и перерисовывать только те фрагменты слоя (те самые тайлы отмеченные голубыми границами) в которых DOM подвергся изменению. В нашем случае только один элемент на весь слой, но в большинстве реальных проектов элементов на слой приходится гораздо больше.


Напрашивается следующий вопрос: что приводит к устареванию DOM’а и его перерисовке? Сложно в нескольких предложения охватить все случаи, которые могут привести к невалидности DOM’а. В большинстве случаев это порча DOM’а посредством изменения CSS стилей и динамическая генерация видимого контента в рантайме. Тони Гентилкор описывал их в своём блоге, также Стоян Стояноф писал очень детализированную статью, но она ограничивается описанием перерисовки без деталей этой новой штуки, о которой мы пытаемся говорить — композиционирование посредством видео подсистемы.


Складываем всё вместе: DOM в экран




Так как же Chrome’е превращает DOM в изображение на экране? Концептуально можно выделить следующие шаги:


  1. Берёт DOM и разбивает его на слои, следуя изложенным выше критериям

  2. Программно рисует каждый из слоёв по отдельности

  3. Отправляет их GPU в качестве текстур

  4. На графической подсистеме компонует все слои в финальное изображение


Это то, что происходит при прорисовке первого кадра страницы. Но есть несколько способов сократить накладные расходы на рендеринг каждого следующего кадра:



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

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


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


На этом всё!


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] Google выкатила замену Javascript — язык Dart

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

Вот что написал Ларс Бак, инженер-программист и глава Dartisan:



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


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


SDK включает в себя легкий, но мощный редактор, с возможностью автозавершения кода, рефакторинга, перехода к определениям, функцией отладки, имеющий подсказки, предупреждения и многое другое. SDK также предлагает цикл edit/refresh с Dartium, пользовательской версией Chromium с родной Dart VM. Вне браузера Dart VM также может использоваться для асинхронных вычислений на стороне пользователя.


Для запуска кода в современных браузерах есть транслятор dart2js. Производительность сгенерированного кода значительно улучшилась с момента нашего первого выпуска и во многих случаях получилась почти что равной родному JavaScript коду. Согласно DeltaBlue benchmark сгенерируемый код работает даже быстрее, чем JavaScript. Размер выходного кода так же существенно сократился. Сгенерированный JavaScript для игры Pop, Pop, Win! в стал на 40% меньше, чем это год тому назад. Производительность VM продолжает улучшаться, теперь это от 42% до 130% быстрее, чем родной JavaScript, выполняющийся в V8 (в зависимости от базовых показателей).



Dart SDK также имеет менеджер пакетов, с более чем 500 пакетами от сообщества. Такие как AngularDart и polymer.dart, которые служат высокоуровневыми основами для строительства веб-приложений. Так же Dart-разработчики могут продолжать использовать свои любимые библиотеки JavaScript вместе с Dart.


В будущем команда Dart будет заниматься улучшении Dartium, увеличением производительности и развитием платформы. В частности изменение основных технологий (Google Chrome пример переводчика) для обеспечения обратной совместимости.



Попробовать Dart можно тут. Dartisans сообщество на Google +.


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] История создания стартапа и последующая его трансформация в аутсорсинговую контору

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

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

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



Заранее прошу не сетовать за наличие имен в статье. Она и для меня тоже.

Меню? Где ваше меню?




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

Цель есть — не вижу препятствий!




Действительно, энтузиазма было только отнимать. Вера в светлое будущее сочеталась с простодушной наивностью. Счастливое состояние, нечего сказать. Позвав друга Сергея и получив от него искреннюю поддержку своей инициативы мы с бесстрашием стали воплощать идею в жизнь. Я на себя возложил полную техническую реализацию, а ему оставил маркетинг. Бизнес план был простой — рас два и в продакшн, и монетизировать продукт как только можно. И понеслась — спецификации, мокапы, первые наброски и реализация. Было решено делать веб-часть на symfony2, и пилить приложения для iOS и под андроид. С вебом я бы справился самостоятельно, а в мобильной части совсем не было практического опыта. Для этого дела привлек своих товарищей — с одним из них занимались музыкой, а со вторым работали в одной конторке. Оба требовали оплаты своей работы. Пускай не по рыночным ценам, но тоже ощутимо. Программер под iOS получил даже 10% от прибыли в будущем.

imageimageimage


Дао Тойота и производственный процес.




По-тихонечку проект стал воплощаться в жизнь. Я написал админку и API для iOS & android. Занятным стала разность форматов отправки информации на iOS (plist) & android (json). Мобильные программист iOS за месяц склепал отличный прототип, который мы допиливали еще месяца три. Долго игрались с скоростью и плавностью прокрутки table view (это там, где список всех товаров с картинками). В итоге добились плавной подгрузки и рендеринга при прокрутке вниз-вверх при наличии даже свыше ста элементов на одном экране. Потом за дело принялся прогер под андроид. Нужно заметить, что потом было достаточно просто и быстро заделать версию для таблеток на андроиде руками опытного программиста. Веб часть этим временем разрослась ролями админа, ресторана, официанта. Можно уже было полноценно заказывать еду или услугу прямо в номер отеля, а официант, получив заказ мог легко распознать эту информацию и пустить заказ в обработку. Счастью не было предела. Ну а потом, наступила суровая действительность.

Как никому не нужно? А может все-таки?




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

Долго ждать не пришлось. Уже было оформлено ООО, небольшой уставной капитал. Его хватило, чтобы купить 100 пластиковых подставок и на типографию рекламных материалов, помещаемых в эти пластиковые прозрачные подставки. План был такой: посетитель приходит в ресторан, смотрит на подставку, видит QR-код и простой урл, с которого стояла переадресация на приложение, скачивал/ставил приложение. Открывал приложение, автоматически подгружалось меню именно этого ресторана (магия), он смотрел на кучу категорий, потом элементов меню, клацал кнопочку “+” там где он хочет добавить блюдо в заказ, клацает на свой заказ, нажимает “Заказать”, вводит номер своего столика и нажимает “Готово”. Потом, в колонках ресторана звучит известный хрюк из ICQ и официант получает на своем экране в браузере этот заказ, и пускает его в обработку. Элементарно, ведь. Сказано — сделано. Все столики стали пестрить пластиковыми подставками с синенькой рекламкой приложения, QR кодом, урлом и паролем к WiFi.

Первый заказ.




Ждали мы его долго. Уже даже не помню каким он был. Обновляли страницу официанта раз в день в надежде увидеть реальный заказ посетителя. Так прошла неделя. А потом еще одна. И еще две. Тем временем официанты и руководство ресторана постарались вбить в меню кучу своих блюд. Нужно еще упомянуть, что для составления меню мы собрали вместе их повара, фотографа и смирно пофотографировали весь ассортимент блюд (кроме алкоголя и напитков). Меню получилось отличным, но никому не нужным. Конечно, было бы гораздо приятнее осознать, что твое творение востребовано. Но так или иначе это оказалось не так, по крайне мере в этом ресторане.

Отели?! Где же отели?




Следующая мысль была о том, что идея возникла в отеле, и попытки это внедрить везде где только можно не сработают. Нужна целевая аудитория. Действительно — в отеле и люди остаются по-дольше, и заинтересованность в меню гораздо выше ибо можно в номер и чайку, и завтрак. Сказано — сделано. Одна большая гостиница проявила готовность с нами сотрудничать, благодаря Сереге. Да еще и за деньги. Что-то около 50$/месяц. Новый приток энтузиазма нам принес наличие новых функций в системе: нотификацию по смс для официантов, нового дизайна подставочек, и заказ на оных в 250 экземплярах. Было очень здорово сидеть и распаковывать этих 5 ящиков с подставками, и пихать в них привезенные из типографии свежие буклетики.

Суровая действительность.




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

imageimage


Безоблачная действительность.




Хороший опыт на то и хороший, чтобы изымать из него уроки. Со временем от фриланса стало подташнивать. Тогда я состоял в удаленном штате комманды веб-программистов сайта chess.com. Хорошие ребята. Мне с ними очень нравилось. Но работа дома, отсутствие дисциплины давало о себе знать. Характер сыграл со мной отнюдь не злую шутку. Был ноябрь 2012 года…

Даешь карбамид! Или сказ о друзьях в бизнесе.




Собрав самых близких друзей Сергея, Глеба в кучу, было решено делать большой бизнес. При этом, он должен отличаться от программирования, ибо достало. Сняли небольшой офис, и стали туда каждый день ходить. Я пригласил “походить в офис” одного из лучших фронтенд-прогеров Украины Пашу, который тоже работал дома на проект exercise.com. Глеб при этом еще преподавал в университете. Выбрали направление внешняя экономика. Экспорт. Благо экспортировать из Украины можно много всего. Агенты, то бишь. Ну и понеслась: alibaba, prom.ua, all.biz. При этом нужно сказать, я продолжал фрилансить. Через месяц к нам приехали делегация итальянцев купить (!!!) пару миллионов тонн такого удобрения, как карбамид. Химпром у нас работает хорошо, и никто просто так нам бы столько сырья не продал и даже не стал бы разговаривать. А итальянцам нужно было не просто навалом (насыпью), а в их брендированых мешках, которые нужно было изготовить у нас. Отлично, мы сняли комнату для конференций в уже упомянутой гостинице, вели переговоры через переводчика (они не понимали английский). Это первое, что меня насторожило. Потом под конец переговоров они начали показывать свои фотографии с итальянскими знаменитостями, актерами, и т.д. Справедливым было бы отметить, что приехал только бизнесмен со своим сыном. Рассказывали про обработку хим веществ на их заводе в Марокко, а у нас за плечами, нужно было осознавать, только понимание местной ментальности (что само по себе большой ценности не имеет), контакт для прямой продажи удобрений с заводов и больше ничего. Так или иначе, после их беспощадных торгов с ценами стало очевидно, что кроме намерения купить тыщу-другую тонн удобений для того, чтобы попробовать толкнуть у себя в регионе, у них нет. А мы в свою очередь не могли провернуть даже это. А все почему? Потому что не было понимания предметной области вообще. А в чем понимание было? В программировании!

Аутсорсингу — да!




В то же время появилось несколько леваков от иностранных заказчиков и мы принялись за них. Быстро ли, плавно ли, Серега стал работать в госконторе по оценке товаров. Глеб и Паша вместе со мной стали заниматься аутсорсингом. Поначалу это был совместный фриланс, а не аутсорсинг. Пара клиентов из штатов, средненький бюджет — хватало только на еду себе и аренду офиса. Был суровый март 2013 года в Киеве с завалами снега и без других развлечений. Спустя некоторое время безудержного кодинга клиентов стало немногим больше, благодаря биржам труда, как то odesk. Стало ясно, что пора бы взять пару программистов, а то самим тяжко. Глеб быстро намайнил двух студентов из НАУ (Авиационный университет), которых сам когда-то обучал. Дело плавно шло. Ребята быстро влились в работу, хоть и работали по пол дня. Через месяца три у нас было уже 5 сотрудников, не считая меня и Пашу с Глебом. Офис на 30 квадратов начал был маловат, да и средства появились. Переехали в офис на 45 квадратов, но не расчитали. Спустя месяцев 5 нас стало около тринадцати и пришлось опять переезжать. И вот, месяц назад мы уже в офисе на 160 квадратов и нас больше 15 человек.

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


Основным выводом этого года стала убежденность: нужно делать то, что у вас лучше всего получается.


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


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] MVC 5 Owin авторизация на примере Вконтакте

Не так давно вышел mvc 5 и одним из ключевых изменений является система авторизации. При создании «пустого» mvc 5 проекта есть возможность подключить авторизацию для Facebook, Google, Twitter и Microsoft аккаунтов. Я тут же полез разбираться с тем как это все работает и результатом стал «middleware» модуль для сети Вконтакте. Его можно поставить через nuget пакеты поискав «Duke.Owin.VkontakteMiddleware» и посмотреть исходники: github.com/DukeNuken/Duke.Owin.VkontakteMiddleware

В интернете есть много статей о owin авторизации и проекте katana с которыми можно ознакомится и даже скачать исходники.



А сейчас предлагаю в общих чертах обсудить как это все работает. Немного истории. Когда то давно, лет 6 назад, один мой заказчик просил сделать на сайте красивые ссылки типа "/account/register" и поскольку проект был на asp.net то единственным решением было установление модуля UrlRewriting для IIS и на сайте все работало хорошо, но вот в студии такие линки понятно не открывались, что доставляло некоторые неудобства. С тех пор как Microsoft выпустило mvc логика UrlRewriting осуществляеться на стороне проекта (RouteConfig), точно так же делается на стороне проекта и оптимизация скриптов (BundleConfig). Это позволяет корректно работать проекту все зависимости от сервера. По такому же принципу в mvc 5 добавилась авторизация.


Класс Startup находится в проекте /App_Start и в нем есть всего одна функция ConfigureAuth(IAppBuilder app). Она дергается при старте проекта и подгружает так называемые middleware модули. Что это такое и как они работают? По сути это классы которые наследуются от AuthenticationMiddleware. В этом классе есть конструктор и метод CreateHandler(). Этот метод вызывается при каждом обращении к странице и все что он должен сделать это создать AuthenticationHandler который, в свою очередь, имеет 2 метода. Рассмотрим их подробнее


1) protected override Task ApplyResponseChallengeAsync() — этот метод вызывается после отработки логики в контролах и перед отправкой response к пользователю. Он делает 3 важных шага. Проверяет код http ответа — равен ли 401 (not autorized), если да то специальным хелпером проверяется должен ли этот модуль делать авторизацию, если да то делается редирект на сайт авторизации и в результате юзер видит такую вот форму:


image


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


После подтверждения юзер будет переброшен назад на ваш сайт на страницу возврата модуля. Примерно такую '/signin-vkontakte?code=8e40fbe05c7ec232c0' (эта страница возврата задается в параметрах модуля) и в этот момент отрабатывает второй метод метод


2) public override async Task<bool> InvokeAsync() — этот метод дергается на каждой странице до того как отрабатывают контролы и сверяет свою «базовую» линку c запросом. Если они совпадают, то происходит сама авторизация. На примере модуля для вконтакте этот метод по сути ждет линку '/signin-vkontakte' от первого метода.


Внутри метода InvokeAsync дергается страница «oauth.vk.com/access_token» и получает token, после этого происходит обращение к Vkontakte API и получение информации о пользователе — имя и id. На основании этих данных создается AuthenticationTicket. В свою очередь AuthenticationTicket используется для создания ReturnEndpointContext объекта и сохранение информации через Microsoft.Owin.Security.AuthenticationManager. После этого пользователь перебрасывается на /Account/ExternalLoginCallback и может завершить регистрацию указав под каким именем он хочет зарегистрироваться на сайте.


Хотелось бы отметить несколько вещей:



1) Поведение «middleware» модуля очень похоже на обычный http модуль, который получает управление в начале и в конце запроса.

image

2) Казалось бы, есть два типа регистрации — регистрация на сайте и регистрация через owin модули, но в конечном итоге когда после авторизации на Вконтакте пользователь будет возвращен на страницу сайта "/Account/ExternalLoginCallback" (на странице будет сообщение что он Вконтакт авторизацию прошел успешно, текстовое поле для указания имени и кнопка Register), то только тут при нажатии на Register будет создан обычный аккаунт и в нем будет указано что он относится к «Vkontakte» провайдеру и в качестве параметра там будет userid. В базе это выглядит так


image


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


Спасибо за внимание.


Живой пример тут freemusiclib.com/Account/Login


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] Скрипты для управления виртуальными хостами на веб-сервере Debian

Хочу поделиться небольшой наработкой, которая упрощает администрирование веб-севера, работающего под управлением Debian-подобной операционной системы. Сразу оговорюсь, я далеко не гуру в этой области, просто в какой-то момент мне понадобилось поднять vsftpd, nginx, PHP-FPM и PostgreSQL. Ни для кого не секрет, что при добавлении виртуальных хостов, настройке пулов PHP-FPM и создании баз данных, приходится выполнять одни и те же действия. Удаление виртуальных хостов со всем, что с ними связано, а также создание резервных копий тоже весьма однообразны. Поэтому было бы неплохо обзавестись скриптами, которые автоматизируют все эти вещи.



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

И все же для начала стоит рассмотреть существующие решения. Одно из них описано в статье. В ней приводится пример скрипта для FreeBSD, который создает виртуальный хост. Другое решение приводится в статье, и там рассматривается аналогичный скрипт, но уже для Debian.


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


К делу




Итак, имеется несколько скриптов:


  • siteadd.sh — для создания виртуального хоста;

  • passwd.sh — для смены пароля;

  • backup.sh — для создания резервной копии;

  • sitedel.sh — для удаления виртуального хоста.




Как с ними работать, описано на вики, но общая идея такова, что, например, при создании виртуального хоста test.ru скрипт спрашивает, какой пароль нужно назначить пользователю test.ru, создает этого пользователя в системе, затем создает папку /var/www/data/test.ru/public_html с файлом-заглушкой index.html и дает все необходимые права пользователю test.ru.

Далее скрипт создает файл конфигурации nginx по шаблону с нужными параметрами и аналогичным образом настраивает пул PHP-FPM, в PostgreSQL создает базу данных test_ru и пользователя test_ru, которого назначает ее владельцем.


Если при вызове скрипта указан параметр --no-php, то пул PHP-FPM не настраивается, а при создании файла конфигурации nginx используется шаблон без поддержки PHP. При наличии параметра --no-pgsql, в PostgreSQL не создается база данных и пользователь.


При изменении пароля для виртуального хоста test.ru скрипт спрашивает новый пароль и назначает его как для пользователя test.ru в системе, так и для пользователя test_ru в PostgreSQL.


При создании резервной копии для виртуального хоста test.ru скрипт создает:



  • архив файлов /var/www/backup/test.ru/YY-mm-dd_HH:ii:ss.tar.gz;

  • дамп базы /var/www/backup/test.ru/YY-mm-dd_HH:ii:ss.sql.




При удалении виртуального хоста test.ru скрипт удаляет базу данных и пользователя test_ru из PostgreSQL, удаляет папку /var/www/data/test.ru и пользователя test.ru из системы. Резервные копии не удаляются.

Следует отметить, что есть две версии скриптов:



  • обычная версия, которая лежит в ветке default;

  • версия с поддержкой передачи параметров в формате JSON, которая лежит в ветке json.




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

Что дальше?




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


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

  • дописать шаблоны конфигураций, т.к. там отсутствуют некоторые настройки;

  • написать скрипт очистки устаревших резервных копий;

  • обеспечить поддержку Apache и MySQL.




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

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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


[Из песочницы] Покопаемся в мозгах «умного» свича

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




Рассмотрим управляемые свичи. Классический пример с ними — опрашивать состояние каждого порта, а также объём и состав прошедшего трафика. Делается это средствами самого zabbix, как именно смотрите здесь. Только мне мониторинг этих параметров не нужен. Гораздо интереснее отслеживать, какие устройства подключены к коммутатору. Он ведь хранит и обновляет таблицу привязки mac адресов к портам, надо её только достать и красиво оформить. Однажды я нашёл на хабре, как получить эту таблицу. Двумя snmp запросами извлекаем списки портов и mac адресов, а потом по суффиксам значений OID-ов устанавливаем соответствие. Подробности смотрите в исходном посте, а здесь рассказывается, как улучшить такой мониторинг.

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


Чтобы решить эти проблемы, я написал небольшую программу на python. Это демон. С заданной периодичностью он сканирует локальную сеть, опрашивает свичи и посылает информацию на сервер zabbix. Информация по всем портам всех коммутаторов сначала записывается во временный файл, а потом за одно подключение передается серверу утилитой zabbix_sender (с помощью ключа --input-file). Для опроса коммутаторов по snmp используется стандартная программа snmpwalk. Перед этим демон проводит arp сканирование доступных локальных сетей сканером nmap. Это, с одной стороны, «разогревает» кеш, а с другой, даёт отображение mac адресов в ip. Полученные таким образом ip адреса демон может дополнительно преобразовывать в доменные имена (работает, если определены реверсивные доменные зоны).


Так выглядит результат на zabbix сервере


На картинке представлен коммутатор HP Procurve 2520. С помощью vlan'ов на нём определено семь подсетей: пять — локальных и две — внешних к разным интернет-провайдерам. Два mac адреса внизу как раз принадлежат шлюзам провайдеров. Машина с демоном во внешние подсети не смотрит, поэтому ip адреса не определись. Если на порту висит много устройств, для наглядности отображается запись «another switch» (при желании это отключается).


А вот история по одному из портов. К нему подключен ip-телефон и компьютер. Видно, как сотрудник включил компьютер в начале дня, работал, работал… а потом ушёл пораньше. Пятница всё-таки.


Демон называется smonitor и доступен на github.com:

git clone https://github.com/ifke/smonitor.git


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

./smonitor.py --debug


Настройки приложения находятся в файле Settings.py. Там тоже python код, но он состоит только из определения переменных, поэтому разобраться несложно. Подсказки по доступным параметрам смотрите в файле Settings.py.sample.rus. Так как использую в основном ubuntu, программа тестировалось на этом дистрибутиве, и инструкция по установке есть только для него. То же касается и коммутаторов — проверял демон на том, что есть в наличии: HP Procurve 2520, HP Procurve 1700 и D-Link DES-3028. Судя по этой информации, с оборудованием Cisco без допиливания программа работать не будет, потому что snmp запросы нужно делать отдельно по каждому vlan'у.


Демон не привязан именно к zabbix. Чтобы подружить его с другой системой мониторинга, достаточно переписать одну функцию, отвечающую за отправку данных. На самом деле, улучшать можно ещё много всего. Например, решить обратную задачу, то есть показывать для хостов, к какому порту какого свича они подключены. Научить демон определять, как соединены между собой коммутаторы. Добавить импорт соответствия mac и ip адресов из файла, тогда можно организовать полноценный мониторинг без arp сканирования, в том числе и сетей, к которым у демона нет непосредственного подключения (а кеш разогревать ping запросами по списку ip адресов). Короче, идей много только бы хватило времени и сил для борьбы с ленью.


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


Old-hard.ru — видеоблог о старых играх и железе


сегодня в 09:25


Сегодня вышел 8й, юбилейный выпуск видеоблога о старых играх и железе, и это видео я решил представить на суд хабравчан. Речь пойдёт об играх на приставке Nintendo 64.





Видеоблог этот появился в середине июля как этап развития одноимённого сайта, 17го ноября как раз будет юбилей в 3 месяца его существования. За это время было выпущено 13 видео.


Содержание основных выпусков:



  1. Шутер «Подземелья кремля» (DOS, 1995 год)

  2. Шутер ".kkrieger" весом в 96 килобайт (Windows, 2004 год)

  3. Платформенная аркада от Apogee — «Hocus Pocus» (DOS, 1994)

  4. Карманная android-консоль JXD S5110b.

  5. «Наследники волчьего логова.» (Wolfenstein 3D — фанатские апдейты графики и игры по мотивам.)

  6. Обзор современного китайского клона NES/Денди.

  7. История серии платформенных аркад Dangerous Dave. (DOS, id Software и не только).

  8. Эмуляция игр с Nintendo 64 (сегодняшний выпуск)




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

  1. Модификация Brutal Doom.

  2. Скролл-шутер Revenge of the Mutant Camels.

  3. Китайский VGA-to-TV адаптер.

  4. Обзор обзорщиков старых добрых игр и железа.




Ну и 13е видео — бонус видео, Сравнение тюнеров Beholder TV 503 FM и EasyCAP USB 2.0. Сейчас я бы его поместил наверное в тот же раздел Quick Shot.

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


Ссылка на канал.


P.S. Автор в курсе своей кагтавости, да.





Developers, stick with Russians – work in London




Переводы с

карты на карту


Переводы

через QR-Код


Новая функция

«Мой контроль»




Возьми Lumia 925 на тест-драйв сейчас.




Впечатляющие возможности

в стильном тонком корпусе из металла




Boomburum

исследует LTE


Эволюция средств связи

в путешествии по России




Проблемы коммуникации внутри бизнеса?



Смотри бесплатные курсы

и выиграй Xbox



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


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).


Система наблюдения в автомобиле за ним же на Raspberry Pi. Часть 2

В прошлой статье я описал:


  • создание на одном Raspberry Pi домашнего VPN-сервера;

  • установку и настройку на втором Raspberry Pi OpenVPN-клиента, Node.JS и 3G-модема.




В этот раз настроим и подключим GPS-приёмник и WEB-камеру через USB-хаб.



Подключение и настройка GPS-приёмника




Для этой цели я приобрёл ND-100S GPS DONGLE

Проверим, определилось ли устройство:



Наше устройство — Prolific Technology.

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

sudo apt-get install gpsd gpsd-clients python-gps -y
sudo reboot




Теперь посмотрим и увидим, что у нас загружается сервис gpsd, но без указания устройства ввода (этот вариант не работает):



Отключим этот демон:

sudo dpkg-reconfigure gpsd




На первый вопрос отвечаем «No»:



На второй тоже «No»:



Можно поправить вручную файл /etc/default/gpsd, но там написано что лучше использовать реконфигуратор пакета, что я и сделал.

Запустим демон для работы с приёмником:

sudo gpsd /dev/ttyUSB0 -F /var/run/gpsd.sock




Теперь попробуем получить координаты:



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

Отлично! Теперь добавим верный запуск демона в автозагрузку:



crontab -e





Подключение и настройка WEB-камеры




Для этой цели я нашёл старую WEB-камеру фирмы Logitech.

Собственно подключим нашу камеру и проверим:



pi@raspberrypi ~ $ ls /dev/video*
/dev/video0




Из-за скорости канала я предпочёл передачу изображения, а не видео.

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

Установим и сразу попробуем получить снимок:

sudo apt-get install fswebcam -y
fswebcam —save /home/pi/test.png






Заберём теперь и проверим:

scp pi@192.168.2.6:/home/pi/test.png ./




Где 192.168.2.6 — IP адрес, полученный от OpenVPN сервера.

В зависимости от скорости передачи можно настроить на меньшее разрешение снимков и формат обработки изображения.


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 fivefilters.org/content-only/faq.php#publishers. FiveFilters.org recommends: March Against Mainstream Media (More info).