高速ブロック配置アルゴリズム、アドバイスが必要ですか?
https://stackoverflow.com/questions/2746590
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
のウィンドウ配置戦略をエミュレートする必要があります。 フラックスボックス 窓際マネージャー。
大まかなガイドとして、ランダムなサイズのウィンドウが一度に 1 つずつ画面を埋めていく様子を視覚化します。各ウィンドウの大まかなサイズにより、他のウィンドウと重なるウィンドウがなく、画面上に平均 80 個のウィンドウが表示されます。
システムに Fluxbox と Xterm がインストールされている場合は、以下を試すことができます。 xwinmidiarptoy BASH スクリプトを使用して、希望する動作の大まかなプロトタイプを確認します。を参照してください。 xwinmidirptoy.txt これが何をするのか、どのように使用するべきかを説明するメモを書きました。
ウィンドウが閉じると、閉じたウィンドウが以前に占めていたスペースが再び新しいウィンドウの配置に使用できるようになることに注意することが重要です。
アルゴリズムは オンラインアルゴリズム データを「シリアル方式で、つまり、最初から入力全体を利用できるようにすることなく、入力がアルゴリズムに供給される順序で、ピースごとに」処理します。
Fluxbox のウィンドウ配置戦略には、エミュレートしたい 3 つのバイナリ オプションがあります。
Windows は水平方向の行を構築します または 垂直列 (潜在的に)
窓は左から右に配置されます または 右から左に
窓は上から下に配置されます または 下から上へ
ターゲット アルゴリズムとウィンドウ配置アルゴリズムの違い
座標単位はピクセルではありません。ブロックが配置されるグリッドは 128 x 128 単位になります。さらに、配置領域は、グリッド内に配置された境界領域によってさらに縮小されてもよい。
なぜアルゴリズムが問題になるのでしょうか?
オーディオ アプリケーションのリアルタイム スレッドの期限までに動作する必要があります。
この瞬間に 高速なアルゴリズムを取得することだけを考えています, 、リアルタイム スレッドの影響や、それがもたらすプログラミングのあらゆるハードルについて心配する必要はありません。
また、アルゴリズムは他のウィンドウと重なるウィンドウを配置することは決してありませんが、ユーザーは特定の種類のブロックを配置したり移動したりすることができ、重複するウィンドウが存在します。ウィンドウや空き領域を格納するために使用されるデータ構造は、この重複を処理できる必要があります。
これまでのところ、緩いプロトタイプを構築した選択肢は 2 つあります。
1) Fluxbox 配置アルゴリズムをコードに移植しました。
これの問題は、クライアント (私のプログラム) がオーディオ サーバーから追い出されることです (ジャック) アルゴリズムを使用して 256 ブロックの最悪のシナリオを配置しようとしたとき。このアルゴリズムは、256 番目のウィンドウを配置するときに、すでに配置されているブロックのリストに対して 14000 を超える完全 (線形) スキャンを実行します。
これをデモンストレーションするために、というプログラムを作成しました。 text_boxer-0.0.2.tar.bz2 これはテキスト ファイルを入力として受け取り、それを ASCII ボックス内に配置します。問題 make それを構築するために。少し不親切です、使用してください --help (またはその他の無効なオプション) コマンド ライン オプションのリストを表示します。オプションを使用してテキスト ファイルを指定する必要があります。
2) 私の別のアプローチ。
部分的にのみ実装されているこのアプローチでは、長方形の領域ごとにデータ構造が使用されます。 無料未使用 スペース (ウィンドウのリストは完全に分離することができ、このアルゴリズムのテストには必要ありません)。データ構造は、二重リンク リスト (ソートされた挿入付き) のノードとして機能するほか、左上隅の座標、幅と高さが含まれます。
さらに、各ブロック データ構造には、4 つの辺のそれぞれですぐに隣接する (接触している) ブロックに接続する 4 つのリンクも含まれています。
重要なルール: 各ブロックは、片側につき 1 つのブロックのみと接触できます。これは、アルゴリズムの保存方法に固有のルールです。 未使用の空きスペース 実際に互いに接触するウィンドウの数は考慮されません。
このアプローチの問題点は、 非常に複雑な. 。私は、1) ブロックの 1 つの角からスペースを削除する、2) 隣接するブロックを分割するという単純なケースを実装しました。 重要なルール が遵守されています。
あまり単純ではないケースでは、削除されるスペースがボックスの列または行内でのみ見つかる場合、削除されるブロックの 1 つが幅 (つまり列) または高さ (つまり、行）その後、問題が発生します。 また、これがチェックするのは 1 ボックス幅の列と 1 ボックス高さの行だけであるという事実には言及しないでください。
私はこのアルゴリズムを C で実装しました。このプロジェクトで使用している言語です (ここ数年 C++ を使用していませんでした。C 開発にすべての注意を集中してきた後では、C++ を使用することに抵抗があります。これは趣味です)。実装には 700 行を超えるコードが含まれます (多数の空白行、中括弧行、コメントなどを含む)。この実装は、水平行 + 左-右 + 上下の配置戦略でのみ機能します。
したがって、この +700 行のコードを他の 7 つの配置戦略オプションで機能させる何らかの方法を追加するか、これらの +700 行のコードを他の 7 つのオプション用に複製する必要があります。これらはどちらも魅力的ではありません。1 つ目は既存のコードが十分に複雑であるため、2 つ目は肥大化のためです。
このアルゴリズムは、機能が欠けているため、リアルタイムの最悪のシナリオで使用できる段階にさえなっていないため、実際に最初のアプローチよりもパフォーマンスが良いか悪いかはまだわかりません。
このアルゴリズムの C 実装の現在の状態は次のとおりです。 フリースペース.c. 。私が使う gcc -O0 -ggdb freespace.c をビルドし、少なくとも 124 x 60 文字のサイズの xterm で実行します。
他には何があるの？
ざっと読んで割引しました：
ビンのパッキング アルゴリズム:最適な適合に重点が置かれていることは、このアルゴリズムの要件と一致しません。
再帰的な二等分配置 アルゴリズム:有望なように聞こえますが、これらは回路設計用です。それらの強調は、最適なワイヤの長さです。
これらの両方、特に後者では、配置/パックされるすべての要素がアルゴリズムの開始前にわかっています。
これについてはどう思いますか？どのようにアプローチしますか?他にどのようなアルゴリズムを検討する必要がありますか?あるいは、コンピュータ サイエンスやソフトウェア エンジニアリングを学んだことがないので、どのような概念を研究すべきでしょうか?
さらに詳しい情報が必要な場合は、コメントで質問してください。
この質問をしてからさらにアイデアが生まれました
- 私の「代替アルゴリズム」と、配置される大きなウィンドウが空き領域のいくつかのブロックをカバーするかどうかを識別するための空間ハッシュマップを組み合わせたものです。
解決 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;
}
上記のコード 1 つ必要です の 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 回の呼び出しを行うコードのタイミングを計る 2 つの異なる方法を使用しました。 freespace_remove.
タイミング main() Unix を使用する time コマンド (およびコード内の出力を無効にする) は、ビット サイズが大きいほど高速であるという私の期待が正しかったことを証明したようです。
一方、個々の呼び出しのタイミングを調整することは、 freespace_remove (使用して gettimeofday)、1999 年の呼び出しにかかった最大時間を比較すると、ビット サイズが小さい方が高速であることが示されたようです。
これは 64 ビット システム (Intel Dual Core II) でのみテストされています。
他のヒント
ある種の空間ハッシュ構造を検討します。あなたの自由空間全体が粗くグリッドされていると想像してください、それらをブロックと呼びます。窓が出入りするにつれて、彼らは特定の隣接する長方形ブロックのセットを占有します。各ブロックについて、各コーナーへの最大の未使用の長方形のインシデントを追跡するため、ブロックごとに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
};
編集
これが写真です：
2つの例ブロックを示しています。色付きのドットは、ブロックの角を示し、それらから発せられる矢印は、その角からの最大のフリーリカングの範囲を示しています。
編集で、ウィンドウが配置されるグリッドはすでに非常に粗い（127x127）ので、ブロックサイズはおそらくサイドの4つのグリッドセルのようなものであり、おそらくあまり得られないでしょう。この方法は、ウィンドウコーナー座標が多くの値をとることができる場合（私はそれらがピクセルになると思っていました）、あなたの場合はそれほど適していません。簡単だから試してみることができます。また、完全に空のブロックのリストを保持して、ウィンドウが入っている場合は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;
}
2D配列はゼロ初期化されています。スペースが使用される配列内のすべての領域は1に設定されています。この構造と機能は、1でマークされた領域を占有しているウィンドウの実際のリストとは独立して機能します。
この方法の利点は、その単純さです。 1つのデータ構造（配列）のみを使用します。関数は短いため、残りの配置オプションを処理するために適応するのが難しくないはずです（ここでは、Row Smart +左 +右 +上から下にのみ処理します）。
私の最初のテストは、スピードフロントでも有望に見えます。これは、ウィンドウマネージャーがWindowsをオンにするのに適しているとは思わないが、たとえば、ピクセルの精度を備えた1600 x 1200デスクトップなど、私の目的のために試してみました。
ここで編集可能なテストコード：http://jwm-art.net/art/text/freespace_grid.c
（Linuxで使用します gcc -ggdb -O0 freespace_grid.c コンパイルする）
