Алгоритм быстрого размещения блоков, нужен совет?

Question

Мне нужно эмулировать стратегию размещения окон в диспетчере окон Fluxbox .

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

Если в вашей системе установлены Fluxbox и Xterm, вы можете попробовать сценарий xwinmidiarptoy BASH, чтобы увидеть грубый прототип того, что я хочу, чтобы происходило. См. xwinmidiarptoy.txt заметки, которые я написал об этом, объясняющие, что он делает и как его следует использовать.

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

Алгоритм должен быть Онлайн-алгоритм обработка данных "по частям последовательно, т. Е. В том порядке, в котором входные данные подаются в алгоритм, без полного доступа к входным данным. с самого начала. "

Стратегия размещения окна Fluxbox имеет три двоичных параметра, которые я хочу эмулировать:

• Windows строит горизонтальные ряды или вертикальные столбцы (потенциально)

• Окна располагаются слева направо или справа налево

• Окна располагаются сверху вниз или снизу вверх

Различия между целевым алгоритмом и алгоритмом размещения окна

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

Почему алгоритм является проблемой?

Он должен работать до крайних сроков потока в реальном времени в аудиоприложении.

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

И хотя алгоритм никогда не будет размещать окно, которое перекрывает другое, пользователь сможет размещать и перемещать блоки определенных типов, перекрывающиеся окна будут существовать. Структура данных, используемая для хранения окон и / или свободного места, должна быть в состоянии справиться с этим перекрытием.

Пока у меня есть два варианта, для которых я построил свободные прототипы:

1) Порт алгоритма размещения Fluxbox в мой код.

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

Для демонстрации этого я создал программу под названием text_boxer-0.0.2.tar.bz2 , которая принимает текстовый файл в качестве входных данных и размещает его в полях ASCII. Выполните команду make, чтобы собрать ее. Немного недружелюбно, используйте --help (или любой другой недопустимый параметр) для списка параметров командной строки. Вы должны указать текстовый файл, используя опцию.

2) Мой альтернативный подход.

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

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

ВАЖНОЕ ПРАВИЛО: Каждый блок может касаться только одним блоком с каждой стороны. Это правило относится к алгоритму хранения свободного неиспользуемого пространства и не учитывает, сколько реальных окон могут касаться друг друга.

Проблема с этим подходом в том, что очень сложный . Я реализовал простые случаи, когда 1) пространство удаляется из одного угла блока, 2) разбивает соседние блоки так, чтобы соблюдалось ВАЖНОЕ ПРАВИЛО .

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

Я реализовал этот алгоритм на C - языке, который я использую для этого проекта (я не использовал C ++ в течение нескольких лет, и мне неудобно его использовать после того, как я сосредоточил все свое внимание на разработке на C, это хобби) , Реализация состоит из 700+ строк кода (включая множество пустых строк, фигурных скобок, комментариев и т. Д.). Реализация работает только для стратегии размещения горизонтальных рядов + левый-правый + верхний-нижний.

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

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

Текущее состояние реализации этого алгоритма на C: freespace.c . Я использую gcc -O0 -ggdb freespace.c для сборки и запускаю его в xterm размером не менее 124 x 60 символов.

Что еще там?

Я проскользнул и со скидкой:

• Bin Packing алгоритмы: их акцент на оптимальной посадке не соответствовать требованиям этого алгоритм.

• Рекурсивное размещение пополам алгоритмы: звучит многообещающе, но это для схемотехники. Их выделение оптимальной длины провода.

Оба из них, особенно последние, все элементы, которые должны быть размещены / упакованы, известны до начала алгоритма.

Что вы думаете об этом? Как бы вы подошли к этому? Какие еще алгоритмы мне следует посмотреть? Или даже какие концепции мне следует изучить, поскольку я не изучал компьютерные науки / разработку программного обеспечения?

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

Дальнейшие идеи возникли после того, как я задал этот вопрос Некоторая комбинация моего «альтернативного алгоритма» с пространственной хэш-картой для определения того, будет ли большое окно, которое нужно разместить, охватить несколько блоков свободного пространства.

Answer 1

Я бы рассмотрел какую-то пространственную структуру хеширования. Представьте, что все ваше свободное пространство грубо привязано, назовите их блоками. Когда окна приходят и уходят, они занимают определенные наборы смежных прямоугольных блоков. Для каждого блока следите за наибольшим неиспользованным прямоугольником, падающим на каждый угол, поэтому вам нужно хранить 2 * 4 действительных числа на блок. Для пустого блока прямоугольники в каждом углу имеют размер, равный блоку. Таким образом, блок может быть «использован» только по углам, поэтому в любом блоке может находиться не более 4 окон.

Теперь каждый раз, когда вы добавляете окно, вы должны искать прямоугольный набор блоков, для которых будет подходить окно, и когда вы это делаете, обновлять размеры свободных углов. Вы должны определить размеры своих блоков так, чтобы несколько (~ 4x4) из них помещались в типичное окно. Для каждого окна отслеживайте, к каким блокам оно относится (вам нужно отслеживать только экстенты), а также к каким окнам касается данный блок (не более 4 в этом алгоритме). Существует очевидный компромисс между гранулярностью блоков и объемом работы на вставку / удаление окна.

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

Я представляю такую ​​структуру данных, как

struct block{
    int free_x[4]; // 0 = top left, 1 = top right,
    int free_y[4]; // 2 = bottom left, 3 = bottom right
    int n_windows; // number of windows that occupy this block
    int window_id[4]; // IDs of windows that occupy this block
};
block blocks[NX][NY];

struct window{
    int id;
    int used_block_x[2]; // 0 = first index of used block,
    int used_block_y[2]; // 1 = last index of used block
};

Редактировать

Вот картинка:

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

Вы упомянули в редактировании, что сетка, на которой будут размещены ваши окна, уже довольно грубая (127x127), поэтому размеры блоков, вероятно, будут примерно такими, как 4 ячейки сетки на стороне, что, вероятно, не принесет вам большой пользы. , Этот метод подходит, если ваши координаты угла окна могут принимать много значений (я думал, они будут пикселями), но не так много в вашем случае. Вы все еще можете попробовать, так как это просто. Возможно, вы захотите также сохранить список полностью пустых блоков, чтобы в случае появления окна шириной более 2 блоков вы сначала смотрели этот список, прежде чем искать подходящее свободное место в сетке блоков.

Answer 2

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

Следующая функция сканирует массив на предмет размера width * height. Первая найденная позиция записывает координаты верхнего левого угла, на который указывают resultx и resulty.

_Bool freespace_remove( freespace* fs,
                        int width,     int height,
                        int* resultx,  int* resulty)
{
    int x = 0;
    int y = 0;
    const int rx = FSWIDTH - width;
    const int by = FSHEIGHT - height;

    *resultx = -1;
    *resulty = -1;

    char* buf[height];

    for (y = 0; y < by; ++y)
    {
        x = 0;
        char* scanx = fs->buf[y];

        while (x < rx)
        {
            while(x < rx && *(scanx + x))
                ++x;

            int w, h;

            for (h = 0; h < height; ++h)
                buf[h] = fs->buf[y + h] + x;

            _Bool usable = true;
            w = 0;

            while (usable && w < width)
            {
                h = 0;
                while (usable && h < height)
                    if (*(buf[h++] + w))
                        usable = false;
                ++w;
            }

            if (usable)
            {
                for (w = 0; w < width; ++w)
                    for (h = 0; h < height; ++h)
                        *(buf[h] + w) = 1;

                *resultx = x;
                *resulty = y;
                return true;
            }

            x += w;
        }
    }

    return false;
}

2d массив инициализируется нулями. Любые области в массиве, где используется пространство, установлены на 1. Эта структура и функция будут работать независимо от фактического списка окон, которые занимают области, отмеченные 1.

Преимуществами этого метода являются его простота. Он использует только одну структуру данных - массив. Функция короткая, и ее не должно быть слишком сложно адаптировать для обработки оставшихся вариантов размещения (здесь она обрабатывает только строку Smart + слева направо + сверху вниз).

Мои начальные тесты также выглядят многообещающими на скорости. Хотя я не думаю, что это подойдет для оконного менеджера, размещающего окна, например, на рабочем столе 1600 x 1200 с точностью до пикселя, для моих целей я считаю, что это будет намного лучше, чем любой из предыдущих методов, которые у меня есть пробовал.

Скомпилированный тестовый код здесь: http://jwm -art.net / искусство / текст / freespace_grid.c
(в Linux я использую gcc -ggdb -O0 freespace_grid.c для компиляции)

Answer 3

#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>


#define FSWIDTH 128
#define FSHEIGHT 128


#ifdef USE_64BIT_ARRAY
    #define FSBUFBITS 64
    #define FSBUFWIDTH 2
    typedef uint64_t fsbuf_type;
    #define TRAILING_ZEROS( v ) __builtin_ctzl(( v ))
    #define LEADING_ONES( v )   __builtin_clzl(~( v ))
#else
#ifdef USE_32BIT_ARRAY
    #define FSBUFBITS 32
    #define FSBUFWIDTH 4
    typedef uint32_t fsbuf_type;
    #define TRAILING_ZEROS( v ) __builtin_ctz(( v ))
    #define LEADING_ONES( v )   __builtin_clz(~( v ))
#else
#ifdef USE_16BIT_ARRAY
    #define FSBUFBITS 16
    #define FSBUFWIDTH 8
    typedef uint16_t fsbuf_type;
    #define TRAILING_ZEROS( v ) __builtin_ctz( 0xffff0000 | ( v ))
    #define LEADING_ONES( v )   __builtin_clz(~( v ) << 16)
#else
#ifdef USE_8BIT_ARRAY
    #define FSBUFBITS 8
    #define FSBUFWIDTH 16
    typedef uint8_t fsbuf_type;
    #define TRAILING_ZEROS( v ) __builtin_ctz( 0xffffff00 | ( v ))
    #define LEADING_ONES( v )   __builtin_clz(~( v ) << 24)
#else
    #define FSBUFBITS 1
    #define FSBUFWIDTH 128
    typedef unsigned char fsbuf_type;
    #define TRAILING_ZEROS( v ) (( v ) ? 0 : 1)
    #define LEADING_ONES( v )   (( v ) ? 1 : 0)
#endif
#endif
#endif
#endif


static const fsbuf_type fsbuf_max =   ~(fsbuf_type)0;
static const fsbuf_type fsbuf_high =  (fsbuf_type)1 << (FSBUFBITS - 1);


typedef struct freespacegrid
{
    fsbuf_type buf[FSHEIGHT][FSBUFWIDTH];

    _Bool left_to_right;
    _Bool top_to_bottom;

} freespace;


void freespace_dump(freespace* fs)
{
    int x, y;

    for (y = 0; y < FSHEIGHT; ++y)
    {
        for (x = 0; x < FSBUFWIDTH; ++x)
        {
            fsbuf_type i = FSBUFBITS;
            fsbuf_type b = fs->buf[y][x];

            for(; i != 0; --i, b <<= 1)
                putchar(b & fsbuf_high ? '#' : '/');
/*
            if (x + 1 < FSBUFWIDTH)
                putchar('|');
*/
        }
        putchar('\n');
    }
}


freespace* freespace_new(void)
{
    freespace* fs = malloc(sizeof(*fs));

    if (!fs)
        return 0;

    int y;

    for (y = 0; y < FSHEIGHT; ++y)
    {
        memset(&fs->buf[y][0], 0, sizeof(fsbuf_type) * FSBUFWIDTH);
    }

    fs->left_to_right = true;
    fs->top_to_bottom = true;

    return fs;
}


void freespace_delete(freespace* fs)
{
    if (!fs)
        return;

    free(fs);
}

/* would be private function: */
void fs_set_buffer( fsbuf_type buf[FSHEIGHT][FSBUFWIDTH],
                    unsigned x,
                    unsigned y1,
                    unsigned xoffset,
                    unsigned width,
                    unsigned height)
{
    fsbuf_type v;
    unsigned y;

    for (; width > 0 && x < FSBUFWIDTH; ++x)
    {
        if (width < xoffset)
            v = (((fsbuf_type)1 << width) - 1) << (xoffset - width);
        else if (xoffset < FSBUFBITS)
            v = ((fsbuf_type)1 << xoffset) - 1;
        else
            v = fsbuf_max;

        for (y = y1; y < y1 + height; ++y)
        {
#ifdef FREESPACE_DEBUG
            if (buf[y][x] & v)
                printf("**** over-writing area ****\n");
#endif
            buf[y][x] |= v;
        }

        if (width < xoffset)
            return;

        width -= xoffset;
        xoffset = FSBUFBITS;
    }
}


_Bool freespace_remove(   freespace* fs,
                          unsigned width, unsigned height,
                          int* resultx,   int* resulty)
{
    unsigned x, x1, y;
    unsigned w, h;
    unsigned xoffset, x1offset;
    unsigned tz; /* trailing zeros */

    fsbuf_type* xptr;
    fsbuf_type mask =   0;
    fsbuf_type v;

    _Bool scanning = false;
    _Bool offset = false;

    *resultx = -1;
    *resulty = -1;

    for (y = 0; y < (unsigned) FSHEIGHT - height; ++y)
    {
        scanning = false;
        xptr = &fs->buf[y][0];

        for (x = 0; x < FSBUFWIDTH; ++x, ++xptr)
        {
            if(*xptr == fsbuf_max)
            {
                scanning = false;
                continue;
            }

            if (!scanning)
            {
                scanning = true;
                x1 = x;
                x1offset = xoffset = FSBUFBITS;
                w = width;
            }
retry:
            if (w < xoffset)
                mask = (((fsbuf_type)1 << w) - 1) << (xoffset - w);
            else if (xoffset < FSBUFBITS)
                mask = ((fsbuf_type)1 << xoffset) - 1;
            else
                mask = fsbuf_max;

            offset = false;

            for (h = 0; h < height; ++h)
            {
                v = fs->buf[y + h][x] & mask;

                if (v)
                {
                    tz = TRAILING_ZEROS(v);
                    offset = true;
                    break;
                }
            }

            if (offset)
            {
                if (tz)
                {
                    x1 = x;
                    w = width;
                    x1offset = xoffset = tz;
                    goto retry;
                }
                scanning = false;
            }
            else
            {
                if (w <= xoffset) /***** RESULT! *****/
                {
                    fs_set_buffer(fs->buf, x1, y, x1offset, width, height);
                    *resultx = x1 * FSBUFBITS + (FSBUFBITS - x1offset);
                    *resulty = y;
                    return true;
                }
                w -= xoffset;
                xoffset = FSBUFBITS;
            }
        }
    }
    return false;
}


int main(int argc, char** argv)
{
    int x[1999];
    int y[1999];
    int w[1999];
    int h[1999];

    int i;

    freespace* fs = freespace_new();

    for (i = 0; i < 1999; ++i, ++u)
    {
        w[i] = rand() % 18 + 4;
        h[i] = rand() % 18 + 4;

        freespace_remove(fs, w[i], h[i], &x[i], &y[i]);
/*
        freespace_dump(fs);
        printf("w:%d h:%d x:%d y:%d\n", w[i], h[i], x[i], y[i]);
        if (x[i] == -1)
            printf("not removed space %d\n", i);
        getchar();
*/
    }

    freespace_dump(fs);
    freespace_delete(fs);

    return 0;
}

Приведенный выше код требует, чтобы один из USE_64BIT_ARRAY, USE_32BIT_ARRAY, USE_16BIT_ARRAY, USE_8BIT_ARRAY был определен в противном случае он будет использовать только старший бит unsigned char для сохранение состояния ячеек сетки.

Функция fs_set_buffer не будет объявлена ​​в заголовке и станет статической в ​​реализации, когда этот код будет разбит на файлы .h и .c. Будет предоставлена ​​более удобная для пользователя функция, скрывающая детали реализации, для удаления использованного пространства из сетки.

В целом, эта реализация быстрее без оптимизации, чем мой предыдущий ответ с максимальной оптимизацией (с использованием GCC на 64-битной Gentoo, опции оптимизации -O0 и -O3 соответственно).

Относительно USE_ NN BIT_ARRAY и разных размеров битов, я использовал два разных метода синхронизации кода, который в 1999 году вызывает freespace_remove.

Синхронизация main() с использованием команды Unix time (и отключение любых выходных данных в коде), казалось, подтвердили мои ожидания, что большие битовые размеры быстрее.

С другой стороны, синхронизация отдельных вызовов с freespace_remove (с использованием gettimeofday) и сравнение максимального времени, затраченного на вызовы 1999 года, по-видимому, указывают на то, что младшие биты были быстрее.

Это было протестировано только на 64-битной системе (Intel Dual Core II).