Архив метки: Программирование

Про нелогичные API

Не могу сказать, что у меня огромный опыт интеграции с внешними службами, но несколько геоинформационных сервисов и соцсетей за этот год я подключил. Мне даже начало казаться, что общедоступное API сначала хорошо продумывают и только потом открывают для всех. Я бы пребывал в счастливом неведении и дальше, но, к сожалению, сверху пришла задача подключиться к Яндекс.Деньгам.
Общая идея довольно простая: я на своей стороне формирую XML-запрос, отправляю его на указанный адрес, и получаю XML-ответ. Проблема в требованиях, которым этот XML-запрос должен удовлетворять:

  • Серия и номер паспорта должны передоваться как одно целое число(!). Возможно, сотрудники Яндекс.Денег видят от этого какую-то пользу (быстрые запросы, например), но как я по мне, это просто идеологически неверно. Но, что гораздо хуже, в России до сих пор можно встретить людей с паспортом СССР, а там в серии могут присутствовать буквы.
  • Дата выдачи паспорта разбита на три числовых поля docIssueYear, docIssueMonth и docIssueDay — год, месяц и день выдачи. Опять же оставим в стороне тот факт, что это идеологически неверно, лучше посмотрим на то, как передаются другие даты. День рождения должен передаться одним текстовым полем в формате ДД.ММ.ГГГГ, а время передачи запроса опять же текстом, но уже в формате ГГГГ-ММ-ДДTЧЧ:ММ:СС.000Z
  • Под место рождения (а там чаще всего указывается только город) отдаётся целых 100 символов, а вот под город проживания только 30. Жителям крупных городов повезло, а вот как быть тем, кому приходится указывать область или район и только потом название села?
  • Вместо названия страны надо передать код «643». Причём, если я правильно понимаю, других кодов просто нет.
  • Всего 100 символов на адрес регистрации. Большинство адресов в этот лимит попадают, но ведь живут же люди и по адресу: Ханты-Мансийский Автономный округ — Югра, Нефтеюганский р-н, пгт Пойковский, Центральная ул., д xx стр xx, кв. xx! Им-то как быть?

К чему я это всё? Не делайте так!
А к Яндекс.Деньгам мы всё же подключились.

Монография по цифровой обработке изображений

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

Про задачи с собеседований…

Столкнулся я недавно с одной задачей на собеседовании:

Дано множество упорядоченных по какому-то критерию элементов, состоящих из двух полей: целочисленный ключ (key) и вещественное значение (data). В процессе работы на вход программы много раз подаются пары чисел L,R . Требуется находить среднее арифметическое элементов, лежащих в массиве между индексами L и R. Вопрос состоит в том, как эффективнее хранить данные: как массив записей или как запись, состоящую из двух массивов.

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

Посмотрим, что мы считываем при каждом из возможных подходов. Если мы храним данные как массив записей, то и считаны будут записи, то есть пары ключ-значение. Учитывая, что для вычислений нам необходимы только вещественные значения, получается, что существенный объём данных (все key) считывается впустую. Если же мы храним данные о ключах в одном массиве, а о значениях в другом, то при обращении к памяти будут считаны только необходимые нам вещественные переменные. Очевидно, что во втором случае обращений к памяти будет меньше.

Именно такого ответа ждали на собеседовании, но я решил проверить насколько в действительности велик выигрыш от такого расположения в памяти. Были написаны тестовые программы, которые показали, что вторая версия (запись массивов) примерно на 7% процентов быстрее.

Результат неплохой, но я сам всегда считал и ученикам говорил, что правильный алгоритм гораздо эффективней всяких ухищрений вроде рассмотренных выше. Существует так называемое интегральное представление массива, когда i-ый элемент интегрального массива равен сумме всех предшествующих элементов оригинального массива. Например, массив A=[1,2,3,4,5] в интегральном виде выглядит так: I=[1,3,6,10,15]. Интегральное представление можно получить за O(N), где N — размер исходного массива. Главное достоинство такого представления — возможность за константное время вычислить сумму элементов любого непрерывного подмассива. Пусть надо найти сумму элементов с L по R, она вычисляется за константное время как I[R]-I[L-1] (при этом будем считать I[0]=0).Этот подход оказался в десятки раз быстрее(!), чем любой из рассмотренных ранее.

Собственно мораль здесь проста — правильные алгоритмы и структуры данных всегда эффективнее любых низкоуровневых трюков.

Про github.com и лабораторные работы

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

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

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

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

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

Приложение github (без репозиториев)

Приложение github (без репозиториев)

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

Приложение github (создание репозитория)

Приложение github (создание репозитория)

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

Приложение github (публикация репозитория)

Приложение github (публикация репозитория)

Перед публикацией репозитория необходимо создать новый коммит. Для этого надо задать название коммита (на рисунке текстовое поле Summury) и его описание (Description). Обычно первый коммит называют «Initial commit», хотя это и необязательно. После того, как поля заполнены, необходимо нажать кнопку «Commit to master». И в завершении публикации необходимо нажать кнопку «Publish Repository». На этом всё, проект опубликован и выложен на github.

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

О работе (хорошей и плохой)

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

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

Первый мой опыт работы по специальности — стажировка в Parallels. Именно там я впервые познакомился с техникой Apple, но сегодня рассказ не об этом. Именно в Parallels я узнал, зачем функциям возвращать *void, а также, что значит страшный #define for if (false) {} else for. Проще говоря, за пару летних месяцев я узнал о программировании на C/C++ больше, чем за пару семестров в институте. Кстати, именно после этой стажировки я окончательно убедился в том, что программирование  на C/C++ не для меня, мне гораздо ближе более «академические» языки.

После Parallels я практически не работал программистом, если не считать разовых (хотя и весьма прибыльных) заказов. Все мои усилия были направлены на учёбу в институте. Эти несколько лет позволили мне понять в чём разница между «программистом» на <ваш любимый язык> и программистом, знающим алгоритмы и структуры данных.

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

SELECT *
FROM Table1
WHERE (1=2)

А у вас какие интересные случаи связаны с работой?