algorithm - 快速块放置算法，需要建议吗？

Question

我需要模拟Fluxbox窗口管理器的窗口放置策略。

作为粗略的指导，一次将一个随机大小的窗口可视化填充屏幕，每个窗口的粗略大小导致屏幕上平均有 80 个窗口，而没有任何窗口重叠。

如果您的系统上安装了 Fluxbox 和 Xterm，您可以尝试使用xwinmidiarptoy BASH 脚本来查看我想要发生的事情的粗略原型。请参阅我写的关于它的xwinmidiarptoy.txt注释，解释它的作用以及应该如何使用它。

重要的是要注意窗口将关闭，并且之前关闭的窗口占用的空间再次可用于放置新窗口。

该算法需要是一种在线算法，“以串行方式逐个处理数据，即按照将输入馈送到算法的顺序，而无需从一开始就提供整个输入。”

Fluxbox 窗口放置策略有三个我想模拟的二进制选项：

• Windows 构建水平行或垂直列（可能）

• 窗户从左到右或从右到左放置

• 窗户从上到下或从下到上放置

目标算法和窗口放置算法之间的差异

坐标单位不是像素。将放置块的网格将是 128 x 128 单位。此外，放置区域可以被放置在网格内的边界区域进一步缩小。

为什么算法有问题？

它需要在音频应用程序中的实时线程的最后期限内运行。

目前我只关心获得一个快速的算法，不要担心实时线程的影响以及由此带来的所有编程障碍。

尽管该算法永远不会放置与另一个重叠的窗口，但用户将能够放置和移动某些类型的块，重叠窗口将存在。用于存储窗口和/或空闲空间的数据结构需要能够处理这种重叠。

到目前为止，我有两个选择，我为它们构建了松散的原型：

1) 将 Fluxbox 放置算法移植到我的代码中。

问题是，当我尝试使用算法放置 256 个块的最坏情况时，客户端（我的程序）被踢出音频服务器（JACK ）。该算法在放置第 256 个窗口时对已放置的块列表执行超过 14000 次完整（线性）扫描。

为了演示这一点，我创建了一个名为text_boxer-0.0.2.tar.bz2的程序，它将文本文件作为输入并将其排列在 ASCII 框中。发布make构建它。有点不友好，使用--help（或任何其他无效选项）作为命令行选项列表。您必须使用该选项指定文本文件。

2）我的替代方法。

仅部分实现，该方法对每个矩形空闲未使用空间区域使用数据结构（窗口列表可以完全分开，并且不需要测试该算法）。该数据结构充当双向链表中的节点（具有排序插入），并包含左上角的坐标以及宽度和高度。

此外，每个块数据结构还包含四个链接，这些链接连接到四个边中每一个上的每个紧邻（接触）块。

重要规则：每个积木每边只能接触一个积木。这是特定于算法存储空闲未使用空间的方式的规则，并且与实际窗口可能相互接触的数量无关。

这种方法的问题是，它非常复杂。我已经实现了简单的案例，其中 1) 从块的一个角移除空间，2) 拆分相邻块以便遵守重要规则。

不太直接的情况，即要删除的空间只能在一列或一行框中找到，仅部分实现 - 如果要删除的块之一与宽度（即列）或高度（即行）然后出现问题。更不用说这个事实，它只检查一框宽的列，一框高的行。

我已经在 C 中实现了这个算法——我在这个项目中使用的语言（我已经有几年没有使用 C++ 并且在将所有注意力都集中在 C 开发之后使用它感到不舒服，这是一种爱好）。实现是 700 多行代码（包括大量的空白行、大括号行、注释等）。该实现仅适用于水平行+左右+上下放置策略。

所以我要么必须添加一些方法，使这+700 行代码适用于其他7 个放置策略选项，要么我将不得不为其他7 个选项复制那些+700 行代码。这些都没有吸引力，第一，因为现有代码足够复杂，第二，因为臃肿。

由于缺少功能，该算法甚至还没有处于我可以在实时最坏情况下使用它的阶段，所以我仍然不知道它实际上是否比第一种方法表现更好或更差。

该算法的 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;
}

二维数组是零初始化的。阵列中使用空间的任何区域都设置为 1。此结构和功能将独立于占用标有 1 的区域的实际窗口列表工作。

这种方法的优点是简单。它只使用一种数据结构——一个数组。该功能很短，应该不难适应处理剩余的放置选项（这里它只处理 Row Smart + 从左到右 + 从上到下）。

我最初的测试在速度方面也很有希望。尽管我认为这不适合将窗口放置在例如具有像素精度的 1600 x 1200 桌面上的窗口管理器，但就我的目的而言，我相信它会比我以前的任何方法都好得多试过了。

此处可编译的测试代码：http://jwm-art.net/art/text/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退到仅使用 an 的高位unsigned char来存储网格单元的状态。

该函数fs_set_buffer不会在标头中声明，并且当此代码在 .h 和 .c 文件之间拆分时，它将在实现中变为静态。将提供一个更加用户友好的隐藏实现细节的功能，用于从网格中删除已使用的空间。

总的来说，这个实现在没有优化的情况下比我之前的最大优化答案更快（在 64 位 Gentoo 上使用 GCC，分别优化选项 -O0 和 -O3）。

关于USE_NN BIT_ARRAY 和不同的位大小，我使用了两种不同的方法来对 1999 年调用freespace_remove.

main()使用 Unix命令计时time（并禁用代码中的任何输出）似乎证明了我的期望是正确的——更高的位大小更快。

另一方面，对freespace_remove（使用gettimeofday）的单个调用进行计时并比较 1999 年调用的最大时间似乎表明较小的位大小更快。

这仅在 64 位系统（英特尔双核 II）上进行了测试。