Линейность математического ожидания или Typewriter Monkey

"Абсолютно случайным образом ударяя по 

клавишам пишущей машинки, гипотетическая 

обезьяна рано или поздно напечатает одну 

из пьес Шекспира."

Теорема о бесконечных обезьянах

Вы знаете что такое математическое ожидание? Тогда сегодня я вам предлагаю поразмыслить над следующей задачкой по программированию Typewriter Monkey.

На прошлых выходных я участвовал в конкурсе Google Code Jam и единственная задача, которая не далась мне полностью оказалась задача про обезьян с печатными машинками.

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

В нашем случае ограничения следующие:

index

Read More...

Regular Expressions basics course

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

"Иногда люди сталкиваются с проблемой и думают: "Для решения я использую Регулярные Выражения". Теперь у них две проблемы." (c) история появления фразы

Ключ к решению задач и преодолению страха перед формальными языками (коим является RegExp) – обучение, не так ли? И сегодня я хотел бы поделиться с Вами своим курсом по основам регулярных выражений. 20 кратких слайдов, которые могут изменить (я надеюсь) Ваш подход к поиску информации. Вы не представляете сколько Вы теряете не пользуясь регулярками. Их поддержка встроена во все современные языки программирования, во многие утилиты и консольные приложения. И по сути, если где либо Вы встречаете слово шаблон или маска, то в половине случаев это будет регулярное выражение.

Интересно? Ай-да под кат.

index

Read More...

Regular Expression quiz

Понравился Regular Expression Crossword из предыдущей записи? У меня для Вас хорошая новость – некоторое время назад я составил небольшой опрос-викторину, когда готовил курс по изучению регулярных выражений.

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

Итак, считаете себя несокрушимым ниндзя-экспертом Регулярок? Не уверены, но хотели бы попробовать свои силы? Новичёк, но не знаете с чего начать обучение? Для Вас ниже всего дестяь (10) усложняющихся вопросов на знание различных тем регулярных выражений.

index

Read More...

Regular Crossword

Regular expressions crossword

Отличная идея кроссворда.

Любите головоломки? Знаете регулярные выражения? Тогда время Че настало... Я не пожалел потраченного времени на решение.

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

Для получения читабельного PDF – кликните на картинку.

index

Read More...

Handmade lamp/alarm clock with Android charge

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

В итоге, решил сделать световой будильник с использованием Андроида. В чём суть?

index

Read More...

Influence, Robert Cialdini

В последнее время я стал достаточно много читать и решил поделиться немного с вами. Очередную книгу по психологии мне посоветовал друг. Встречайте: Robert Cialdini, Influence.

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

index

Read More...

Immigration process (search for a work)

"Люди думают, что будут счастливы, если переедут в Париж, а потом оказывается: куда бы ты ни поехал, ты берёшь с собой себя." (с)овершенно точно.

Сегодня мы поговорим о вопросах поиска работы за пределами родной страны. Данный пост по сути родился из моего опыта и всё учащающихся вопросах о процессе иммиграции. Хочется начать рассказ с самого начала: с поиска работы, ибо только подписанный контракт на сегодняшний день - залог долгосрочной визы. Речь, естественно об IT.

Данный пост почему-то захотелось оформить в стиле поучительного TO-DO списка. Итак, поехали:

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

1. Страна или страны. Этот выбор стоит сделать на достаточно раннем этапе.

1.1. Изучи иммиграционное законодательство целевой страны. Обычно достаточно изучить материалы на сайтах посольств или консульств. Там есть большинство документов и описанных процессов.

1.2. Узнай какие типы виз тебе подходят. В некоторых странах действуют программы для "Highly Skilled Immigrants", по которым тебе вообще не нужен рабочий контракт, для получения визы. Достаточно соответствовать некому набору критериев. (Большинство таких программ, к сожалению, закрылись или в процессе закрытия)

1.3. Изучи рынок. Узнай какие вакансии преимущественно попадают на IT рынок данной страны, какие у них зарплаты. Здесь сильно помогают monster.com и glassdoor.com

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

2. Вылижи резюме.

2.1. Резюме должно быть на английском, а не на его подобии.

2.2. Вот собственно: CV style. Мои взгляды особо не поменялись :)

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

2.4. Ну и наконец, используй PDF :) Хотя лучше иметь заготовки в разных форматах.

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

3.1. Составь список компаний, которые работают в данной стране. Выписывай и крупные, и маленькие. Можно искать через тот же Monster например, но одного источника мало. Многие крупные компании вообще не работают через агенства - о их вакансиях можно узнать только у них на сайте.

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

3.3. Будь готов, что если кто-то заинтересуется - будут звонить. Телефонный контакт для HR очень важен: он более надёжен + позволяет хоть немного оценить адекватность и наличие языка. Если можешь говорить только в определённое время - укажи это в резюме.

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

3.5. Если какая-то компания нравится больше всего, через день после отсылки резюме перезвони и уточни получили ли они твоё письмо.

4. Ну и BodyShop

4.1. Такие фирмы, как Епам, Люксофт и множество других перевозят людей. Они получают процент от твоей з/п в итоге. Этот вариант стоит рассматривать в самый последний момент, ибо условия работы зачастую пониже будут + есть свои нюансы. Из позитивных моментов - компания берёт на себя всё оформление.

5. Немного психологии.

5.1. Будь готов, что многие не отвечают вообще.

5.2. Пойми, что процесс может быть очень длительным.

5.3. Если кто-то пригласил на собеседование, это еще не победа. Иногда надо пройти 6-8 собеседований в одной и той же компании, чтобы устроится на работу.

P.S. Если кто-то не в курсе про источник картинки: Поросёнок Петя

index

Read More...

PostgreSQL. Redirect data to child partition.

На одном из недавно "вверенных" проектов жил поживал PostgreSQL с настроенным разбиением данных по таблицам-разделам в зависимости от значений (т.н. Partitioning). Особенности работы с БД были таковы, что раз в сутки в таблицы "вливалось" достаточно большое кол-во данных (десятки миллионов строк) и до следующего "вливания" база работала только на отдачу данных.

Проблема, а точнее даже не проблема, а пожелание заключалось в следующем: ПО, которое занималось подготовкой, фильтрацией и, собственно заливкой данных, занималось еще и тем, что вычисляло тот самый, нужный раздел (child table), в который данные нужно сложить. Это приводило к:

• невозможности менять условия разбиения данных достаточно гибко (изменения должны быть синхронизированы на стороне БД и кода);
• иногда в разделы попадали некорректные данные, так как заливка данных осуществлялась пакетно, с помощью операции COPY и нужный раздел определялся для всего пакета один;
• необходимо было заранее создавать таблицы разделов.

Решение, приведенное ниже - не панацея, но кому-то может пригодиться:

Первым делом был создан триггер, который вешался на мастер таблицу:


CREATE TRIGGER redirect_to_child
  BEFORE INSERT ON parent
  FOR EACH ROW
  EXECUTE PROCEDURE redirect_to_child();


Затем, экспериментируя с процедурой redirect_to_child() выяснилось, что на стандартном PlPgsql написать достаточно гибкую функцию, которая бы перенаправляла данные в нужный раздел не получается, так как на этапе запуска функции не известно название таблицы, в которую нужно вставлять данные. Таким образом приходиться использовать EXECUTE для формирования динамического SQL, но это не решает всех проблем, так как теперь нельзя использовать NEW.*, потому что полученный SQL выполняется вне контекста триггерной функции и соответственно не видит структуры NEW.

В PostgreSQL 8.4 появилось ключевое слово USING, которое позволяет обойти проблему с использованием NEW.*, но скорость работы данного триггера оставляла желать лучшего.

В результате всех экспериментов родился небольшой велосипедик на PlPython, который сам создаёт нужные таблички и перенаправляет вставку данных. Нижеприведенный кусочек кода, решает все задачи, описанные в начале статьи, а по времени работает всего около 5-ти раз медленнее "чистой" вставки, что для моих условий было более чем приемлемо. Собственно код:


CREATE OR REPLACE FUNCTION redirect_to_child()
RETURNS trigger AS
$BODY$
  import datetime

  # TD['new'] -> inserted data
  new_data = TD['new']
  values = new_data.values()

  date_occured = new_data['occured'].split()[0]
  s_year, s_month = date_occured.split('-')[:2]

  # TD['table_name'] -> table name, that triggered this function.
  parent_table_name = TD['table_name']
  # Child table name pattern is <parent_table>_<year>_<month>.
  child_table_name = '_'.join([parent_table_name, s_year, s_month])

  try:
    insert_plan = SD[child_table_name]
  except KeyError:
    # Check whether child table exists.
    child_table_result = plpy.execute(("SELECT * FROM information_schema.tables"
                      " WHERE table_catalog = CURRENT_CATALOG"
                      " AND table_schema = CURRENT_SCHEMA"
                      " AND table_name = '%s'") % (child_table_name, ))

    if child_table_result.nrows() == 0 :
      # Need to create child table
      year = int(s_year)
      month = int(s_month)

      min_range_date = datetime.date(year, month, 1)
      max_range_date = datetime.date(year + ((month + 1) / 12), (month + 1) % 12, 1)

      create_sql = ("CREATE TABLE %(child)s ("
              " id BIGINT DEFAULT nextval('%(parent)s_id_seq'::text) PRIMARY KEY,"
              " CHECK ( occured >= DATE '%(min)s' AND occured < DATE '%(max)s' )"
              ") INHERITS (%(parent)s);") \
              % {'parent': parent_table_name,
                'child':child_table_name,
                'min':min_range_date.isoformat(),
                'max':max_range_date.isoformat() }
      plpy.execute( create_sql )
      plpy.execute( "ALTER TABLE %s OWNER TO tableowner;" % child_table_name )

    # Prepare insertion plan.
    questions_marks = ','.join(['$%d' % x for x in xrange(1, len(new_data) + 1)])


    col_types = plpy.execute( ("SELECT column_name, data_type"
                  " FROM information_schema.columns"
                  " WHERE table_catalog = CURRENT_CATALOG"
                  " AND table_schema = CURRENT_SCHEMA"
                  " AND table_name = '%s'"
                  " AND column_name <> 'id';")
                  % parent_table_name );

    type_hash = dict((column["column_name"], column["data_type"])
         for column in col_types)

    column_names = new_data.keys();
    types = [type_hash[k] for k in column_names]

    insert_sql = ("INSERT INTO %s (%s) VALUES (%s);" %
         (child_table_name,
         ', '.join(column_names),
         questions_marks))
    insert_plan = plpy.prepare(insert_sql, types)

    # Cache insertion plan for reuse in the same transaction.
    SD[child_table_name] = insert_plan

  # Insert data to child table
  plpy.execute( insert_plan, values )

  # Skip insertion to parent table
  return "SKIP";
$BODY$
LANGUAGE 'plpythonu';

ALTER FUNCTION redirect_to_child() OWNER TO tableowner;

index

Read More...

Blogspot expandable posts

Давно я не писал сюда. Сегодня решил исправится и первым делом настроил себе красивый скрипт для длинных статей.

Встречайте:

Ссылка "Read more" появляется только в тех статьях, которые действительно этого заслуживают (и где я собственноручно проставил нужный тег). Работает всё предельно просто, код взят отсюда. Правда пришлось самую малость допилить.

index

Read More...

Видео прокси для вещания в локальной сети

В период чемпионата мира по футболу очень хотелось следить за ходом матчей в живую, да вот беда - работа. Решение казалось бы банально - on-line видео трансляции, но не я один такой заинтересованный оказался. А при 30-40 одновременных потоках входящий Интернет канал оставляет остальным сотрудникам офиса лишь маленькую надежду на закачку чего бы то ни было.
Очень быстро родилась идея организовать видео прокси, которое бы принимало on-line трансляцию и раздавало видео поток в сети. Локальный трафик не так значим, как входящий интернет трафик, потому приступил к реализации. Выбор пал на VLC media player, который сначала показался несколько монстроидальным, но в дальнейшем оправдал все надежды.

Итак, что такое VLC player? Это open-source программный комплекс, позволяющий творить с видео чудеса. В плейере уже находиться масса возможностей, фактически плейер может одновременно выступать и сервером и клиентом. В поставку входят интерфейсы для удалённого управления (telnet, http), так что можем смело ставить vlc на консольную виртуальную машину (здесь и далее все команды приводятся для Ubuntu):
sudo aptitude install vlc vlc-plugin-*

Далее запускаем VLC с активным http интерфейсом удалённого управления:
vlc -vvv -I http --http-host 10.1.6.3:8181

, здесь

• -vvv - verbose опция (количество букв v отображает уровень логов)
• -I - включает один из интерфейсов удалённого управления (здесь http)
  
• --http-host - задаёт имя (ip) которое пользователь должен ввести, чтобы попасть в админ часть и порт, который будет слушать встроенный сервер
  

Заходим по адресу и видим:
В принципе данного интерфейса хватает для экспериментов. Для лучшей наглядности лучше сразу же нажать кнопочку "Help".

Первым делом, я нажал кнопку "Open", ввёл адрес сервера (для экспериментов было выбрано футбольное on-line вещание ICTV) и... И насладился цветной картинкой ASCII видео в консоли удалённого сервера. Поборов восхищение и отключив видео - нашел в http интерфейсе кнопку "Stream output", которая и привела меня к победе. Догадался одновременно заполнить обе секции перед нажатием кнопки "Play":

• в Input (Open кнопка) адрес вещания в интернете.
  
• в Stream output выбрал http, ввёл адрес (всё тот же 10.1.6.3), указал порт (на этот раз 8080, чтобы не пересекаться с админкой) и отметил тип кодирования "MPEG TS"

Подключившись локальным VLC player'ом к адресу http://10.1.6.3:8080/ получил звук и картинку ICTV. Казалось бы вот он успех, но всё не закончилось так быстро. После нескольких переподключений локальным плейером оказалось, что в половине случаев видео даже не пытается стартануть, зато звук передаётся отлично. После танцев с бубном вокруг логов проблема решилась дополнительной отметкой "Video Codec" в "mp2v" и 1024 kb/s. Эта опция перекодирует видео на лету в выбранный формат.

И на последок консольный вариант запуска:
vlc -vvv -I http --http-host 10.1.6.3:8181 http://<internet.on-line.video.url> -sout "#transcode{vcodec=mp2v,vb=1024,scale=1}:std{access=http,mux=ts,dst=10.1.6.3:8080}"

index

Read More...