Олимпиадные задачи.

[PAV]

ewert в сообщении #343128 писал(а):

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

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

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

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

Чтобы не быть голословным, я провел несколько простых экспериментов. Было создано два массива из ста миллионов чисел, заполненные случайно нулями и единицами. Основная процедура подсчитывала количество позиций, в которых в первом массиве стояла 1, а во втором - 0.

Первая реализация, самая примитивная:

Используется синтаксис C

int sum = 0;
for(int i = 0; i < N; ++i, ++p1, ++p2)
{
    if( p1[0] != 0 && p2[0] == 0 )
        ++sum;
}
 

Не считая затрат на организацию цикла (включая проверку условия выхода) и инкремент sum, которые будут одинаковы во всех реализациях, мы имеем в теле цикла два if'а и две проверки на равенство и неравенство нулю. Один if написан явно, второй же возникает неявно в соответствии с правилами Си по вычислению логических операторов: после вычисления первого условия делается проверка и в случае, когда оно неверно, второе не вычисляется.
Данная реализация занимала примерно 500 миллисекунд времени.

(Замечу, что также ради небольшой потенциальной экономии я инкрементирую указатели на элементы массивов, вместо того, чтобы обращаться к ним по произвольному индексу p1[i] и p2[i]).

Вторая реализация (промежуточная): воспользуемся арифметикой и избавимся от неявного ифа. Разумеется, этот подход работает только потому, что у нас по условию значения могут быть только 0 или 1:

Используется синтаксис C

int sum = 0;
for(int i = 0; i < N; ++i, ++p1, ++p2)
{
    if( p1[0] * (1 - p2[0]) != 0 )
        ++sum;
}
 

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

Разумеется, совершенно понятно, что if тут вообще не по делу, так как проверяемое выражение принимает значения только 0 или 1. Отсюда третья реализация:

Используется синтаксис C

int sum = 0;
for(int i = 0; i < N; ++i, ++p1, ++p2)
{
    sum += p1[0] * (1 - p2[0]);
}
 

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

Но и это еще не все. Можно применить еще один важный метод ускорения - массовые операции. Фактически ведь мы работаем с битами, поэтому можем упаковывать их в группы и применять побитовые операции, которые выполняются еще быстрее, чем арифметические. Итак, заводим массивы в 8 раз меньше, чем исходные, и в каждый байт нового массива будем класть по 8 исходных значений. Сохранение значения x, имеющего исходный индекс i, в элемент нового массива arr, производится операцией:

arr[i/8] |= x<<(i%8)

Еще нам потребуется определять количество единичных бит в байте. Это удобнее всего делать по таблице: заранее заготовить соответствующий массив значений длины 256. Обозначим его Table. Реализация при этом выглядит так (n - это одна восьмая от количества чисел в исходном массиве):

Используется синтаксис C

int sum = 0;
for(int i = 0; i < n; ++i, ++p1, ++p2)
{
    sum += Table[p1[0] & (~p2[0])];
}
 

Заметим, что этот подход требует в 8 раз меньше памяти под хранение данных. Время работы - 16 миллисекунд. Ускорение по сравнению с исходным примитивным вариантом - более чем в 30 раз.

[ewert]

Да я и не спорю насчёт оптимизации по времени. Я говорил о прямо противоположном: очень часто эта оптимизация не имеет практически никакого значения, в то время как читабельность -- полезна всегда, и тогда задумываться об оптимизации -- попросту вредно.

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

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

[lim0n]

ewert в сообщении #343186 писал(а):

... мы обходим всю доску, а это -- $n^2$ действий.

Вот вы о чём...
Я под $n$ понимал количество выпиленных клеток.

Спасибо, PAV, за оживление темы. Иногда хочется подурачиться.

[PAV]

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

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

То, что задача простая, служит дополнительным аргументом в пользу разумности постановки. Ведь подобные ухищрения нужно применять в процедурах, применяемых во внутренних циклах, а они всегда простые. В моем примере ведь по сути речь идет о том, как реализовать задачу: дано два двоичных числа, нужно увеличить счетчик переменной в случае, если первое равно 1, а второе 0. Казалось бы, какие тут могут быть сложности, ведь речь об одной строке кода. Но оказывается, что в зависимости от того, как написать эту строку, быстродействие содержательной процедуры, в которой она используется, может увеличиться на порядок.

Математиков этому не особо учат, я сам почти ничего не знал (как потом понял), пока не стал решать реальные задачи, а точнее - пока не стал общаться с теми, кто их уже давно решает. Классические курсы программирования и Computer Science увлекаются, например, оценками сложности алгоритмов через число операций. Многие студенты не понимают, что асимптотическое поведение числа операций от размера входа - это одно, а быстродействие реальной процедуры - это другое. Кто-то во внутреннем цикле уменьшит число умножений с 20 до трех, и будет считать, что сейчас у него все ускорится. А на if'ы вообще не обращает внимания, и потом удивляется, почему все стало работать вообще с черепашьей скоростью. Также можно написать несколько строк кода так, что нормальный компилятор сам все замечательно ускорит при оптимизации, а можно написать так, что он не сможет применить свои оптимизационные алгоритмы, потому что не сможет быть уверен, что это безопасно.

Вполне возможно, что кто-то ждет часами или сутками результаты своих численных математических расчетов, не понимая, что изменив пару строк, это, возможно, получится ускорить в разы. Так что постановка разумная.

[ewert]

lim0n в сообщении #343260 писал(а):

Я под $n$ понимал количество выпиленных клеток.

А вот этого я уже совершенно не понимаю. Т.е. то, что я не понимаю алгоритм (ввиду его непрозрачности и моей тупости, конечно) -- это дело десятое. Но. Вам же всё равно приходится инициализировать всю доску. А это -- уже эн-квадрат. (ну мой эн, а не Ваш, конечно)

[Maslov]

ewert в сообщении #343230 писал(а):

Да я и не спорю насчёт оптимизации по времени. Я говорил о прямо противоположном: очень часто эта оптимизация не имеет практически никакого значения, в то время как читабельность -- полезна всегда, и тогда задумываться об оптимизации -- попросту вредно.

ewert в сообщении #343230 писал(а):

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

На мой взгляд, имеет смысл разделять практическое и учебное программирование. В практическом программированиии есть расхожая фраза: "Premature optimization is the root of all evil". Другими словами, прежде чем заниматься низкоуровневой оптимизацией, надо получить работающую программу. И только потом, если возникнет необходимость, начинать её "улучшать". В большинстве случаев, по моему опыту, необходимость не возникает .

Учебные же задачи, в силу их простоты, можно попробовать порешать разными способами, посравнивать производительность и вообще покрутить их так и этак. Причём важно именно посравнивать различные варианты, чтобы понимать, за счёт каких модификаций какого изменения эффективности можно достичь. Полезно это хотя бы для того, чтобы когда в 1% практических случаев все-таки возникнет необходимость низкоуровневой оптимизации, понятно было, с какого конца за неё браться и на что в первую очередь смотреть.

Другими словами, я согласен с PAV в том, что всякие дополнительные условия могут быть весьма полезны при обучении.

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

[ewert]

Maslov в сообщении #343311 писал(а):

Поэтому оптимизация структуры -- это задача, которая в полный рост встаёт с самого начала работы над программой.

Это -- смотря по тому, насколько коммерческая задача или, наоборот, наколенная. Вот у меня с неделю назад стал вопрос: перевести данные из Excel'евской таблички в матлабовский формат. Выбросив из неё незначащие поля, согласовав даты поступления в текстовом формате по разным листам (и проверив корректность этих дат -- в частности, их согласованность с указанными там же днями недели, они тоже значимы), вставив недостающие в тех табличках дни с соотв. заглушками по данным, сцепив разные листы с учётом того, что в них, вообще говоря, указаны разные потребители (в Excel'е есть ненужное ограничение на к-во столбцов, в данном случае по датам, почему и приходится сцеплять данные из разных листов), ну и т.д.

Ну и что ж, для всей этой наколенной деятельности я буду глубоко и всесторонне продумывать структуру программы?... Щас.

[PAV]

Что же касается собственно исходной задачи, то сам алгоритм я предполагал ровно такой, какой написал ewert: для каждой вырезанной клетки посчитать среди ее четырех соседей количество невырезанных. А реализацию без циклов и условных переходов видел примерно такой. Хранить состояние доски в виде битовых полей. Применять массовые операции. Для этого нужно отдельно иметь развертку доски по горизонтали и вертикали. Простейший метод - хранить в виде двух массивов отдельно строки и столбцы:

unsigned char row[8];
unsigned char col[8];

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

А с 64-битными (которые в майкрософтском компиляторе __int64) получится так. Нам их нужно два - один по строкам, второй по столбцам:

__int64 a=0, b=0;

Заполнение: для того, чтобы пометить клетку с координатами x,y (0-7) как вырезанную, нужны две строки:

a |= 1LL << (8*x+y);
b |= 1LL << (8*y+x);

где 1LL - это __int64, равный 1.
Собственно вычисление всего занимает 4 строки:

__int64 r1 = a & ~(a<<8);
__int64 r2 = a & ~(a>>8);
__int64 r3 = b & ~(b<<8);
__int64 r4 = b & ~(b>>8);

Осталось посчитать количество единичных битов во всех 4-х переменных ri. Это можно сделать с помощью таблицы, как и в моем примере, непосредственно прописав все операторы:

int sum = Table[r1 & 255] + Table[(r1>>8) & 255] + Table[(r1>>16) & 255] ...

и так далее. Всего 32 слагаемых, по 8 на каждое число.
Вот примерно так можно сделать.

[ewert]

(Оффтоп)

PAV в сообщении #343315 писал(а):

Вот примерно так можно сделать.

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

Впрочем, прошу прощения за лирику.

[PAV]

(Оффтоп)

Так я с этого и начал.

PAV в сообщении #342875 писал(а):

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

Расширения пошли после этого, чтобы стало хоть немного интереснее.

[Circiter]

2lim0n

Цитата:

Здорово! Но как это реализовать? "Код в студию".

Я попробовал реализовать предложенный алгоритм на C, вот набросок (необходима предварительная сортировка данных, зато память константная):

Используется синтаксис C

#include <stdio.h>
#include <stdlib.h>

typedef struct {int Top, Left, Right;} Row;

int BoardSize=0, PolygonArea=0, LatticePoints=0;

Row CurrentRow={0}, PreviousRow={0};

int max(int Value1, int Value2) {return Value1>Value2?Value1:Value2;}
int min(int Value1, int Value2) {return Value1<Value2?Value1:Value2;}

int InRange(int Value, int LowerBound, int UpperBound)
{
    int Result=Value>=LowerBound && Value<=UpperBound;
    if(!Result) fprintf(stderr, "Not in range.\n");
    return Result;
}

int ProcessRow()
{
    if(!PreviousRow.Top) return 1;

    /* Count the "overlapped" cells in two adjacent rows. */
    /* FIXME: Try to eliminate conditional branching. */
    int Overlapped=
        min(PreviousRow.Right, CurrentRow.Right)-
        max(PreviousRow.Left, CurrentRow.Left);

    if(Overlapped<0)
    {
        fprintf(stderr, "Polygon isn't simply-connected set.\n");
        return 0;
    }

    /* TODO: Add holes detection. */

    /* Update the total number of integral points. */
    LatticePoints+=Overlapped;

    return 1;
}

int ProcessCell(int Row, int Column)
{
    if(!InRange(Row, 1, BoardSize)||
        !InRange(Column, 1, BoardSize)) return 0;

    /* When a new row arrived... */
    if(CurrentRow.Top && Row!=CurrentRow.Top)
                                                                                                        {
        if(Row!=CurrentRow.Top+1)
        {
            fprintf(stderr, "Data is unsorted.\n");
            return 0;
        }

        if(!ProcessRow()) return 0;

        PreviousRow=CurrentRow;
        CurrentRow.Left=CurrentRow.Right=0;
    }

    CurrentRow.Top=Row;

    /* Adjust the current row. */
    if(!CurrentRow.Left || Column<CurrentRow.Left)
        CurrentRow.Left=Column;
    if(!CurrentRow.Right || Column>CurrentRow.Right)
        CurrentRow.Right=Column;

    return 1;
}

/*
** Finds the perimeter of our polygon
** using well-known Pick's theorem.
*/
int Perimeter()
{
    return 2*(PolygonArea-LatticePoints+1);
}

int main(int ArgumentsCount, char *Arguments[])
{
    int i, Row, Column;
    char Buffer[100];

    if(ArgumentsCount==2) BoardSize=atoi(Arguments[1]);
    if(!BoardSize)
    {
        fprintf(stderr, "Size of the chessboard is assumed to be 8.\n");
        BoardSize=8;
    }

    gets(Buffer);
    sscanf(Buffer, "%d", &PolygonArea);
    if(!InRange(PolygonArea, 1, BoardSize*BoardSize)) return 1;

    for(i=PolygonArea; i; --i)
    {
        if(feof(stdin))
        {
            fprintf(stderr, "Unexpected EOF.\n");
            return 1;
        }

        gets(Buffer);
        Row=Column=0;
        sscanf(Buffer, "%d %d", &Row, &Column);

        if(!ProcessCell(Row, Column)) return 1;
    }

    if(!ProcessRow()) return 1; /* It's necessary. */

    printf("%d", Perimeter());

    return 0;
}
 

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

2PAV
Кстати о сортировке (вообще о сортировке, к моему алгоритму это не относится). Я так понимаю, слишком на if'ах в этом случае не поэкономишь?

-- Пн авг 09, 2010 08:49:10 --

Хотя нет, можно конечно и без if'ов. Например, если нейросетью сортировать. :)

[ewert]

Ещё один примитивный вариант:

leng:=4*width;

for i:=1 to n do begin
  next:=0;
  if (t[i].r=1) or (t[i].r=width)   then inc(next);
  if (t[i].c=1) or (t[i].c=width)   then inc(next);
  ninn:=0;
  for k:=1 to n do
    if (abs(t[i].c-t[k].c)=1) or (abs(t[i].r-t[k].r)=1)   then inc(ninn);
  inc(leng, 4-ninn-2*next);
end;

Работает медленно (если вырезано много клеток): $O(N^2)$, но зато не требует дополнительной памяти. Если массив вырезанных упорядочен и по строкам, и по столбцам, то можно ускорить до типа $O(N\sqrt N)$, но усложнится логика.

[Circiter]

2ewert
Ну краткость записи я оценил. :) Но ваш fortran-like стиль не позволяет мне понять стоящую за алгоритмом идею... Не могли бы вы в нескольких словах пояснить суть? Спасибо.

[ewert]

Очень просто.Для каждой вырезанной клетки ninn -- это количество соседствующих с ней опять-таки вырезанных и next -- количество её сторон, которыми она примыкает к краю доски. Соответственно, 4-ninn-next -- это количество её сторон, которыми она примыкает к невырезанным. Каждая очередная просматриваемая вырезанная клетка добавляет к линии границы исходной (неповреждённой) доски 4-ninn-next отрезков и при этом удаляет из неё next отрезков.

Да, а t[...] -- это, конечно, массив записей (по-вашему "структур"), каждая из которых состоит из двух полей: номер строки и колонки очередной вырезанной клетки.

[Circiter]

2ewert
Ещё раз спасибо. Теперь все стало понятным.

Цитата:

по-вашему "структур"

Ну я 4 года писал на паскале, так что записи тоже для меня вполне естественны. :)