Аббревиатура на все случаи жизни

В одной из последних лекций на образовательном ресурсе Coursera проф. Тим Рафгарден поведал о любопытном факте. Когда математики и программисты второй половины XX века думали о том, как назвать те задачи, которые мы привыкли именовать NP-полными, среди прочих был предложен следующий вариант - английская аббревиатура PET. Вариант, как видим, не прижился, однако достоин упоминания вследствие лингвистической находчивости авторов.

В чем же эта находчивость проявляется?
Как известно, доказательство неравенства классов P и NP еще не получено, и поэтому нельзя аргументированно заявлять о том, что эти задачи можно решить только экспоненциально. Поэтому PET можно расшифровать как "probably exponential time".

Но прогресс не стоит на месте и когда-нибудь это доказательство может быть получено. Тогда аббревиатура останется прежней, поменяется лишь расшифровка - "provably exponential time". Теперь давайте представим что дед мороз существует и P = NP. И даже в этом случае аббревиатуру не пришлось бы менять - задачи стали бы называть "previously exponential time".

Привычный  нам термин NP-сomplete, впрочем, тоже не является уязвимым к разным разгадкам этой мировой загадки.

Декларативное и императивное программирование

Вступление
Допустим, наше приложение тем или иным образом хранит информацию о странах и городах мира. Предположим, что нам нужно вывести все города, начинающиеся на букву "V", расположенные в странах, которые начинаются на "R". Представим, что программа написана на Java без использования СУБД, и данные хранятся в обыкновенных коллекциях. Тогда код получения требуемых городов может иметь вид:

for(Country country : countryList){
            if(country.getName().startsWith("R"))
                for(City city:country.getCityList())
                    if(city.getName().startsWith("V")){
                        //что-то делаем с городом
                    }
        }

Теперь пусть приложение использует СУБД, к примеру, Oracle. Теперь данные можно извлечь посредством простого запроса:

select ctr.name country_name, c.name city_name, c.city_id
            from countries ctr, cities c
        where 1=1
              and c.country_id = ctr.country_id
              and ctr.name like 'R%'
              and c.name like 'V%'

Чем отличаются эти два способа извлечения данных? Помимо синтаксических отличий есть одно очень важное разграничение. В первом случае мы задаем инструкции, пошаговое выполнение которых приводит к извлечению нужных данных, а во втором - описываем данные, которые хотим получить, предоставляя СУБД возможность решить самостоятельно, каким способом эти данные извлечь. Первый подход называется императивным, а второй - декларативным. Рассмотрим эти понятия более подробно

Немного о временных таблицах

В арсенале СУБД Oracle имеется такое средство как временные таблицы. Вопреки первоначальному предположению, которое может возникнуть при встрече этого термина, такие таблицы создаются один раз и существуют в базе постоянно, а временный характер носят данные, находящиеся в этих таблицах.

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

Привыкнув к такому положению вещей, очень легко упустить одну важную деталь.

Something About CASE, NVL And DECODE

Sometimes the programming language constructions which seem to be well known and usual, can behave in odd way. Here is the PL/SQL function for the simpliest example of the situation:

create or replace function get_number_five
return number
is
begin
  dbms_output.put_line('function get_number_five is invoked');
  return 5;
end;

As we can see, this function just returns the number 5 and outputs some string to standard buffer. So, here is an example of function which not only returns the result, but also performs some action, in other words it has some side effect. We need this quality to trace the function executons.

Let's try to guess the result of the following code:

declare
 x number;
 p number;
begin
  p :=5;
  x := nvl(p,get_number_five);
end;

Немного о case, nvl и decode

Иногда конструкции языка, кажущиеся знакомыми и вполне обычными, могут вести себя несколько неожиданно. Рассмотрим в качестве простейшего примера следующую функцию на PL/SQL:

create or replace function get_number_five
return number
is
begin
  dbms_output.put_line('function get_number_five is invoked');
  return 5;
end;

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

Попытаемся угадать, что произойдет при следующем вызове:

declare
 x number;
 p number;
begin
  p :=5;
  x := nvl(p,get_number_five);
end;

Немного об автономных транзакциях в Oracle

Вступление.
Многие, кому приходилось работать с Oracle RDBMS, сталкивались с автономными транзакциями, которые можно использовать для обеспечения дополнительной гибкости в пакетах на PL/SQL. Если кратко, то этот механизм позволяет в любой месте выполняемого кода начать транзакцию, независимую от текущей.

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


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

Лиха беда начало

Сегодня первый раз принял участие в матче системы TopCoder - SRM 517.

Чтобы было понятно, о чем идет речь,  поясню для тех, кто не знает - на ТопКодере программисты меряются своими талантами. Периодически проводятся SRM (Single Round Match), в ходе которых конкурсантам предлагаются три задачи. Все участники разделены на два дивизиона - в первый дивизион входят те, у кого рейтинг начинается с 1200, а во второй - все остальные, включая новичков. Этот рейтинг рассчитывается по хитрой формуле относительно результатов всех остальных участников, что и создает соревновательный момент.


В первом и втором дивизионе предлагаются задачи разного уровня сложности(в первом сложнее). За первую задачу максимальное количество баллов - 250, за вторую - 500, за третью тысяча. Максимум этот является недостижимым, так как итоговый балл нелинейно зависит от времени решения. Проще говоря,чем быстрее решена задача - тем ближе к максимуму будет балл.

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

Второе мое удивление было вызвано тем, что с единственной решенной задачей мой рейтинг стал равен 1295, что влечет попадание в первый дивизион.

То есть историю изменения ощущений можно выразить так
1. The Coding Phase. Чего уж говорить, облажался...
2. The System-Testing Phase. Хм, а не так уж и облажался вроде.
3. Осмысление сути бытия. Надо бы к следующему участию подготовиться получше :)