Бърз алгоритъм за поставяне на блокове, необходим е съвет?

Бих обмислил някакъв вид структура за пространствено хеширане. Представете си, че цялото ви свободно пространство е грубо очертано, наречете ги блокове. Докато прозорците идват и си отиват, те заемат определени комплекти от съседни правоъгълни блокове. За всеки блок следете най-големия неизползван правоъгълник, падащ на всеки ъгъл, така че трябва да съхранявате 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 ширини на блока, тогава да погледнете първо в този списък, преди да потърсите подходящо свободно място в блоковата мрежа.

След няколко фалстарта, в крайна сметка пристигнах тук. Тук е изоставено използването на структури от данни за съхраняване на правоъгълни области на свободно пространство. Вместо това има 2d масив с 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.

Предимствата на този метод са неговата простота. Той използва само една структура от данни - масив. Функцията е кратка и не би трябвало да е твърде трудна за адаптиране, за да се справи с останалите опции за разположение (тук обработва само интелигентен ред + отляво надясно + отгоре надолу).

Първоначалните ми тестове също изглеждат обещаващи по отношение на скоростта. Въпреки че не мисля, че това би било подходящо за мениджър на прозорци, който поставя прозорци на, например, 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).