algorithm - 高速ブロック配置アルゴリズム、アドバイスが必要ですか？

Question

Fluxboxウィンドウマネージャーのウィンドウ配置戦略をエミュレートする必要があります。

大まかなガイドとして、ランダムなサイズのウィンドウが一度に1つずつ画面に表示されることを視覚化します。各ウィンドウの大まかなサイズでは、ウィンドウが互いに重なることなく、画面上に平均80個のウィンドウが表示されます。

システムにFluxboxとXtermがインストールされている場合は、xwinmidiarptoy BASHスクリプトを試して、私が何をしたいかの大まかなプロトタイプを確認できます。それが何をするのか、そしてそれがどのように使われるべきかを説明する私がそれについて書いたxwinmidiarptoy.txtノートを見てください。

ウィンドウが閉じ、以前に閉じていたウィンドウが占めていたスペースが、新しいウィンドウの配置に再び使用できるようになることに注意することが重要です。

アルゴリズムは、「最初から入力全体を利用できるようにすることなく、入力がアルゴリズムに供給される順序で、シリアルに1つずつ」データを処理するオンラインアルゴリズムである必要があります。

Fluxboxウィンドウ配置戦略には、エミュレートしたい3つのバイナリオプションがあります。

• Windowsは水平行ま​​たは垂直列を作成します（潜在的に）

• ウィンドウは左から右または右から左に配置されます

• ウィンドウは上から下または下から上に配置されます

ターゲットアルゴリズムとウィンドウ配置アルゴリズムの違い

座標単位はピクセルではありません。ブロックが配置されるグリッドは128x128ユニットになります。さらに、配置領域は、グリッド内に配置された境界領域によってさらに縮小される場合があります。

なぜアルゴリズムが問題なのですか？

オーディオアプリケーションのリアルタイムスレッドの期限まで動作する必要があります。

現時点では、高速アルゴリズムの取得のみに関心があります。リアルタイムスレッドの影響と、それがもたらすプログラミングのすべてのハードルについては気にしないでください。

また、アルゴリズムが別のウィンドウと重なるウィンドウを配置することはありませんが、ユーザーは特定のタイプのブロックを配置および移動でき、重なるウィンドウが存在します。ウィンドウや空き領域を格納するために使用されるデータ構造は、この重複を処理できる必要があります。

これまでのところ、ルーズなプロトタイプを作成した2つの選択肢があります。

1）Fluxbox配置アルゴリズムのコードへの移植。

これに伴う問題は、アルゴリズムを使用して256ブロックの最悪のシナリオを配置しようとすると、クライアント（私のプログラム）がオーディオサーバー（ JACK ）から追い出されることです。このアルゴリズムは、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開発にすべての注意を向けた後、それを使用するのは不快です、それは趣味です）。実装は700行以上のコードです（多くの空白行、中括弧行、コメントなどを含みます）。実装は、水平行+左右+上下配置戦略でのみ機能します。

したがって、この+700行のコードを他の7つの配置戦略オプションで機能させる方法を追加するか、これらの+700行のコードを他の7つのオプションで複製する必要があります。これらはどちらも魅力的ではありません。1つ目は既存のコードが十分に複雑であるため、2つ目は肥大化のためです。

機能が不足しているため、アルゴリズムはリアルタイムの最悪のシナリオで使用できる段階にさえありません。そのため、最初のアプローチよりも実際にパフォーマンスが良いか悪いかはわかりません。

このアルゴリズムのC実装の現在の状態はfreespace.cです。私はこれgcc -O0 -ggdb freespace.cをビルドして、少なくとも124x60文字のxtermサイズで実行するために使用します。

他には何があるの？

私はざっと目を通し、割引しました：

• ビンパッキングアルゴリズム：最適な適合に重点を置いているため、このアルゴリズムの要件と一致しません。

• 再帰的二分配置アルゴリズム：有望に聞こえますが、これらは回路設計用です。それらの重点は、最適なワイヤ長です。

これらの両方、特に後者では、アルゴリズムが開始する前に、配置/パックされるすべての要素がわかっています。

これについてどう思いますか？どのようにアプローチしますか？他にどのようなアルゴリズムを検討する必要がありますか？または、コンピュータサイエンス/ソフトウェアエンジニアリングを勉強したことがないので、どのような概念を調べればよいでしょうか。

さらに情報が必要な場合は、コメントで質問してください。

この質問をして以来、さらなるアイデアが生まれました

• 私の「代替アルゴリズム」と、配置する大きなウィンドウが空きスペースのいくつかのブロックをカバーするかどうかを識別するための空間ハッシュマップのいくつかの組み合わせ。

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
};

編集

ここに写真があります：

2 つのブロックの例を示します。色付きの点はブロックの角を示し、そこから発する矢印はその角からの最大自由四角形の範囲を示します。

編集で、ウィンドウが配置されるグリッドはすでにかなり粗い (127x127) と述べたので、ブロック サイズはおそらく 4 つのグリッド セルのようなものになるでしょう。この方法は、ウィンドウのコーナー座標が多くの値を取ることができる場合に適しています (ピクセルになると思っていました) が、あなたの場合はそれほどではありません。簡単なのでまだまだ挑戦できます。また、完全に空のブロックのリストを保持して、2 ブロック幅を超えるウィンドウが表示された場合に、ブロック グリッドで適切な空きスペースを探す前に、そのリストを最初に確認するようにすることもできます。

Answer 2

いくつかの誤ったスタートの後、私は最終的にここにたどり着きました。ここでは、空き領域の長方形領域を格納するためのデータ構造の使用が放棄されています。代わりに、128 x 128 要素の 2 次元配列を使用して同じ結果を得ることができますが、複雑さが大幅に軽減されます。

次の関数は、サイズの領域について配列をスキャンし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;
}

2 次元配列はゼロで初期化されます。スペースが使用されている配列内の領域はすべて 1 に設定されます。この構造体と関数は、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コンパイルに使用)

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_ARRAYUSE_32BIT_ARRAYUSE_16BIT_ARRAYUSE_8BIT_ARRAYunsigned 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) でのみテストされています。