В этой рубрике мы публикуем любые сложные и интересные задачи, такие, чтобы даже наши самые матерые читатели (да-да, Иннокентий Сенновский, это про тебя) нашли в них для себя то, над чем можно как следует попотеть. Но особенно мы любим задачи от международных компаний. И это не только потому, что офис Virtuozzo расположен в Сиэтле (и в один прекрасный момент ты сможешь запустить свой трактор в направлении цивилизованного места, где в конце сентября +23 по Цельсию). Международная компания — это еще и новые связи, совсем другой уровень перспектив и возможностей. А поскольку Virtuozzo не так давно отделилась от другой крупной компании — это еще и новые интересные проекты.

 

Задачи от Virtuozzo


Файлы задач расположены на GitHub:
https://github.com/VznutAtem5aXi/xakep
 

Задание 1

У вас есть программа, простой таймер, запускаемая из командной строки. Программа собрана под libc6 x86_64 linux и должна работать в совместимых по архитектуре дистрибутивах Linux.

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

$ ./timer
10

Однако, если два или более экземпляра этой программы будут работать параллельно, второй и последующий процесс выполнятся неуспешно:

$ ./timer (из одного терминала)
10
$ ./timer (одновременно, из другого терминала)
error!

Ваша задача — создать такое runtime-окружение для запуска этой и подобных программ (использующих тот же самый API), чтобы два и более одновременно работающих экземпляра выполнялись без ошибок, не мешая друг другу.

 

Задание 2

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

 

Задание 3

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

Необходимо написать программу-конвертер, которая может автоматически преобразовывать SFX-архивы в RPM-пакет. Предполагается, что SFX-архив будет запускаться в корне файловой системы, а результат установки RPM-пакета должен полностью соответствовать такому запуску, не считая дополнительных изменений rpmdb. Требуется, чтобы сконвертированный пакет содержал уже распакованные файлы, а не сам архив.

В задании приведены два примера SFX-архивов, но программа-конвертер не должна опираться на знание о конкретных форматах архивов.

 

Куда слать ответы?

Правильные ответы принимает Анна Зуева.

 

Награждение победителя

Лучше всех с решением задач от Postgres справился Андрей Асякин. Он крутой, поздравляем победителя! Андрей получает бесплатный билет на все три дня международного форума PgConf.Russia, который Postgres Professional будет проводить 15–17 марта 2017 года в Москве.

 

Ответы на задачи от Postgres Professional

 

Задача 1

select p.*
  from friend f, lateral(select * post p where p.usr_id=f.friend_id order by p.added desc) p
where f.usr_id=:usr_id
order by p.added desc
limit 10

Нам потребуется индекс post(usr_id,added). Запрос «в лоб»:

select *
  from friend f, post p
where f.usr_id=:usr_id
  and p.usr_id=f.friend_id
order by p.added desc
limit 10

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

 

Задача 2

Можно ли в строке, состоящей из символов ( и ), проверить баланс скобок? Как?

Очень просто — сначала превратим строку в таблицу:

 select * from (select s.v[1] as v, pos from regexp_matches(')()()()()(','(.)','g') with ordinality as s(v, pos)) t     where t.v in ('(',')')

после чего для каждой открывающей скобки будем выдавать единицу, а для закрывающей — -1. Обрати внимание на предложение with ordinality — оно позволяет получить, кроме собственно значений, еще и их порядковый номер (в данном случае pos). Вообще говоря, даже без этого предложения мы получим корректный результат, и его использование в данном случае почти буквоедство, но кто знает, как в будущем станут возвращаться строки?

Посчитаем промежуточные суммы для этого выражения:

select sum(case v when '(' then 1 else -1 end)over(order by pos) as r, pos  from tokens order by pos

(tokens — имя таблицы со скобками).

Понятно, что для корректной последовательности скобок, во-первых, число закрывающих скобок должно быть равно числу открывающих и, во-вторых, слева от любой закрывающей скобки число открывающих скобок должно быть не меньше, чем число закрывающих – 1; то есть рассматривается случай ')(' и подобные.
Соберем все вместе:

with tokens as(
    select * from (select s.v[1] as v, pos from regexp_matches(')()()()()(','(.)','g') with ordinality as s(v, pos)) t where t.v in ('(',')')
),
rt as(
        select sum(case v when '(' then 1 else -1 end)over(order by pos) as r, pos  from tokens order by pos
)
    select case when (select rt.r from rt order by pos desc fetch first 1 rows only)=0
                 and not exists(select * from rt where rt.r<0)
                then true
                else false
           end

Кстати, интересное решение предложил один из читателей (из строки предварительно удаляются все символы, отличные от ( и ):

RETURN CASE WHEN EXISTS (
        WITH RECURSIVE a AS (
            SELECT regexp_replace(str, '()', '') rep
            UNION ALL
            SELECT regexp_replace(rep, '()', '') FROM a WHERE rep ~ '()'
        )
        SELECT * FROM a WHERE rep = ''
    ) THEN true ELSE false END;

В нем он удаляет все пары '()' до тех пор, пока они встречаются; если получилась пустая строка, то баланс скобок соблюден.

 

Задача 3

Это происходит в том случае, когда ищут бульдозериста-женщину или нянечку-мужчину. PostgreSQL ведет статистику только по колонкам, а не по парам (тройкам и так далее), отчего рассчитывает, что нужные строки будут получены практически сразу, и потому ошибочно выбирает последовательное сканирование.
Исправить можно просто построением индекса и по occupation, и по sex.

 

Задача 4

При вставке строки в такую схему накладывается блокировка FOR KEY SHARE; она подобна блокировке FOR SHARE, за тем исключением, что блокируются только колонки, входящие в первичный ключ / ограничение уникальности.

 

Задача 5

Для одного запроса — а тут только один запрос — вполне достаточно стандартного уровня изоляции READ COMMITTED. При таком уровне изоляции каждый запрос видит согласованный снимок базы данных; если бы было несколько запросов в транзакции, то уровень изоляции пришлось бы повышать, но так как запрос один, этого не требуется.

 

Задача 6

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

create or replace function tusrupdate(id int, name text) returns void as
$code$
declare
 temp int;
begin
  loop
    begin
        with upd as(
          update tusr tu set name=tusrupdate.name where tu.id=tusrupdate.id returning 1
        ),
        ins as(
          insert into tusr(id,name)
          select tusrupdate.id, tusrupdate.name
          where not exists(select * from upd)
          returning 2
        )
        select 1 into temp from ins;
        exit;
    exception
      when unique_violation then
        continue;
    end;
   end loop;
end;
$code$
language plpgsql

Также можно использовать конструкцию insert ... on conflict(...) do update;. К сожалению, это не всегда срабатывает — при наличии более одного ограничения уникальности (например, primary key и unique) могут также возникать ошибки с нарушением уникальности; впрочем, описанный подход должен работать и в таком случае.

 

Задача 7

Триггер некорректен сразу по нескольким причинам.

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

Во-вторых, если триггер создан как триггер before, то он должен вернуть какое-то значение (обычно new для добавления/обновления строки или null, если операции со строкой требуется пропустить).

Однако нередко возникает задача обеспечить уникальность сразу в нескольких таблицах — например, колонка id должна быть уникальна как в таблице t1, так и в таблице t2. В таком случае можно предложить использовать advisory-блокировки и перед проверкой блокировать значение id, например так:

create or replace function check_uniq() returns trigger as
    $code$
    begin
     if pg_advisory_xact_lock(10000, new.col) then
      if exists (select * from tbl1 t where t.col=new.col) then
        raise exception 'Unique violation';
      end if;
      if exists (select * from tbl2 t where t.col=new.col) then
        raise exception 'Unique violation';
      end if;
     end if;
    end;
    $code$
Language plpgsql

Хотелось бы обратить внимание на то, что используется функция pg_advisory_xact_lock, то есть блокировка будет снята при окончании транзакции и потому нет опасности случайно забыть снять блокировку.

Кроме того, если триггер выше подходит для случая вставки в таблицу, то для обновления его следует модифицировать (примечание: предполагается, что колонка col имеет тип int; значение 10000 в вызове функции pg_advisory_xact_lock взято для примера).

 

Задача 8

Блок выдаст значение ER000, потому что sqlstate, заканчивающийся на 000, определяет не ошибку, а класс ошибок и потому может обрабатывать ошибки и ER001. Кроме того, при возникновении исключения обработчики исключения просматриваются сверху вниз и используется первый подходящий. Конечно, обработка исключений в PL/pgSQL далека, скажем, от Java, но в то же время предоставляет довольно широкие возможности — с ошибкой можно установить многие дополнительные параметры, получить стек вызовов.

Следует также отметить, что с помощью работы с исключительными ситуациями в PL/pgSQL организована работа с точками сохранения (savepoints).

IT-компании, шлите нам свои задачки!

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

Комментарии

Подпишитесь на ][, чтобы участвовать в обсуждении

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

Check Also

Машинное обучение. Разработка на R: тонкости при использовании циклов

Во многих языках программирования циклы являются базовыми строительными блоками, которые и…