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

Я бы рассмотрел какую-то пространственную структуру хеширования. Представьте, что все ваше свободное пространство грубо размечено сеткой, назовите их блоками. Когда окна появляются и исчезают, они занимают определенные наборы смежных прямоугольных блоков. Для каждого блока отслеживайте наибольший неиспользуемый прямоугольник, попадающий в каждый угол, поэтому вам нужно хранить 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 блока, вы сначала смотрели в этот список, прежде чем искать подходящее свободное место в сетке блоков.

После некоторых фальстартов я в конце концов прибыл сюда. Здесь отказались от использования структур данных для хранения прямоугольных областей свободного пространства. Вместо этого есть двумерный массив с элементами 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. Эта структура и функция будут работать независимо от фактического списка окон, занимающих области, отмеченные единицами.

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

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

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

#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_NNBIT_ARRAY и разных размеров битов, я использовал два разных метода синхронизации кода, который делает 1999 вызовов freespace_remove.

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

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

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