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

Question

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

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

如果你的系统上安装了 Fluxbox 和 Xterm，你可以试试 xwinmidiarptoy BASH 脚本来查看我想要发生的事情的粗略原型(prototype)。见 xwinmidiarptoy.txt我写的关于它的笔记解释了它的作用以及应该如何使用它。

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

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

Fluxbox 窗口放置策略有三个我想要模拟的二元选项:

Windows 构建水平行 或 垂直列(可能)

window 从左到右放置或 从右到左

window 从上到下放置或 从下到上

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

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

为什么算法有问题？

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

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

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

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

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

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

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

2)我的替代方法。

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

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

重要规则:每个方块每边只能接触一个方块。这是特定于算法存储方式的规则 可用空间 并且不考虑实际窗口可能相互接触的数量。

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

不太直接的情况，即要删除的空间只能在一列或一行框内找到，仅部分实现 - 如果要删除的块之一完全适合宽度(即列)或高度(即行)然后出现问题。甚至不要提到这样一个事实，即只检查一格宽的列和一格高的行。

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

因此，我必须添加某种方式使这 +700 行代码适用于其他 7 个放置策略选项，或者我将不得不为其他 7 个选项复制那些 +700 行代码。这些都没有吸引力，第一，因为现有代码足够复杂，第二，因为膨胀。

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

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

那里还有什么？

我已经浏览并打折了:

装箱算法:他们的
强调最佳拟合并不
符合这个要求
算法。

递归二分放置算法:听起来很有希望，但
这些用于电路设计。他们的
重点是最佳的电线长度。

这两个，尤其是后者，在算法开始之前，所有要放置/打包的元素都是已知的。

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

如果需要更多信息，请在评论中提出问题。

提出这个问题后进一步发展的想法

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

Answer 1

我会考虑某种空间散列结构。想象一下，您的整个可用空间都被粗略地网格化，称它们为块。随着 window 的来来去去，它们占据了某些连续的矩形块。对于每个块，跟踪每个角的最大未使用矩形，因此每个块需要存储 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 个块宽度，那么您首先在该列表中查找，然后再在块网格中寻找一些合适的空闲空间。