快速块放置算法,需要建议吗？
Jam*_*ris 10 algorithm packing bisection
我需要模拟Fluxbox窗口管理器的窗口放置策略.
作为一个粗略的指南,可视化随机大小的窗口一次一个地填满屏幕,其中每个窗口的粗略大小导致屏幕上平均80个窗口,而没有任何窗口与另一个窗口重叠.
如果您的系统上安装了Fluxbox和Xterm,您可以尝试使用xwinmidiarptoy BASH脚本来查看我想要发生的事情的粗略原型.请参阅我写过的xwinmidiarptoy.txt说明,解释它的作用以及如何使用它.
重要的是要注意窗口将关闭,并且关闭先前占用的窗口的空间再次可用于放置新窗口.
该算法需要是一个在线算法处理数据"以串行方式逐个处理,即按照输入被提供给算法的顺序,而不需要从一开始就提供整个输入."
Fluxbox窗口放置策略有三个我想模拟的二元选项:
Windows构建水平行或垂直列(可能)
Windows从左到右或从右到左放置
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算法:它们对最佳拟合的强调与该算法的要求不匹配.
递归二分位置算法:听起来很有希望,但这些都是用于电路设计的.他们的重点是最佳的电线长度.
在算法开始之前,所有这些元素,特别是后者,所有要放置的元素/包都是已知的.
你对此有何看法？你会怎么做？我应该看看还有哪些其他算法？或者甚至我应该研究哪些概念,因为我没有学过计算机科学/软件工程？
如果需要进一步的信息,请在评论中提问.
自提出这个问题后开发的其他想法
- 我的"替代算法"与空间散列图的某种组合,用于识别要放置的大窗口是否会覆盖几个可用空间块.
我会考虑某种空间哈希结构.想象一下,你的整个自由空间被粗略地网格化,称之为块.当窗户来来往往时,它们占据了一些连续的矩形块.对于每个块,跟踪每个角落中最大的未使用矩形,因此您需要为每个块存储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个块宽度的窗口,那么你先查看该列表中的第一个,然后在块网格中寻找一些合适的空闲空间.
#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 位系统（Intel Dual Core II）上进行了测试。