...

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

[Перевод] Срочная новость: почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка

Это перевод статьи Джошуа Блоха «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken» 2006 года. Разумеется, новость уже не срочная, однако даже сейчас она представляет не только исторический интерес.

Я живо помню первую лекцию Джона Бентли в университете Карнеги-Меллон, на которой он попросил нас, свежеиспечённых аспирантов, написать функцию двоичного поиска. Потом он взял одно из решений и разобрал его на доске, и разумеется, в нём оказалась ошибка, как и во многих других наших попытках. Этот случай стал для меня наглядной демонстрацией к его книге «Жемчужины программирования». Мораль в том, чтобы внимательно расставлять инварианты в программе.


И вот, теперь 2006 год. Я был потрясён, узнав, что программа двоичного поиска, корректность которой Бентли доказывал формально и тестами, содержит ошибку. Не подумайте, что я придираюсь; по правде сказать, эта такая ошибка, что вполне может ускользать от тестеров десятилетиями. Более того, двоичный поиск, который я написал для JDK, тоже был багнутым лет эдак девять. И только сейчас, когда она сломала кому-то программу, о ней сообщили в Sun.



Так в чём же заключается эта ошибка? Вот стандартный двоичный поиск в Java, один из тех, который я написал для java.util.Arrays:



public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;

while (low <= high) {
int mid = (low + high) / 2;
int midVal = a[mid];

if (midVal < key)
low = mid + 1
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}




Ошибка в шестой строке:

int mid = (low + high) / 2;




В «Жемчужинах программирования» Бентли на счёт аналогичной строки пишет, что она «устанавливает m равным среднему этих чисел, округленному к ближайшему меньшему целому». На первый взгляд всё в порядке, но для достаточно больших low и high (а именно, если их сумма больше 231-1) возникает ошибка. Их сумма становится отрицательным числом, и mid также получается отрицательным. В Си это привело бы обращению памяти за пределами массива с непредсказуемыми последствиями, а Java кидает исключение ArrayIndexOutOfBoundsException.

Эта ошибка проявляется только на очень больших массивах, больше 230 (порядка миллиарда) элементов. В 80-х годах, когда книга увидела свет, это было невозможно, но теперь у нас в Google (да и вообще в любом проекте) это обычное дело. В «Жемчужинах программирования» Бентли пишет: «хотя первая версия двоичного поиска была опубликована в 1946, корректный код, обрабатывающий все значения n, появился лишь в 1962». На самом деле, корректный код до сих пор почти не встречался даже в самых популярных реализациях языков.


Так как же правильно написать этот код? Шестую строку можно переписать так:



int mid = low + ((high - low) / 2);




Хотя, возможно, быстрее и проще такой вариант:

int mid = (low + high) >>> 1;




В С/C++ (где нет оператора >>>) можно написать так:

mid = ((unsigned int)low + (unsigned int)high)) >> 1;




Ну уж теперь-то мы точно знаем, что ошибок больше нет, правда? Ну… скорее всего. Чтобы абсолютно строго доказать корректность программы, её нужно протестировать на абсолютно всех возможных входных данных, но на практике это почти никогда не осуществимо. А для параллельных вычислений всё ещё хуже: вам придётся тестировать программу для всех возможных внутренних состояний, даже и не пытайтесь.

Эта ошибка может вылезти в сортировке слиянием и в других алгоритмах типа «разделяй и властвуй». Если вы реализовывали такие алгоритмы, перепроверьте их, пока ошибка не привела к неприятным последствиям. Лично меня эта ошибка научила быть чуточку скромнее и не полагаться на очевидность даже небольшого и привычного куска кода, не говоря уже о действительно сложных системах, которыми мы пользуемся каждый день.


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


Апдейт 17 февраля 2008 г. Главный инженер финского исследовательского центра Нокии Антуан Трю (Antoine Trux) сообщил, предложенное исправление для Си и C++ не гарантирует корректной работы, потому что по стандартам этих языков арифметическое переполнение при сложении даёт неопределённый результат. Теперь, когда мы исправили этот недочёт, мы точно уверены, что программа работает правильно. ;)


Ссылки:


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.


Дайджест интересных материалов из мира веб-разработки и IT за последнюю неделю № 84 (16 — 23 ноября 2013)


сегодня в 22:38





Веб-разработка




CSS




JavaScripts







Браузеры




Веб-инструменты




Новости




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




Дизайн




Подборка бесплатных дизайнерских печенек




Занимательное


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


Дайджест за прошлую неделю.

Материал подготовили dersmoll и alekskorovin




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


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.


Ачивер: что к чему

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


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





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

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


Небольшое вступление

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


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


1. Какую потребность пользователя мы удовлетворяем?

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


Если потребность реально существует, то должны найтись и люди, которые готовы платить за её удовлетворение. То есть, должен существовать какой-то рынок удовлетворения этой потребности. И такой рынок существует. Что ж, поглядим на этот рынок.


Книги.

Рынок книг на тему саморазвития огромен; каждый год появляются новые авторские методики, которые сулят читателю удивительные жизненные блага после освоения новой техники. Особенно проворные авторы выпускают в год сразу по нескольку книг, каждая из которых непременно «лучшая в своём роде». Скорочтение, развитие внимания, памяти, логика для чайников, книги о том, как влиять на людей, всевозможные самоучители, пресловутый «секрет» – только вершина айсберга.


Тренинги.

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


И даже религиозные услуги!

Ещё более впечатляющих успехов достигла индустрия продажи «духовного развития». Все наслышаны о книгах одиозного Рона Хаббарда – создателя сайентологии, который прославился, создав своё религиозное движение и продавая многомиллионными тиражами книги об успехе и карьере.


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


Какую проблему пользователя мы решаем?

Потребность существует. А проблема – это затруднение, возникающее при удовлетворении потребности. Давайте отыщем затруднение.


Затруднение №1.

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

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


Затруднение №2.

Поставим себя теперь на место простого потребителя «услуг развития». Нужен ли мне как пользователю ещё один инструмент для постановки целей (типа уже существующих в изобилии дримбордов?). Ответ – нет. Человеку, который знает, чего хочет, для постановки целей достаточно листа и ручки, чтобы записать их и продумать шаги.

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


Затруднение №3

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


Соответственно, решение указанных проблем должно:

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

2) пользователю должны быть указаны совершенно конкретные способы достижения целей – те самые проторенные дороги, которые и нужны потребителю услуг развития

3) должны быть созданы условия, которые повышают вероятность достижения результата. Создатели продукта должны сделать всё возможное, использовать все доступные методы, чтобы повысить мотивацию пользователя, убрать тревоги, возникающие в связи с недостаточной информированностью, показать, что достижение целей – это модно, на это способен каждый; разжечь конкуренцию между пользователями. Сделать всё, чтобы облегчить жизнь пользователя в этом направлении.


Наше решение.

Основные требования к решению готовы, аудитория ясна и решение становится очевидным.

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


Как это сделать? Achiever.ru

Мы подошли к самому интересному – к конкретному решению понятных проблем.


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

1) Пользователь выбирает себе конкретную цель в одном из 4 разделов сайта. Запускается таймер, и пользователь должен достигнуть цели до того, как время выйдет. На его странице публикуются поставленные и достигнутые цели.

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

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

4) Пользователь делает то, что описано в гайде.

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

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


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


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


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.


Оптимизация запросов. Основы EXPLAIN в PostgreSQL (часть 2)



Подолжаю публиковать авторскую переработку Understanding EXPLAIN от Guillaume Lelarge.

Ещё раз обращу внимание, что часть информации опущено, так что настоятельно рекомендую ознакомиться с оригиналом.

Часть 1



Кэш




Что происходит на физическом уровне при выполнениии нашего запроса? Разберёмся. Мой сервер поднят на Ubuntu 13.10.

Останавливаю PostgreSQL, принудительно фиксирую изменения в файловой системе, очищаю кэши, запускаю PostgreSQL:

> sudo service postgresql-9.3 stop
> sudo sync
> sudo su -
# echo 3 > /proc/sys/vm/drop_caches
# exit
> sudo service postgresql-9.3 start




Теперь кэши очищены, пробуем выполнить запрос с опцией BUFFERS

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM foo;





QUERY PLAN

— Seq Scan on foo (cost=0.00..18334.10 rows=1000010 width=37) (actual time=0.525..734.754 rows=1000010 loops=1)

Buffers: shared read=8334

Total runtime: 1253.177 ms

(3 rows)





Таблица считывается частями — блоками. Кэш пуст. Таблица полностью считывается с диска. Для этого пришлось считать 8334 блока.

Buffers: shared read — количество блоков, считанное с диска.

Повторим последний запрос

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM foo;





QUERY PLAN

— Seq Scan on foo (cost=0.00..18334.10 rows=1000010 width=37) (actual time=0.173..693.000 rows=1000010 loops=1)

Buffers: shared hit=32 read=8302

Total runtime: 1208.433 ms

(3 rows)





Buffers: shared hit — количество блоков, считанных из кэша PostgreSQL.

Если повторите этот запрос несколько раз, то увидите, как PostgreSQL с каждым разом всё больше данных берёт из кэша. С каждым запросом PostgreSQL наполняет свой кэш.

Операции чтения из кэша быстрее, чем операции чтения с диска. Можете заметить эту тенденцию, отслеживая значение Total runtime.

Объём кэша определяется константой shared_buffers в файле postgresql.conf.

WHERE




Добавим в запрос условие

EXPLAIN SELECT * FROM foo WHERE c1 > 500;





QUERY PLAN

— Seq Scan on foo (cost=0.00..20834.12 rows=999522 width=37)

Filter: (c1 > 500)

(2 rows)





Индексов у таблицы нет. При выполнении запроса последовательно считывается каждая запись таблицы (Seq Scan). Каждая запись сравнивается с условием c1 > 500. Если условие выполняется, запись вводится в результат. Иначе — отбрасывается. Filter означает именно такое поведение.

Значение cost, что логично, увеличилось.

Ожидаемое количество строк результата — rows — уменьшилось.

В оригинале даются объяснения, почему cost принимает именно такое значение, а также каким образом рассчитывается ожидаемое количество строк.

Пора создать индексы.

CREATE INDEX ON foo(c1);
EXPLAIN SELECT * FROM foo WHERE c1 > 500;





QUERY PLAN

— Seq Scan on foo (cost=0.00..20834.12 rows=999519 width=37)

Filter: (c1 > 500)

(2 rows)





Ожидаемое количество строк изменилось. Уточнилось. В остальном ничего нового. Что же с индексом?

EXPLAIN (ANALYZE) SELECT * FROM foo WHERE c1 > 500;





QUERY PLAN

— Seq Scan on foo (cost=0.00..20834.12 rows=999519 width=37) (actual time=0.572..848.895 rows=999500 loops=1)

Filter: (c1 > 500)

Rows Removed by Filter: 510

Total runtime: 1330.788 ms

(4 rows)





Отфильтровано только 510 строк из более чем миллиона. Пришлось считать более 99,9% таблицы.

Принудительно заставим использовать индекс, запретив Seq Scan:

SET enable_seqscan TO off;
EXPLAIN (ANALYZE) SELECT * FROM foo WHERE c1 > 500;





QUERY PLAN

— Index Scan using foo_c1_idx on foo (cost=0.42..34623.01 rows=999519 width=37) (actual time=0.178..1018.045 rows=999500 loops=1)

Index Cond: (c1 > 500)

Total runtime: 1434.429 ms

(3 rows)





Index Scan, Index Cond вместо Filter — используется индекс foo_c1_idx.

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

Не забываем отменить запрет на использование Seq Scan:

SET enable_seqscan TO on;




Изменим запрос:

EXPLAIN SELECT * FROM foo WHERE c1 < 500;





QUERY PLAN

— Index Scan using foo_c1_idx on foo (cost=0.42..25.78 rows=491 width=37)

Index Cond: (c1 < 500)

(2 rows)





Тут планировщик решил использовать индекс.

Усложним условие. Используем текстовое поле.

EXPLAIN SELECT * FROM foo
WHERE c1 < 500 AND c2 LIKE 'abcd%';





QUERY PLAN

— Index Scan using foo_c1_idx on foo (cost=0.42..27.00 rows=1 width=37)

Index Cond: (c1 < 500)

Filter: (c2 ~~ 'abcd%'::text)

(3 rows)





Как видим, используется индекс foo_c1_idx для условия c1 < 500. Для c2 ~~ 'abcd%'::text используется фильтр.

Обратите внимание, что в выводе результатов используется POSIX фомат оператора LIKE.

Если в условии только текстовое поле:

EXPLAIN (ANALYZE)
SELECT * FROM foo WHERE c2 LIKE 'abcd%';





QUERY PLAN

— Seq Scan on foo (cost=0.00..20834.12 rows=100 width=37) (actual time=14.497..412.030 rows=10 loops=1)

Filter: (c2 ~~ 'abcd%'::text)

Rows Removed by Filter: 1000000

Total runtime: 412.120 ms

(4 rows)





Опять Seq Scan.

Строим индекс по c2:

CREATE INDEX ON foo(c2);
EXPLAIN (ANALYZE) SELECT * FROM foo
WHERE c2 LIKE 'abcd%';





QUERY PLAN

— Seq Scan on foo (cost=0.00..20834.12 rows=100 width=37) (actual time=20.992..424.946 rows=10 loops=1)

Filter: (c2 ~~ 'abcd%'::text)

Rows Removed by Filter: 1000000

Total runtime: 425.039 ms

(4 rows)





Опять Seq Scan? Индекс не используется потому, что база у меня для текстовых полей использует формат UTF-8.

При создании индекса в таких случаях надо использовать класс оператора text_pattern_ops:

CREATE INDEX ON foo(c2 text_pattern_ops);
EXPLAIN SELECT * FROM foo WHERE c2 LIKE 'abcd%';





QUERY PLAN

— Bitmap Heap Scan on foo (cost=4.58..55.20 rows=100 width=37)

Filter: (c2 ~~ 'abcd%'::text)

-> Bitmap Index Scan on foo_c2_idx1 (cost=0.00..4.55 rows=13 width=0)

Index Cond: ((c2 ~>=~ 'abcd'::text) AND (c2 ~<~ 'abce'::text))

(4 rows)





Ура! Получилось!

Bitmap Index Scan — используется индекс foo_c2_idx1 для определения нужных нам записей, а затем PostgreSQL лезет в саму таблицу: (Bitmap Heap Scan) -, чтобы убедиться, что эти записи на самом деле существуют. Такое поведение связано с версионностью PostgreSQL.

Если выбирать не всю строку, а только поле, по которому постоен индекс



EXPLAIN SELECT c1 FROM foo WHERE c1 < 500;





QUERY PLAN

— Index Only Scan using foo_c1_idx on foo (cost=0.42..25.78 rows=491 width=4)

Index Cond: (c1 < 500)

(2 rows)





Index Only Scan выполняется быстрее, чем Index Scan за счёт того, что не требуется читать строку таблицы полностью: width=4.

Резюме





  • Seq Scan — читается вся таблица.

  • Index Scan — используется индекс для условий WHERE, читает таблицу при отборе строк.

  • Bitmap Index Scan — сначала Index Scan, затем контроль выборки по таблице. Эффективно для большого количества строк.

  • Index Only Scan — самый быстрый. Читается только индекс.


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.


[recovery mode] Домашний сервер «всё-в-одном» — success story

Жил да был у меня роутер одной хорошей фирмы на букву «Dead». Ну, это с ним, собственно, и случилось.

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



Как это было?




Покопавшись в залежах железа, на свет были извлечены:

• Процессор Intel Core 2 Duo E8400 @ 3GHz

• При нём же – материнка Asus P5Q

• 2 планки DDR2 по 2Gb

• PCI-e сетевая карта TP-Link TG-3468

• Неопознанная сетевая карта WiFi (b/g/n) на базе Ralink RT3060

• Жёсткий диск Seagate 250Gb

Вывод lshw можно посмотреть тут.

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

Основы основ




За основу я взял дистрибутив Debian Testing, раскатанный через Debootstrap. Сверху сразу были поставлены openssh-server, firmware-ralink и pppoe/pppoeconf.

Ребутнувшись в свежепоставленную систему, я сразу перенёс SSH на 192.168.1.1 и отключил авторизацию по паролю (установив предварительно свой ключ).

Да будет сеть!




Для начала был запущен pppoeconf. К DOCSIS-модему оказалась подключена сетевая карта с именем eth1, в итоге был получен следующий конфиг /etc/ppp/peers/rt:

noipdefault
defaultroute
replacedefaultroute
hide-password
noauth
persist
plugin rp-pppoe.so eth1
user "ptn"
usepeerdns




Но это не всё – необходимо ещё настроить /etc/network/interfaces следующим образом:

auto rt
iface rt inet ppp
pre-up /sbin/ifconfig eth1 up
provider rt


Превращаем роутер в WiFi-AP




Изначальная задумка была в том, что бы сделать 2 WiFi-сети: одну для своих компьютеров и ноутбуков, с надёжным паролем и присоединением ко всем необходимым ресурсам, а вторую – для гостей, которым захотелось выйти в интернет, но не надо знать о том, что творится в моей сети.

В итоге на сервер был установлен hostapd с конфигом следующего вида (все названия сетей и пароли были изменены):

interface=wlan0
driver=nl80211
country_code=RU
ieee80211d=1
hw_mode=g
channel=9

ssid=Private
bridge=br0
preamble=1
ignore_broadcast_ssid=0
wpa=3
wpa_key_mgmt=WPA-PSK
wpa_pairwise=TKIP CCMP
rsn_pairwise=CCMP
wpa_passphrase=MyVeryStrongPassword
wmm_enabled=1
ieee80211n=1
ht_capab=[HT40-][SHORT-GI-20][SHORT-GI-40]
internet=1

bss=wlan0_0
ssid=Guest
preamble=1
ignore_broadcast_ssid=0
wpa=3
wpa_key_mgmt=WPA-PSK
wpa_pairwise=TKIP CCMP
rsn_pairwise=CCMP
wpa_passphrase=passw0rd
wmm_enabled=1
ieee80211n=1
ht_capab=[HT40-][SHORT-GI-20][SHORT-GI-40]
internet=1




Тут мы ставим ещё и bridge для eth0 и wlan0 – это позволит подключившимся к нашей сети видеть её целиком, а не беспроводной сегмент. Модифицируем networks:

auto eth0 wlan0 wlan0_0 br0

iface eth0 inet manual

allow-hotplug wlan0
allow-hotplug wlan0_0

iface wlan0 inet manual
pre-up ifconfig wlan0 hw ether f2:7d:68:6d:51:30

iface br0 inet static
bridge_ports eth0 wlan0
address 192.168.1.1
netmask 24

iface wlan0_0 inet static
address 192.168.254.1
netmask 24




Немного о магии в pre-up для wlan0: для работы с несколькими AP нам надо использовать больше, чем один MAC-адрес. Hostapd назначает MAC для виртуальных интерфейсов (wlan0_0 в нашем случае) автоматически, но для этого адрес первой точки доступа должен иметь несколько «пустых» битов в конце. Я не стал мелочиться и освободил сразу 4 штуки. Задача на дом – посчитайте, сколько максимум AP теперь можно запустить на одной карте.

Налетай – IP всем и каждому, бесплатно!




Всем компьютерам в сети, как это ни прискорбно, надо выдать IP-адреса. Да-да, этим мы и будем заниматься.

Недолго думая, на сервере был запущен DHCP-сервер следующей конфигурации:

update-static-leases on;
authoritative;
allow unknown-clients;
use-host-decl-names on;
log-facility local7;

subnet 192.168.1.0 netmask 255.255.255.0 {
interface br0;
authoritative;
range 192.168.1.2 192.168.1.254;
option subnet-mask 255.255.255.0;
option ntp-servers 192.168.1.1;
option domain-name-servers 192.168.1.1;
option netbios-name-servers 192.168.1.1;
option routers 192.168.1.1;
option domain-name "local";
}

subnet 192.168.254.0 netmask 255.255.255.0 {
interface wlan0_0;
authoritative;
range 192.168.254.2 192.168.254.254;
option subnet-mask 255.255.255.0;
option domain-name-servers 8.8.8.8, 8.8.4.4;
option routers 192.168.254.1;
}

local-address 192.168.1.1;




Видно, что для 192.168.1.1/24 так же выдаются DNS, WINS, NTP и шлюз 192.168.1.1 – самое время их настроить.

Со шлюзом всё просто, думаю, эти команды не знает только ленивый:

sysctl net.ipv4.ip_forward=1
iptables –t nat -A POSTROUTING -o ppp0 -j MASQUERADE




Разумеется, ставим iptables-persistent для сохранения наших настроек, а так же прописываем соответствующие параметры в /etc/sysctl.conf.

Теперь наш сервер является полноценным китайским роутером за 10$. Что? Вам кажется слабовато? Мне тоже. Едем дальше.

Как пройти в библиотеку?




Думаю, никто не забыл, что нам нужен DNS? Простейший forwarding настраивается до нелепости просто, но ведь мы делаем полноценный сервер с резолвингом и реверс-зонами… Ставим bind9, и настраиваем:

options {
directory "/var/cache/bind";
forwarders {
8.8.8.8;
8.8.4.4;
};
dnssec-validation auto;
auth-nxdomain no;
listen-on { 127.0.0.1; 192.168.1.1; };
allow-transfer { none; };
version none;
};
zone "local" IN {
type master;
file "/var/lib/bind/db.localnet";
};
zone "1.168.192.in-addr.arpa" IN {
type master;
file "/var/lib/bind/db.localnet-rev";
};




Теперь нам нужны файлы прямой и обратной зоны:

/var/lib/bind/db.localnet


$ORIGIN .
$TTL 86400 ; 1 day
local IN SOA ns.local. router.local. (
200216990 ; serial
28800 ; refresh (8 hours)
7200 ; retry (2 hours)
604800 ; expire (1 week)
86400 ; minimum (1 day)
)
NS ns.local.
$ORIGIN local.
$TTL 86400 ; 1 day
ns A 192.168.1.1
server A 192.168.1.1
router A 192.168.1.1





/var/lib/bind/db.localnet-rev


$ORIGIN .
$TTL 86400 ; 1 day
1.168.192.in-addr.arpa IN SOA ns.local. router.local. (
2001105214 ; serial
28800 ; refresh (8 hours)
14400 ; retry (4 hours)
3600000 ; expire (5 weeks 6 days 16 hours)
86400 ; minimum (1 day)
)
NS ns.local.
$ORIGIN 1.168.192.in-addr.arpa.
$TTL 3600 ; 1 hour
1 PTR router.local.





Просто? А теперь сделаем так, что бы каждый компьютер в сети можно было видеть не по IP, а по DNS-имени.

Для этого нам нужно настроить DDNS. Эта технология позволяет связать DHCP-сервер, выдающий адреса, и DNS-сервер.

Для начала создадим ключ для нашего DDNS:

dnssec-keygen -a HMAC-MD5 -b 128 -r /dev/urandom -n USER DDNS_UPDATE




Эта команда создаст нам 2 файлика с DDNS-ключом. Нам нужно содержимое ключа:

cat Kddns_update.+157+36693.key
DDNS_UPDATE. IN KEY 0 3 157 HEyb0FU9+aOXnYFQiXfiVA==




«HEyb0FU9+aOXnYFQiXfiVA==» и есть наш ключ.

Немного отредактируем наш конфиг DHCP, добавив в него следующие опции:

ddns-updates on;
ddns-update-style interim;
key rndc-key { algorithm HMAC-MD5; secret HEyb0FU9+aOXnYFQiXfiVA==; }
zone local. { primary 192.168.1.1; key rndc-key; }
zone 1.168.192.in-addr.arpa. { primary 192.168.1.1; key rndc-key; }
subnet 192.168.1.0 netmask 255.255.255.0 {

ddns-domainname "local.";
ddns-rev-domainname "in-addr.arpa.";
}




Так же поступим с DNS:

key "rndc-key" {
algorithm hmac-md5;
secret "HEyb0FU9+aOXnYFQiXfiVA==";
};

zone "local" IN {

allow-update { key rndc-key; };
};
zone "1.168.192.in-addr.arpa" IN {

allow-update { key rndc-key; };
};




Вуаля – и эта киллер-фича работает.

Будущее всё-таки здесь. Шестая версия




Так исторически сложилось ©, что мой провайдер (презрительный взгляд в сторону Ростелекома) не выдаёт IPv6 (хотя обещал).


В настоящее время на всей протяженности сети «Ростелеком» обеспечил возможность работы по протоколу IPv6, — парирует пресс-служба оператора.





Что ж, пофиксим это недоразумение. В качестве брокера я выбрал sixxs.net – у них есть туннельные серверы в России, и их туннель прост в настройке для случая с динамическим IP.

Процесс регистрации и получения настроек туннеля/подсети я опущу – там всё довольно просто. Остановлюсь на настройке.

Настройка IPv6 на самом сервере производится в 2 этапа. Во-первых, поставим пакет aiccu – это и есть туннелирующая программа. При установке у нас будет запрошен логин и пароль от sixxs, и некоторые другие данные. После запуска у нас появится новый интерфейс:

sixxs Link encap:IPv6-in-IPv4
inet6 addr: 2a02:578:5002:xxx::2/64 Scope:Global
UP POINTOPOINT RUNNING NOARP MTU:1280 Metric:1





Сервер теперь имеет доступ в v6-сеть – почему бы не поделиться ей с другими?

Для начала, разрешим IPv6-forwarding (не забудьте прописать в /etc/sysctl.conf):

sysctl net.ipv6.conf.all.forwarding=1



Настроек с iptables производить не надо – привет, 21 век!

Далее на сайте sixxs получаем подсеть. Её адрес будет очень похож на адрес нашего туннеля – будьте внимательны, они отличаются!

После получения адреса вида 2a02:578:5002:xxxx::2/64, приступим к его настройке. Во-первых, зададим нашему серверу адрес 2a02:578:5002:xxxx::1, добавив в interfaces следующие строки:

iface br0 inet6 static
address 2a02:578:5002:xxxx::1
netmask 64




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

interface br0
{
AdvSendAdvert on;
prefix 2a02:578:5002:xxxx::/64
{
AdvOnLink on;
AdvAutonomous on;
AdvRouterAddr on;
};
RDNSS 2a02:578:5002:xxxx::1 { };
};




Добавим IPv6 DNS в настройки нашего bind – для полного фен-шуя:

options {
forwarders {

2001:4860:4860::8888;
2001:4860:4860::8844;
};
listen-on-v6 { ::1/128; 2a02:578:5002:xxxx::/64; };

};




Это всё – теперь мы имеем доступ, например, к ipv6.google.com, или, что гораздо ценнее – к ipv6.nnm-club.me ;)

Пингвин, смотрящий в окно




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

Его настройка крайне проста: устанавливаем пакет samba. Конфиг по умолчанию надо немного изменить:

workgroup = WORKGROUP
wins support = yes
dns proxy = yes
interfaces = lo br0
bind interfaces only = yes
server role = standalone server




Проверяем результаты… О, да тут всё хорошо!



Кстати, так как у нас есть samba, можно сразу настроить файлопомойку. Но это уже настолько избитая тема, что я оставляю её на плечах гугла. По сути, всё и так должно работать из коробки – разве что read only для homes выключить да smbpasswd -a user

Который час?




Настроим раздачу времени на сервере: установим ntp. С конфигами всё до нелепости просто:

server 0.ru.pool.ntp.org
server 1.ru.pool.ntp.org
server 2.ru.pool.ntp.org
server 3.ru.pool.ntp.org

broadcast 192.168.1.1




А вот и результат:



Мы уже вплотную приблизились к роутерам уровня microtik за $150-$200. Но это же не всё? Конечно нет.

Killer-feature #1: I2P




А почему бы не иметь доступа в эту сеть без каких-либо настроек, без прокси-серверов и так далее? Вот и я думаю, «почему». Для начала установим вменяемую версию Java:

echo "deb http://ppa.launchpad.net/webupd8team/java/ubuntu precise main" >> /etc/apt/sources.list
apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys EEA14886
apt-get update
apt-get install oracle-java7-installer




И установим сам роутер:

echo "deb http://deb.i2p2.no/ unstable main" >> /etc/apt/sources.list
wget "http://www.i2p2.de/_static/debian-repo.pub" -O- -q | apt-key add -
apt-get update
apt-get install i2p i2p-keyring




Теперь создадим зону, направляющую все запросы к *.i2p на наш сервер. В конфиг bind:

zone "i2p" IN {
type master;
file "/etc/bind/db.i2p";
};




Сама зона:

$ORIGIN i2p
$TTL 7200
i2p. IN SOA ns.i2p. hostmaster.i2p. (
2010020701 ; serial
7200 ; refresh
1800 ; retry
7200 ; expire
7200 ; minimum
)
i2p. IN NS ns.i2p.
ns.i2p. IN A 192.168.1.1

*.i2p. IN A 192.168.1.1
*.i2p. IN AAAA 2a02:578:5002:xxxx::1




Отлично, но как теперь это обработать? Банально завернуть весь трафик на порт роутера у меня не получилось – прокси ругался на то, что не может так работать. Пришлось настраивать связку nginx+php5-fpm и писать небольшой скрипт. Как сделать первую часть – искать долго не надо, благо мануалов в сети полно. Вторая часть:

/etc/nginx/sites-enabled/i2p


server {
listen [2a02:578:5002:xxxx::1]:80;
listen 192.168.1.1:80;
# по этому адресу можно будет получить доступ к конфигам роутера
server_name localhost.i2p;
location / {
proxy_pass http://127.0.0.1:7657;
}
}
server {
listen [2a02:578:5002:xxxx::1]:80;
listen 192.168.1.1:80;
server_name *.i2p;
location / {
fastcgi_pass unix:/var/run/php5-fpm;
include fastcgi_params;
# принудительно задаём адрес скрипта
fastcgi_param SCRIPT_FILENAME /etc/nginx/proxy.php;
# передаём скрипту параметр с адресом HTTP proxy от i2p
fastcgi_param PROXY_PASS 127.0.0.1:4444;
}
}





Сам скрипт можно увидеть тут.

Это всё! Теперь мы имеем доступ в i2p даже с телефона – никаких проблем.

Killer-feature #2: делаем рабочее место рабочей сетью




Так исторически сложилось ©, что я являюсь системным администратором по удалёнке сразу в нескольких фирмах. И очень полезно иметь к ним доступ с любого компьютера в сети. Настройку OpenVPN (или любого другого) для сервера осуществляем как для любого другого клиента. Например, после этих действий у нас появился интерфейс tap0 с IP 10.0.0.7/24. Но если мы обратимся из локальной сети по адресу 10.0.0.1, то трафик уйдёт в default gateway провайдера. Исправим этот недостаток:

iptables -t nat -A POSTROUTING -d 10.0.0.0/24 -o tap0 -j MASQUERADE
iptables-save > /etc/iptables/rules.v4




Аналогичным образом поступаем для всех сетей на сервере.

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




У нас есть полноценный сервер, который мы можем использовать по своему усмотрению. DNS, nginx, IPv6, i2p… Можно так же установить зону для локальной разработки, например, *.dev, и тестировать свои сайты с любого устройства в локальной сети. Так как каждый компьютер в сети имеет свой постоянный IPv6-адрес, можно иметь к нему доступ из любой точки мира (Security warning! Настраивайте файрволы правильно!).

И это всё – лишь вершина айсберга. То, что будет его подводной частью – решать вам.

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


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.


Кто-то осуществил транзакцию биткоинов на $160 млн


сегодня в 18:31


Bitcoin-адрес с историей крупных транзакций прошлой ночью осуществил ещё один перевод на рекордную сумму 194 993 BTC, что составляет чуть более $160 млн в эквиваленте по текущему курсу.

Что характерно, владелец этой суммы заплатил 0 BTC комиссионных за перевод. Только представьте, какова была бы комиссия при международном переводе 160 миллионов долларов через банковскую систему.



На сегодняшний день это самая крупная транзакция в сети Bitcoin.






1472


1






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.


Скажем спасибо WINAMP • thxwinamp.com


сегодня в 18:27


Добрый день!

В общем-то я даже не уверен, что данная 6-часовая поделка достойна поста, но оффтопик на то и оффтопик?



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

никто себе не представлял музыку без него. WINAMP = Музыка, Музыка = WINAMP.






Он уже давно не в топе, да и лучшим он был до 3й версии, но всё равно он стал культовым,

а культовый продукт заслуживает особое место.


На данной страничке можно оставить отзыв или просто сказать спасибо WINAMP'у. BONUS: Ну и конечно же нажать на кнопочку Play и услышать легендарную фразу, которую вероятно слышал весь мир и много много раз :)


Приглашаю и нас-вас, хабравчане, написать пару строчек про WINAMP: thxwinamp.com

* для международного восприятия можно сделать это на английском





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.


[Из песочницы] Windows Deployment Services и DHCP-сервер на Linux + пара особенностей

Привет Хабро-людям!

Будучи начинающим администратором, я стремлюсь познать все новое и как губка впитывать информацию. Так же ценю порядок в IT-инфраструктуре предприятия, логичность, доступность и универсальность. Стремясь добиться последнего, (использовать для Active Directory nix-овый DNS — BIND) не так давно потерпел фиаско, но не останавливаюсь на достигнутом. Я хотел бы поделиться с вами информацией, касающейся роли Windows Deployment Services в Windows Server 2012 и настройкой ее для работы со сторонним DHCP-сервером на Ubuntu Server.



Часть 1. Настройка DHCP-сервера




Вся сеть в нашей организации построена на UNIX-системах, а для, пусть и скромного по меркам IT, парка машин в 50 шт. все же хочется использовать все современные блага и удобства администрирования. Встал вопрос: как разворачивать Windows на ПК пользователей по сети, когда TFTP-сервер будет находиться отдельно от DHCP? Задача, хоть и простая, но заставила меня бегло изучить работу и настройку DHCP-сервера на Ubuntu. Нам же важна универсальность. :) Не поднимать же ради этого «виндовый» DHCP.

Всего-то требовалось, при описании сети, указать командой next-server, что TFTP-сервер находится на другом хосте. Приведу фрагмент конфига DHCP на примере сети 192.168.1.0/24:



shared-network 2_Users {
subnet 192.168.1.0 netmask 255.255.255.0
{
range 192.168.1.2 192.168.1.254;
default-lease-time 3600;
max-lease-time 7200;
option domain-name "test.jp";
option domain-name-servers 192.168.1.1;
option routers 192.168.1.1;
next-server 192.168.2.2; #Вот как раз строка, которая сообщает клиентам DHCP, что TFTP-сервер с PXE-загрузчиком находится на другом сервере. Он может находиться даже в другой подсети, главное, чтобы был туда маршрут.
option tftp-server-name "addc1.test.jp"; #DNS-имя нашего сервера с ролью WDS. Указываем на всякий случай, лишним не будет.
option bootfile-name "boot\\x86\\wdsnbp.com"; #Указываем, где на нашем сервере лежит файл для сетевой загрузки.
}




Вот, собственно, и все. /etc/init.d/isc-dhcp-server restart. Переходим к настройке WDS.

Часть 2. Настройка роли Windows Deployment Services




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

После установки роли, ее консоль будет доступна в списке Администрирование Панели управления Windows Server и носит название Службы развертывания Windows.

image


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


Если в вашей сети используются доменные службы Active Directory, то при настройке сервера можете указать, будет ли сервер изолирован или завести его в AD. Куда важнее будет позже отметить, что DHCP-сервер находится в другом месте и не нужно слушать подключения на портах нашего WDS-сервера.



  • Вам потребуется указать, интегрировать ли сервер в AD

  • Указать место хранения образов установки

  • Выбрать политику ответов клиентам. Здесь немного подробнее.




image

Если ограничиться только установкой системы, то можно выбрать пункт «Отвечать всем...» т.к., установка Windows потребует пары логин/пароль от сервера, с которого происходит загрузка. Несанкционированная установка «винды по сетке» не прокатит.



  • В конце будет предложено добавить первый образ




Хочу обратить ваше внимание на вкладку «Протокол DHCP» свойств сервера.

image

Здесь как раз и требуется снять птичек, если вы используете сторонний DHCP-сервер. А на вкладке «Клиент» можно указать, заводить ли новых пользователей в домен.

image


Часть 3. Интересности




Как известно, образы Windows добавляются на WDS-сервер в два этапа: добавления загрузочного образа (boot.wim) и образа установки (install.wim). Вот тут я и заметил маленькую и интересную особенность. В нашей компании используются ОС Windows, начиная с Windows 7, Server 2008R2 и заканчивая Windows 8.1 и Server 2012. Как известно, содержимое boot.wim — это то, что мы видим, запустив установку Windows с диска. И если при установке с диска важны только драйверы на контроллер HDD, то для сетевой установки важны еще драйвера на сетевой адаптер. В этой статье хорошо описан способ внедрения драйверов в дистрибутив с помощью WAIK. Но когда я добавил образ загрузки из дистрибутива Windows 8.1 и проверил его, то заметил, что база драйверов на сетевые адаптеры расширена. Но главная особенность не в этом. :) Используя один, самый последний образ загрузки Windows (пусть даже собранный вами лично с помощью WAIK), можно устанавливать любые редакции Windows, начиная с Windows Vista, заканчивая Windows Server 2012R2. Вам не нужно добавлять кучу образов для загрузки — выберет один, универсальный и современный. Можно добавлять только образы установки (install.wim), выбирая, какие редакции Windows вам нужны.

Вы можете создать в консоли управления WDS группы образов…

image


… и в результате получите при установке список всех ОС, из групп Desktop и Servers, выберете нужную и проинсталлируете. Не забывайте, для установки требуется ввести логин/пароль администратора сервера.


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

image


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


Вот, собственно, и все, чем я хотел с вами поделиться. Если хотите расширить возможности WDS, на хабре есть статья "Добавляем WDS универсальности", где еще больший любитель этой самой «универсальности», рассказывает, как заставить WDS использовать GRUB2, а отсюда и установка Linux и утилиты реанимации… В общем, все для того, чтобы современный админ не таскал с собой флешку.


Я за совместное использование Windows и Linux. Спасибо за внимание!


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.


[recovery mode] Android In-app purchasing: платное отключение рекламы в своём приложении

Много раз уже просили написать статью о том, как в приложении реализовать платное отключение рекламы. По In-app уже былистатьи на хабре. Правда, они старую версию API рассматривали. В принципе, новая версия не особо то и отличается от старой. Была похожая статья, но там больше именно про отображение рекламы рассказывалось, а второй части статьи мы так и не увидели. Как оказалось, многим до сих пор интересен этот вопрос, решил написать как это реализовать в своём приложении.



In-App Purchase представляет собой сервис покупки виртуальных товаров внутри приложения (например игровой валюты, новых уровней и т.д.). Применяется он в основном в играх, в тех случаях, когда встает вопрос о необходимости заработка на своем творении.

В данной статье рассмотрю как можно использовать In-App Purchase для отключения рекламы в своём приложении.


Реклама в приложении




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

public interface AdsControllerBase {

public void createView( RelativeLayout layout);
public void show(boolean show);
public void onStart();
public void onDestroy();
public void onResume();
public void onStop();
}


Тогда обёртка для AdMob будет выглядеть примерно так:


Обёртка для AdMob


public class AdMobController implements AdsControllerBase, AdListener {
private static final String ADMOB_ID = "ваш_идентификатор_из_AdMob";
private static final int REQUEST_TIMEOUT = 30000;
private AdView adView;
private Context c;
private long last;

public AdMobController(Context activity, RelativeLayout layout) {
this.c = activity;
createView(layout);
last = System.currentTimeMillis() - REQUEST_TIMEOUT;
}

public void createView(RelativeLayout layout) {
if(PreferencesHelper.isAdsDisabled()) return;
adView = new AdView((Activity) c, AdSize.BANNER, ADMOB_ID);
RelativeLayout.LayoutParams adParams = new RelativeLayout.LayoutParams(
RelativeLayout.LayoutParams.WRAP_CONTENT,
RelativeLayout.LayoutParams.WRAP_CONTENT);
adParams.addRule(RelativeLayout.ALIGN_PARENT_BOTTOM);
adParams.addRule(RelativeLayout.CENTER_HORIZONTAL);

adView.setAdListener(this);

layout.addView(adView, adParams);

adView.loadAd(new AdRequest());
}

// обновляем рекламу не чаще, чем раз в 30 секунд
public void show(boolean show) {
if(adView == null) return;
adView.setVisibility((show) ? View.VISIBLE : View.GONE);
if (show && (System.currentTimeMillis() - last > REQUEST_TIMEOUT)) {
last = System.currentTimeMillis();
adView.loadAd(new AdRequest());
}
}

@Override
public void onReceiveAd(Ad ad) {}

@Override
public void onFailedToReceiveAd(Ad ad, AdRequest.ErrorCode error) {}

@Override
public void onPresentScreen(Ad ad) {}

@Override
public void onDismissScreen(Ad ad) {}

@Override
public void onLeaveApplication(Ad ad) {}

@Override
public void onStart() {}

@Override
public void onDestroy() {}

@Override
public void onResume() {}

@Override
public void onStop() {}

}





Тогда инициализация рекламы будет такой:



AdsControllerBase ads = new AdMobController(this, layout);


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


In-app purchasing или внутренние платежи в приложениях




Для того, чтобы работать с системой покупок необходим файл IMarketBillingService.aidl. Лежит он в /user/android-sdk-linux/extras/google/play_billing директории с SDK. Положить файлик надо в com.android.vending.billing пакет вашего приложения.

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


Для работы необходимо добавить разрешение в AndroidManifest.xml:

<uses-permission android:name=«com.android.vending.BILLING»/>


Очень помогает официальная документация и пример из SDK.


Необходимо определить ключик в приложении – PublicKey, полученный при регистрации аккаунта на Android Market

Определяем IabHelper и инициализируем. Если удачно, то пытаемся восстановить покупки.



// id вашей покупки из админки в Google Play
static final String SKU_ADS_DISABLE = "com.ads.disable";
IabHelper mHelper;
private void billingInit() {
mHelper = new IabHelper(this, BASE64_PUBLIC_KEY);

// включаем дебагинг (в релизной версии ОБЯЗАТЕЛЬНО выставьте в false)
mHelper.enableDebugLogging(true);

// инициализируем; запрос асинхронен
// будет вызван, когда инициализация завершится
mHelper.startSetup(new IabHelper.OnIabSetupFinishedListener() {
public void onIabSetupFinished(IabResult result) {
if (!result.isSuccess()) {
return;
}

// чекаем уже купленное
mHelper. queryInventoryAsync(mGotInventoryListener);
}
});
}



mGotInventoryListener – слушатель для восстановления покупок.



// Слушатель для востановителя покупок.
IabHelper.QueryInventoryFinishedListener mGotInventoryListener = new IabHelper.QueryInventoryFinishedListener() {
private static final String TAG = "QueryInventoryFinishedListener";

public void onQueryInventoryFinished(IabResult result,
Inventory inventory) {
LOG.d(TAG, "Query inventory finished.");
if (result.isFailure()) {
LOG.d(TAG, "Failed to query inventory: " + result);
return;
}

LOG.d(TAG, "Query inventory was successful.");

/*
* Проверяются покупки.
* Обратите внимание, что надо проверить каждую покупку, чтобы убедиться, что всё норм!
* см. verifyDeveloperPayload().
*/

Purchase purchase = inventory.getPurchase(SKU_ADS_DISABLE);
PreferencesHelper.savePurchase(
context,
PreferencesHelper.Purchase.DISABLE_ADS,
purchase != null && verifyDeveloperPayload(purchase));
ads.show(!PreferencesHelper.isAdsDisabled());

}
};





Теперь надо, собственно, саму покупку реализовать:

private void buy(){
if(!PreferencesHelper.isAdsDisabled()){
/* для безопасности сгенерьте payload для верификации. В данном примере просто пустая строка юзается.
* Но в реальном приложение подходить к этому шагу с умом. */
String payload = "";
mHelper.launchPurchaseFlow(this, SKU_ADS_DISABLE, RC_REQUEST,
mPurchaseFinishedListener, payload);
}
}


SKU_ADS_DISABLE – идентификатор товара, который вы создали в адмике Google Play. mPurchaseFinishedListener – слушатель:



// слушатель завершения покупки
IabHelper.OnIabPurchaseFinishedListener mPurchaseFinishedListener = new IabHelper.OnIabPurchaseFinishedListener() {
public void onIabPurchaseFinished(IabResult result, Purchase purchase) {
if (result.isFailure()) {
return;
}
if (!verifyDeveloperPayload(purchase)) {
return;
}

if (purchase.getSku().equals(SKU_ADS_DISABLE)) {
Toast.makeText(getApplicationContext(), "Purchase for disabling ads done.", Toast.LENGTH_SHORT);
// сохраняем в настройках, что отключили рекламу
PreferencesHelper.savePurchase(
context,
PreferencesHelper.Purchase.DISABLE_ADS,
true);
// отключаем рекламу
ads.show(!PreferencesHelper.isAdsDisabled());
}

}
};





Стоит отдельно поговорить о методе по верификации:

boolean verifyDeveloperPayload(Purchase p) {
String payload = p.getDeveloperPayload();
/*
* TODO: здесь необходимо свою верификацию реализовать
* Хорошо бы ещё с использованием собственного стороннего сервера.
*/

return true;
}


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


В принципе всё, теперь при запуске приложения просиходит проверка настроек (куда мы сохранили, что отключили рекламу):



PreferencesHelper.loadSettings(this);




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

Тестирование покупок




Сейчас довольно удобно тестировать своё приложение. Можно залить .apk как альфа/бета версию и опубликовать. При этом можно назначить группу в Google+, которая будет иметь возможность к тестированию. Если вы публикуете альфа или бета версию приложения, то в маркете она не появится, иметь доступ будет только эта группа.


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


Полностью рабочий пример можете посмотреть на гитхабе.


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.


[Из песочницы] Задача о ранце и код Грея

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.

image

КДПВ: задача о ранце на живом примере


Предыстория




Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2n (количество сочетаний, умноженное на длину суммы).



Прошло 5 лет. Я успел закончить школу и поступить в университет, но эта задача по-прежнему была со мной. Один раз, листая книгу «Алгоритмические трюки для программистов» (Hacker's Delight / Henry S. Warren Jr.), я наткнулся на описание кода Грея: это последовательность двоичных чисел, каждое из которых отличается от предыдущего только одним битом. «Стоп!» — подумал я — «Это означает… Да! Это означает, что в той самой задаче на каждом шаге перебора можно не считать сумму целиком, а лишь добавлять или вычитать одно число». И я тут же углубился в изучение темы.


Построение кода Грея




Код Грея можно построить для числа любой разрядности. Для одного разряда он очевиден:

0

1


Чтобы добавить второй разряд, можно к этой последовательности дописать такую же задом наперёд


0

1

1

0


и ко второй половине дописать единицы:


00

01

11

10


Аналогично для трёх разрядов:


000

001

011

010

110

111

101

100


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


Этот код назван в честь Фрэнка Грея, который изобрёл ламповый АЦП, выдававший цифровой сигнал именно в этом коде. При небольших изменениях уровня входного сигнала цифровой выход мог измениться только в одном бите, и этим исключались резкие скачки из-за неодновременного переключения битов.


Патент Фрэнка Грея

Иллюстрация патента Фрэнка Грея


Самое наглядное применение кода Грея — в датчиках угла поворота. Датчик, аналогичный тем, что был в старых механических мышах, но определяющий не относительное смещение, а абсолютное значение угла. Для этого на каждый датчик нужно несколько оптопар и несколько щелевых решёток. Причём каждое следующее положение датчика должно отличаться от предыдущего только состоянием одного бита, иначе на границах возможно несинхронное переключение битов, и следственно — резкие скачки в показаниях прибора. Здесь видна любопытная особенность кода Грея: последнее число также отличается от первого одним битом, поэтому его можно «закольцевать».


image

Датчик абсолютного угла поворота. Оптические щели расположены в соответствии с кодом Грея


Применение в задаче о ранце




Но вернёмся к задаче о ранце. Стандартная формула даёт нам код Грея по номеру:

G = i ^ (i >> 1)




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

0

1

0

2

0

1

0

3

0

1

0

2

0

1

0

4


Ничего не напоминает? Это номер бита, который мы устанавливаем в единицу, когда просто перечисляем обычные двоичные числа. Или иначе — номер младшей единицы в двоичном числе. Эта операция называется find first set и в большинстве процессоров существует в виде отдельной инструкции. Visual C++ предоставляет эту инструкцию в виде функции _BitScanForward.


Итак, теперь мы готовы написать программу, решающую задачу о ранце через код Грея. Сформулируем задачу так:



В файле input.txt в первой строке указана вместимость рюкзака, а в остальных строках — размеры вещей. В консоль нужно вывести максимальную загрузку рюкзака и размеры выбранных вещей. Проверку корректности ввода и пр. — нафиг.





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

#include <iostream>
#include <fstream>
#include <bitset>
#include <intrin.h>
using namespace std;

void main()
{
int target; // размер ранца
int nItems = 0; // количество предметов
int weight[31]; // веса предметов
ifstream inFile("input.txt");
inFile >> target;
while(inFile >> weight[nItems])
nItems++;
inFile.close();

const unsigned int nIterations = 1 << nItems; // количество комбинаций, 2^n
int sum = 0; // текущий вес вещей
int bestSum = 0; // лучший вес (максимальный без перегрузки)
bitset<31> mask; // текущая комбинация выбранных вещей
bitset<31> bestMask; // лучшая комбинация выбранных вещей
for (unsigned int i = 1; i < nIterations; i++)
{
unsigned long position; // какой по счёту бит инвертируем
_BitScanForward(&position, i);
mask[position] = !mask[position];
if (mask[position]) // кладём в рюкзак или убираем эту вещь
sum += weight[position];
else
sum -= weight[position];

if (sum > target) // перегруз
continue;
if (sum > bestSum) // Отличный вариант! Надо запомнить...
{
bestSum = sum;
bestMask = mask;
}
}

cout << "Best approximation: " << bestSum << endl;
cout << "Used weights:" << endl;
for (int i = 0; i < 31; i++)
if (bestMask[i])
cout << weight[i] << endl;
cin.get();
}




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

Работает действительно быстрее, чем сборка с нуля всех сумм, разница заметна уже при 20 числах, а при 30-и я так и не дождался выполнения наивного алгоритма, в то время как новый вариант выполняется за 7 секунд. Впрочем, учитывая экспоненциальную сложность, это совсем не мало: для 50 чисел использовать этот алгоритм уже нет смысла. К сожалению, любой точный алгоритм будет работать не быстрее, чем за 2n; быстрее возможно только приблизительное решение.


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


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.


9-я Хабравстреча в Киеве

image

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


Судя по настроениям в тайных инбоксах™, Хабракиевляне сильно соскучились по Хабравстречам и друг за другом. Как-никак, мы тут уже провели 8 Хабравстреч, многие продолжают общаться вне сайта, вне IT-тематики.


Зря недоброжелатели пускали слухи, что Хабравстречи отменили, и они теперь вне закона. Причина столь долгого, почти полугодового таймаута банальна: прежний организатор Дима а.к.а. Alliceinwonders пока не готов единолично заниматься организационной работой в связи с полной личной занятостью в своих проектах. Что вполне закономерно для некоммерческого мероприятия. В любом случае, львиную долю благодарности за все предыдущие 8 Хабравстреч следует высказать именно ему. И компании М.У.К., которая постоянно помогала нам в технических вопросах.


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


Что: 9-я Хабравстреча в Киеве

Где: коворкинг «Часопис» (ru: «Летопись»), ст. м. Льва Толстого, ул. Льва Толстого, д. 3

Когда: 1-го декабря, в воскресенье, с 13:00 до 18:00

Сколько стоит: 100 UAH

Связь: vk, habr, gmail, +38 (O5O) O55-24-15


Что будет происходить:

• Как и прежде, мы выступим с докладами. Список докладчиков на данный момент пополняется, со своими предложениями вы можете написать мне в ЛС. Актуальный список докладов обновляется тут:



  1. 5erg «Основы телемаркетинга для продажи IT-услуг»

  2. Виталий (ждёт инвайта) «Tiled Deferred и Tiled Forward рендеринг» (алгоритм освещения 3D-сцен, позволяющий рендерить тысячи источников света в кадре)




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

• Вместе с вами мы сделаем свой off-line Linked-In, с нардами и айтишниками

• И приятный бонус для дочитавших до конца. На Хабравстрече, ближе к завершению, мы раздадим $10.000. О том, как это будет происходить, вы сможете узнать, придя на встречу. Заинтриговали?

Мы нас ждём! Будет интересно


UPD:

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


Анонс опубликован по просьбе товарища 5erg


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.


[Из песочницы] Развитие CMS Textpattern и кому оно нужно

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

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

Перепробовав около сотни таких систем, светлую память о себе оставил PHP-Nuke — на тот момент она был хорош, но, не выдержав давление более молодых систем он ушёл в тень, пересел на Joomla и Drupal — они показались несколько сложными… Было ещё множество систем и фреймворков установив которые они прожили на локалхосте не больше пары дней.

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

Примерно одновременно с разочарованием в Wordpress, я открыл для себя Textpattern. Я тогда искал для себя систему, с которой создание типичного сайта занимало бы дня два-три с готовой вёрсткой. Попробовал. Первые впечатления от Textpattern — аскетизм и простота админки, но вместе с тем, всё логично и достаточно для работы. Первый сайт на нём я делал, конечно, не два дня. Но процесс пошёл, я втянулся. И подсел! Мой личный рекорд — удалось поднять на нём сайт за 2 часа! Плюс на нём сейчас работают четыре региональных портала (один из них ранее трудился на Wordpress).

Интернет рос. Рос и я в профессиональном плане. Рос и развивался Textpattern.

Textpattern Logo

За эти годы он сохранил все свои преимущества, прикрыв попутно все свои слабости. Прелестей у Textpattern множество:

— благодаря тому, что он весь написан функциями, он чрезвычайно быстр и лёгок. По опыту работы с Wordpress помню, что тот отжирает на генерацию страницы около 60 метров без кэширования, а с кешем — примерно 30-40 метров. Textpattern же забирает на себя 5-10 мегабайт памяти(!) без всякого кеша. Это позволяет и быстрее отдавать контент, и не нагружать хостинг на нагруженном проекте.

— простота настройки дизайна и структуры. Textpattern пошёл по своему пути развития — в этом и его сила, и его слабость. Код страниц сайта хранится не в отдельных файлах, как например в Wordpress, или Smarty, а правится в админке и хранится в базе. Это с первого взгляда усложняет подъём готового шаблона (в том же Wordpress можно просто скопировать шаблон на хостинг), но в практике сильно упрощает правку и отладку. Что экономит уйму сил и времени в итоге.
Преимущества Textpattern:



— Textpattern поддерживает из коробки ВСЕ существующие языки! Не нужно ничего переименовывать — всё уже работает на том языке, на котором вы говорите.

— естественно есть и хорошо работает ЧПУ

— большое количество плагинов и активное сообщество. Для Textpattern разработана не одна сотня серьёзных плагинов, так или иначе расширяющих его функционал.

— распределение ролей и прав пользователей.

— серьёзная взломоустойчивость, стабильность и надёжность. Если у вас на сервере нет дыр, или злобного вируса на рабочем компьютере, то взломать ваш сайт будет почти нереально! Сам Textpattern защищён великолепно.

— простота освоения и поддержки сайта. У меня есть несколько проектов, которые поддерживаю настоящие, классические блондинки. Даже с ними полёт нормальный.

— простое написание плагинов. При нормальном знании php, научиться писать хорошие плагины для Textpattern дело 1-2 месяцев. Разобравшись с внутренней логикой и структурой Textpattern, всё становится простым и изящным. Код у Textpattern красив, логичен и прост для понимания. Чем больше вникаешь в логику разработчиков, тем больше погружаешься в Дзен PHP.
Минусы тоже есть:



— свой язык разметки — Textile. Лично для меня удобен привычный html. Разработчики решили иначе, что отпугивает массу пользователей от CMS. Но есть простой выход — есть плагин, который позволяет переключить работу на классический WYSIWYG редактор (плагин hak_tinymce).

— из коробки вставка изображения, или галереи в статью заставляет поработать копипастером (решается плагинами, например ku_image_uploader).

— слабый функционал по работе с пользователями сайта. Нет нормального плагина для регистрации/личного кабинета.

— сложно сделать интернет-магазин.
Так для кого же подходит Textpattern?



Если ваш проект в первую очередь информационный и вы хотя бы знаете, что такое html теги, то Textpattern для вас — это Клондайк возможностей!

Для фрилансеров — способ быстрой и простой разработки проекта.

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

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

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.