Алгоритм

> как можно быстрей вернуть неудачу если различий нет.

ну в твоей постановке, если различий нет, то нужен полный проход по буферам. Как раз в случае различий можно оптимизировать.

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

Чтобы не сбивать с толку - алгоритм не должен быть привязан к архитектуре и считаем что нет оптимизированных наборов команд, собственно поэтому и возник вопрос. Написал драйвер - у меня это работало на арм и у меня был аппаратный интерфейс с дма которые я и использовал - скармливал весь буфер дма благо он успевал все перекидывать до появления нового буфера. Выложил исходники - пара человек заинтересовалось но у одного х86 с эмуляцией интерфейса на lpt а у другого mips тоже с софтовой эмуляцией и никаких дма соответственно - у них просто нифига не успевает. Встал вопрос оптимизации количества перекидываемых данных.

я бы, для простоты, разбил буфер на регионы и выводил только те регионы что изменились. Например, считая md5(или что попроще :)) и таким образом выявляя что поменялось.

А вообще, выбор алгоритма сильно зависит от постановки задачи. Например, на сколько часто буфера меняются итп.

>для простоты, разбил буфер на регионы и выводил только те регионы что изменились.
Вариант конечно - но не оптимальный. Железяка умеет работать только с прямоугольными областями, если поменялись 5 пикселей например 2 из которых в одном регионе 2 в другом и 1 в третьем то нужно будет объединить их в один большой и из-за 5 пикселей передавать большой результирующий регион.
>на сколько часто буфера меняются
Буфер не изменится пока ты его не отпустишь - элементарно блокировки. Вопрос в другом - устроит ли тебя на экране частота 2 fps %)

я так понимаю ncurses именно это и делает.

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

>А кто пишет в буфер? Может подойдет вариант с проксей, которая и будет сохранять информацию о размере и положении "испорченного" региона.

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

Думаю понятно по предыдущему посту что алгоритмы используемые в ncurses тут совсем не подойдут, потому что ей самой известно что она меняла а что нет.

что-то вроде этого:


#define diff new[i][j]!=old[i][j]

for(i=0..M-1) for(j=0..N-1) if (diff)
{
        min_i=max_i=i;
        min_j=max_j=j1=j2=j;
        goto found;
}

// вообще не нашли
return ((0,0)-(0,0));

found:

for(i=min_i..N-1)
{
//ещем границы фигуры на новой строке.

        //левая граница.
        //отправная точка - колонка, где она начиналась на предыдущей строке
        j=j1

        if(diff) //всё еще на месте
        {
                // ищем левее
                for(j=j1-1..0) if(!diff)
                {
                        min_j=j1=j+1
                        break;
                }
        }
        else //куда-то делась
        {
                // ищем правее
                for(j=j1+1..j2) if(diff)
                {
                        j1=j
                        break;
                }
                if(j>j2) //вообще не нашли
                {
                        max_i=i-1;
                        return ((min_i,min_j)-(max_i,max_j));
                }
        }

        //правая граница.
        //отправная точка - колонка, где она начиналась на предыдущей строке
        j=j2

        if(diff) //всё еще на месте
        {
                // ищем правее
                for(j=j2+1..M) if(!diff)
                {
                        max_j=j2=j-1
                        break;
                }
        }
        else //куда-то делась
        {
                // ищем левее
                for(j=j2-1..j1) if(diff)
                {
                        j2=j
                        break;
                }
                //вообще не нашли уже отсеяли
        }
}

ЗЫ: до ума, надеюсь, сам доведешь?!;)

правда, он охватывает только одну фигуру.

но если у тебя выч. мощности не критичны, а узкое место - канал связи, по которому передаются изменения, подойдет.

завернуть его в цикл, пока не обнаружит все области. каждую - отправлять. параллельно - искать новую.

Много буков - если честно не осилил до конца логику :) Но что-то мне подсказывает
if(diff) //всё еще на месте
{
// ищем левее
for(j=j1-1..0) if(!diff)
{
min_j=j1=j+1
break;
}
}

ты выходишь из цикла как только нашел первое совпадение - но не факт что дальше нет несовпадений.
У меня мысль такая - ищем первое несовпадение с начала буфера (сверху) - уже имеем y1, далее ищем первое несовпадение справа урезая область поиска сверху по y = y1 - выше искать нет смысла мы там смотрели, получаем x2. Затем ищем снизу урезая область поиска справа по x = x2, получаем y2 и в самом конце ищем слева урезая область сверху и снизу y1,y2.

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

да, твой вариант довольно хорош.
главное, если будет несколько фигур - ты их всех сразу охватишь.

мой вариант оптимален для выделения маленьких простеньких фигур. :P
а в случае прямоугольника он вообще даст приличный прирост производительности (хотя и не самый лучший).

но как я понимаю, для тебя это не критично. удачи.

Вообще в условии четко сказано что требуется _минимальный прямоугольник_ :) С твоим алгоритмом когда в буфере в цикле ведется поиск локальных изменений кроется подводный камень: предположим работу в консоли - неграфический режим с точки зрения пользователя. что представляет шрифт - это прямоугольник предположим 8х8 там отображен знак и по краю в любом случае есть фоновые незаполненые пиксели. теперь представим - мы внизу экрана - командная строка и нажимаем enter - происходит скролинг экрана вверх, что произойдет с твоим алгоритмом ? - он обнаружит 80х25 изменившихся фигур :) в итоге нужно будет 80*25=2000 раз передать новые координаты (это команда + 4 координаты прямоугольника) + данные этого региона - а это нехилый оверхед. более того на моей железяке я использую дма при передаче - мне нужно будет 2000 раз перепрограммировать контроллер дма. в моем варианте максимум что произойдет - это отрисовать прямоугольник во весь экран причем в таком случае он будет найден максисально быстро так как границы у самого края откуда и начинается поиск.

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

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