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

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个放置策略选项，或者我必须将这些+700行代码复制到其他七个选项中。两者都不太理想，第一个原因是现有代码已经足够复杂，第二个原因是膨胀。

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

当前C语言实现该算法的状态为freespace.c。我使用gcc -O0 -ggdb freespace.c进行构建，并在至少124 x 60字符大小的xterm中运行它。

还有什么其他的吗？

我已经浏览并排除了以下内容：

• 装箱算法：它们强调最佳适配，与该算法的要求不符。

• 递归二分放置算法：听起来很有前途，但这些是用于电路设计的。它们强调最佳线长。

这两种算法，特别是后者，在算法开始之前就已知所有要放置/打包的元素。

你对此有何想法？你会如何处理？我应该看哪些其他算法？或者我应该研究哪些概念，因为我没有学习过计算机科学/软件工程？

如果需要进一步的信息，请在评论中提出问题。

自提问以来进一步发展的想法

• 我的“替代算法”与空间哈希图的某些组合，用于识别一个要放置的大窗口是否会覆盖多个自由空间块。

- James Morris

---

哦，为什么我要在周五晚上（当地时间）提出这样复杂的问题，当每个人都有更好的事情要做呢？？？ - James Morris

这些是Stack Overflow唯一有趣的问题！琐碎问题的日常涡流使我不想访问这个网站。 - Victor Liu

@James Morris：我有一种奇怪的感觉，好像我之前读过这个问题的更短版本... - ire_and_curses

@James Morris：窗口是否必须对齐于127x127网格，还是可以占据半个网格单元？窗口大小的分布情况如何？ - Victor Liu

没有半个单元格。窗口大小的分布，最小应该是1x1，最大的...我不确定，也许是64x64？ - James Morris

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块宽的窗口，则首先查找该列表，然后再查找块网格中的某些合适的空间。

- Victor Liu

---

我觉得这个方法很有趣，虽然听起来有些奇怪，但 Victor 给你点赞。不过我还没有完全理解它。请看我的编辑，提到了单位，自由空间的网格有多粗？能否提供一个图表呢？ - James Morris

Answer 2

经历了一些失败的尝试之后，我最终来到了这里。这里已经放弃使用数据结构来存储自由空间的矩形区域。相反，使用了一个128 x 128元素的2D数组来实现相同的结果，但复杂度要低得多。

下面的函数扫描该数组以查找大小为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;
}

这个二维数组会被初始化为0。数组中任何用过的空间都会被设置为1。这个结构和函数独立于实际窗口列表，它们仅与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进行编译）

- James Morris

---

我打算尝试使用单独的位来存储一个单元格是否被使用，而不是整个字符。 - James Morris

我仍在努力使用二维数组的每个单独位来表示每个单元格是否被窗口占用。这意味着二维数组现在是 buf_type buf[128][128 / (sizeof(buf_type) * CHAR_BIT)] - 是的，二维数组中的每个单独元素都是一个typedef类型，因此我可以测试使用char与int、short、long之间的区别，以查看它们对性能的影响。一旦我有了行智能+左上角+上下特定实现的工作原理，我将发布另一个答案，并详细说明它与这个（更简单）解决方案的比较情况。 - James Morris

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文件时，它将在实现中变为静态函数。提供了一个更用户友好的函数来隐藏实现细节，以从网格中删除已使用的空间。

总体而言，这个实现比我的先前的答案更快，即使没有优化（在64位Gentoo上使用GCC，优化选项分别为-O0和-O3）。

关于USE_NNBIT_ARRAY和不同的位大小，我使用了两种不同的计时代码的方法，这些代码调用1999次freespace_remove。

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

另一方面，使用gettimeofday计时单个freespace_remove调用，并比较1999次调用中所需的最长时间，似乎表明较低的位数更快。

这只在64位系统（Intel Dual Core II）上进行过测试。

- James Morris