Search
Write a publication
Pull to refresh
2
0
Send message

Разрезание на две равные части, часть вторая

Reading time3 min
Views19K
С первой частью можно невозбранно ознакомиться здесь.

Итак, дорогие друзья, в предыдущей части мы с вами поговорили о параллельном переносе, а сегодня займёмся поворотом. Это будет интересно. Сейчас быстренько вспомним основные понятия — и вперёд.



Интриги, расследования, скандалы

Разрезание на две равные части, часть первая

Reading time4 min
Views56K
Задачи на разрезание — это та область математики, где, как говорится, мамонт не валялся. Множество отдельных проблем, но по сути нет общей теории. Помимо всем известной теоремы Бойяи-Гервина, других фундаментальных результатов в этой области практически нет. Неопределённость — вечный спутник задач на разрезание. Мы можем, например, разрезать правильный пятиугольник на шесть частей, из которых можно сложить квадрат; однако мы не можем доказать, что пяти частей для этого было бы недостаточно.

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



Скандалы, интриги, расследования

Сфера из двух треугольников

Reading time7 min
Views61K
История этой демки такова: однажды один мой друг сделал для своей игры генератор карт планет и захотел, чтобы созданные таким образом карты показывались в виде вращающейся сферы. Однако, при этом он не хотел использовать 3D-графику, а вместо этого сгенерировал множество кадров с этой самой сферой, повёрнутой на разные углы. Количество используемой памяти было… скажем так, избыточным, ну а скорость генерации кадров (как и качество их исполнения) сильно страдала. Чуть подумав, мне удалось помочь ему оптимизировать этот процесс, но в целом меня не покидало справедливое ощущение того, что это задача для OpenGL, а вовсе не для 2D-графики.

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

Изображения: форматы и сжатие (1/3)

Reading time9 min
Views55K
Схематичное изображение PCX, GIF и PNG

На что при загрузке сайта расходуется больше трафика? Чаще всего это картинки, и их суммарный «вес» частенько в несколько раз больше, чем у разметки, скриптов и стилей. В файлах изображений распространенных форматов растровые данные хранятся в сжатом виде, и это значительно лучше, чем несжатый BMP. А если хочется ещё лучше? Ведь в достаточно крупных проектах каждый байт на счету (например, в TradingView, чего уж там скромничать).

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

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

Quickpong — разработка сетевой игры на основе фреймворка Twisted

Reading time6 min
Views17K
Разработал и запустил на домене quickpong.com онлайн версию игры Pong. В игре (by design) реализован только режим мультиплейера, то есть игра идет не против искусственного интеллекта, а против другого человека.

Игра представляет из себя клиент-серверное приложение, серверная часть написана на питоновском фреймворке Twisted, клиентская — на флэшовом фреймворке FlashPunk.

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

Прививка от реальности: розовые очки для браузера

Reading time7 min
Views26K
Почему вокруг так много матерятся? Одно дело, когда на ногу падает молоток, или когда надо срочно сообщить коллеге, что он не успевает сделать макет сайта. Но в Интернете-то у автора всегда должно быть достаточно времени, чтобы подобрать красивую фразу и показать себя грамотным интеллигентным человеком с большим словарным запасом. К сожалению, редок тот случай, когда обсценная лексика действительно уместна — навскидку, один на сотню.

Некоторые владельцы форумов, чатов и блогов борются с обилием мата организационными мерами (устанавливая правила) или техническими (используя парсеры), но самый большой недостаток существующих антимат-систем — это многочисленные ложные срабатывания, порождающие удивительные неологизмы вроде заштричлен, застрапенис и скигей (кто не догадался — в оригинале было слово «скипидар»). Также скрипты (а зачастую — и сами авторы текстов) иногда заменяют буквы из середины бранных слов на звёздочки (***) или символы "#$%^", из-за чего у меня возникает подозрение, что у этих людей вместо половых органов чёрные квадратики.

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

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

Приступим

Советы Google по кодированию на языке Python. Часть первая: советы по программированию

Reading time13 min
Views115K

Хай, Хабр!
Сегодня я хочу представить, дорогому хабрасообществу свой первый хабраперевод. Программировать на языке Python — подобно песне. Но еще лучше, когда Ваш код читаем и понятен, а значит чуть более поэтичен, чем обычно бывает производстве. У каждого свои правила и свои стереотипы относительно написания и оформления исходного кода, на каком бы языке он ни был написан. Множество копий сломано о щиты на форумах, но, как ни крути, нельзя не считаться с мнением авторитетных товарищей. Так что сейчас будет представлен перевод первой части стайл-гайда для языка Python от Google. Коснется он именно постулатов написания кода (вторая часть тоже скоро появится, а посвящена она будет форматированию исходного кода). Сразу предупреждаю: тут много (если не большая часть) прописных истин, которые все знают уже давно. Но я искренне надеюсь, что Вы сможете найти тут что-то новое или хотя бы вспомнить старое. Приступим под катом. И pdf тут как тут.
Читать дальше →

Опасности обучения по книгам

Reading time3 min
Views44K
Сегодня разработчики находятся в состоянии постоянного давления. Желание добиться высокого уровня владения новыми языками и инструментами, боязнь однажды выпасть из информационного потока может затмевать всё. Действительно, с риском потери конкурентоспособности сталкиваются как программисты, не следящие за тенденциями и движениями индустрии, так и постоянно читающие технические новости для ориентации: какие навыки выучить при наличии времени, какие игнорировать, какие методы следует использовать.

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

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

Поддержка Portable Native Client появилась в Chrome. Кто победит в гонке за нативным быстродействием — PNaCl или Asm.js?

Reading time1 min
Views13K
Google наконец-то выпустил портативную версию Native Client (PNaCl). Технологию Native Client, которая позволяет компилировать в машинный код и выполнять в браузере программы на С или С++, достигая практически нативной производительности, часто критиковали за то, что изначально NaCl поддерживал не все платформы, и для каждой из них приходилось компилировать отдельно. PNaCl компилирует исходный код программы в биткод LLVM — низкоуровневой виртуальной машины, которая поддерживает множество аппаратных платформ и гарантирует, что код будет работать практически везде.
Читать дальше →

EFF возобновил приём пожертвований в Bitcoin — благодаря правительству США

Reading time2 min
Views5K
В пятницу, 17 мая Фонд электронных рубежей возобновил приём пожертвований в криптовалюте Bitcoin. Около двух лет назад EFF в течение нескольких месяцев принимал биткоины, но затем отказался от этой практики по причине опасений юридического характера. EFF часто приходится защищать людей, у которых возникают проблемы с законом из-за использования современных технологий, и приём платежей в валюте, которая никем и никак не регламентирована официально мог создать ещё больше проблем и поставить под угрозу основную деятельность фонда.

Однако благодаря недавним инициативам FinCEN — подразделения министерства финансов США, которое занимается борьбой с отмыванием денег, финансированием терроризма и другими финансовыми преступлениями, юридический статус Биткоин приобрёл хоть какую-то определённость. Несмотря на то, что попытки правительства загнать криптовалюту в юридические рамки многими воспринимаются отрицательно, они могут стимулировать более широкое распространение Биткоин, так как многие люди и организации относятся к нему с опаской или пренебрежением именно из-за отсутствия официального признания.
Читать дальше →

SEGA портировала ёжика Соника на Andriod и iOS

Reading time1 min
Views17K
Одну из самых популярных игр 90-х теперь можно купить в Google Play за три доллара. Версия для iOS появилась чуть раньше. Доступны семь классических уровней, графика и звук обновлены с учётом возможностей современных устройств, но геймплей остался неизменным. Кроме того, теперь можно поиграть за друзей Соника — лисёнка Tails и ехидну Knukcles, кроме того, появился новый режим игры на время. Вот трейлер игры:



Источник: блог SEGA.

Шесть недель до закрытия Google Reader — спасаем всё что можно

Reading time3 min
Views59K
image

Google Reader появился в 2005 году. Год или два спустя я начал им пользоваться как основным источником информации. И вдруг нате, получите — не выгодно, не профильно, закрываемся… Как результат, во-первых потеряли продвинутую (гики) и лояльную аудиторию, во-вторых эти гики тут же начали писать или дописывать различные альтернативы. Усилилась сегментация, возникла проблема выбора ну и вообще some folks got pissed off
Читать дальше →

Игра Жизнь и преобразование Фурье

Reading time5 min
Views63K
Многие слышали о великом и ужасном быстром преобразовании Фурье (БПФ / FFT — fast fourier transform) — но как его можно применять для решения практических задач за исключением JPEG/MPEG сжатия и разложения звука по частотам (эквалайзеры и проч.) — зачастую остается неясным вопросом.

Недавно я наткнулся на интересную реализацию игры «Жизнь» Конвея, использующую быстрое преобразование Фурье — и надеюсь, оно поможет вам понять применимость этого алгоритма в весьма неожиданных местах.
Читать дальше →

Google отказывается от поддержки XMPP

Reading time1 min
Views44K
Много лет Google Talk работал на основе протокола XMPP, в том числе поддерживая XMPP Federation с другими сетями и делая возможным, например, использование ICQ через соответствующий jabber-транспорт в Google Talk (как в приложении, так и в чате в Gmail через web).
Однако, при переходе на Google Hangouts, представленный на последней конференции Google I/O, который объединяет Google Talk и Google+, Google отказывается от поддержки XMPP. Android-приложение Google Talk автоматически обновляется на Google Hangouts. Чат в Gmail пока можно переключать на Hagouts и обратно к классическому виду (соответственно, общение с джабер-клиентами других сетей и контактами ICQ и других транспортов возможно только в последнем случае).

[1]

Скрытые цепи Маркова, алгоритм Витерби

Reading time5 min
Views60K
Нам нужно реализовать детектор лжи, который по подрагиванию рук человека, определяет, говорит он правду или нет. Допустим, когда человек лжет, руки трясутся чуть больше. Сигнал может быть таким:

Исходный сигнал

Интересный метод, описан в статье «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition» L.R. Rabiner, которая вводит модель скрытой цепи Маркова и описывает три ценных алгоритма: The Forward-Backward Procedure, Viterbi Algorithm и Baum-Welch reestimation. Несмотря на то, что эти алгоритмы представляют интерес только в совокупности, для большего понимания описывать их лучше по отдельности.
Читать дальше →

Skype просматривает содержимое ссылок отправленных в чате

Reading time1 min
Views75K
image

Вернее обходит все HTTPS ссылки отправленные в чате HEAD-запросом.

Шаги для воспроизведения:

1. Отправляем в чате ссылку с https которая ранее через Skype не отправлялась

2. Через 10-40 минут наблюдаем HEAD запрос в access логе из сети 65.52.0.0/14 принадлежащей Microsoft. Запрос приходит без User-Agent.

Выдержка из пользовательского соглашения гласит:

«Skype may use automated scanning within Instant Messages and SMS to (a) identify suspected spam and/or (b) identify URLs that have been previously flagged as spam, fraud, or phishing links.»


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

Читать дальше →

Про мнимые и реальные оптимизации в 10 раз, целительный SSE, и все такое

Reading time6 min
Views38K
По мотивам одного вчерашнего поста про оптимизацию условных переходов при расчете x=sign(a,b)*min(abs(a), abs(b)) якобы в 10 раз. Краткая сводка:

  • оптимизация налицо, но размер мнимый: не в 10 раз, а 2.5 раза;
  • бенчмарки надо делать правильно: не надо мерить CPU stalls, RAM bandwidth итп вместо исследуемой функции;
  • бенчмарки надо делать правильно: иначе могут дико дрожать;
  • выставлять только приоритет прикольно, но на коротких бенчмарках зря: +0.5% скорости, -15% дрожания;
  • нужно мерить исследуемую функцию и только ее, только так получаешь корректные данные;
  • нужно греть проц, нужно считать минимум из N прогонов/секунд, только так побеждаешь дрожание;
  • нужно пользовать SSE, с ним получилось 8.6 раз, причем код… читается.

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

Wasted Dreams — история забытой игры (статья-пилот из цикла «Истории Игровой Индустрии»)

Reading time16 min
Views72K


В поисках утраченного ковчега – часть I


Представим, что вы тертый в боях игрок. Старый. Опытный. Человек, которого трудно удивить. Человек, который многое повидал. Человек, который видел Истоки. Каждая новая игра сопровождается вашим скрипом, — «А вот раньше…», «Помню, были времена…», «Детки, то, что вы считаете новым, не более чем хорошо забытое старое, я это видел в 19..». Предположим также, что вы новый Индиана Джонс своего времени, боец невидимого археологического фронта, который каждый божий день пытается отыскать свой Грааль. Грядущее вас интересует мало, настоящее вызывает скепсис, цель ваших поисков – прошлое. Полагаю, что нам с вами, сегодня, по пути.

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

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

На глубине временных пластов периода 1999 года моя лопата со звоном ударилась о неизвестный объект. По моим выкладкам в этом секторе не должно было находиться крупных и не изученных игр. Обкопав объект по периметру и сдув пыль там, где она мешала разглядеть символы я увидел… чудо. Это покажется невозможным, но в наш короткий игровой век мы до сих продолжаем находить неизвестные широкой публике работы древних зодчих. Можете представить мое удивление, изумление и благоговейный восторг, когда я увидел игру, созданную в стилистике…


Дать лопате шанс

Тёплый деревянный звук

Reading time1 min
Views39K


Аманда Гассей, которая несколькими месяцами ранее умудрилась распечатать на 3D-принтере работающую грампластинку, продолжает безумствовать. Опираясь на наработки из предыдущей серии экспериментов, теперь она с помощью скриптов на Python и Processing преобразовала файл MP3 в программу для 120-ваттного лазерного резака Epilog Legend 36EXT и смогла вырезать грампластинку из дерева и даже из плотной бумаги. Характеристики несколько хуже, чем у записей, распечатанных на 3D-принтере — 4-5 бит и 4,5 кГц. Как и в прошлый раз, подробное описание эксперимента и все использованные скрипты опубликованы на Instructables.


Под катом - больше фотографий и видео.

История прогноза погоды

Reading time8 min
Views65K
Занимаясь прогнозированием временных рядов, часто сталкиваюсь с идеей: «Вот бы реализовать такую модель прогнозирования, которая бы все-все учитывала и давала самый точный на свете прогноз». Утопия ли это? В ответе на этот вопрос окунулась в историю одного из самых сложных вопросов прогнозирования — прогнозирование погоды.

Прогноз погоды
Попробуем разобраться на примере прогноза погоды

Information

Rating
Does not participate
Registered
Activity