Архив за 22 февраля 2014 - 3

… или сказ про то, как пингвин Америку с Японией подружил.

Итак, в стародавние времена люди играли в Sony Playstation и их все устраивало. Но прогресс не стоял на месте. Увеличивалась степень интеграции микросхем. Инженерная мысль постоянно искала новые формфакторы, а мысль маркетинговая — новые рынки сбыта. Так в 2005 году появилась в продаже за пределами Японии портативная игровая система Sony Playstation Portable. Ее игровая линейка (как и у любой другой приставки) представляла собою специально скомпилированные под железо PSP игры. Но также она обладала и достаточными вычислительными мощностями для запуска игр от оригинальной PlayStation через встроенный эмулятор. Хотя, быть может, тут ключевую роль сыграло то, что и у PlayStation, и у PSP стоял процессор одной и той же архитектуры — а именно MIPS. Но самое примечательное в этой системе то, что сразу же, в год запуска, в сеть утекли библиотеки PSP SDK. В результате, через почти 10 лет с момента запуска, мы имеем огромную библиотеку игр и отлаженного homebrew. Также, сейчас, в не самом крупном городе России полностью рабочую PSP (самой функциональной модификации) можно купить с рук за 3000 рублей. Все это делает ее к настоящему моменту очень привлекательной бюджетной игровой системой с просто огромной инсталлбазой. Самая функциональная модификация имеет компонентный выход для подключения к ТВ. Но разъем подключения к ТВ располагается неудачно с точки зрения долгого использования PSP в качестве геймпада. К тому же, при длительном использовании возникает необходимость подключения второго провода — от зарядного устройства. И удобство использования такой химеры стремится к нулю. Как относительно бюджетно и при этом гиково решить эту проблемку — про это и пойдет речь в этой статье. Также вкратце будут затронуты темы программирования драйвера USB-клиента под PSP, методика установки хук-функций в PSP, работа под линуксом с устройствами USB и с джойстиками через API. Мы начинаем.Читать полностью »

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

Время было веселое, это тренировало мозги, характер, стимулировало здоровую конкуренцию.

Потом в институте все как-то перешло в разряд «сдал-не сдал». Отл = Обманул Товарища Лектора и так далее.

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

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

И когда нам предложили ее в регионе провести, мы с радостью согласились.
Читать полностью »

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них , что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.
Читать полностью »