3

私は 32 の絶対四角形サイズの列挙を持っており、寸法を指定し、列挙の中から最適な近似値を見つける必要があります。

if多くのネストされた と から作成しているスパゲッティ コードよりも優れた (つまり、より読みやすく保守しやすい) 方法はありますelseか?

現時点では、私はちょうど持っています:

enum imgOptsScale {
    //Some relative scales
    w005h005 = 0x8,
    w010h010 = 0x9,
    w020h020 = 0xA,
    w040h040 = 0xB,
    w070h070 = 0xC,
    w100h100 = 0xD,
    w150h150 = 0xE,
    w200h200 = 0xF,
    w320h320 = 0x10,
    w450h450 = 0x11,
    w200h010 = 0x12,
    w200h020 = 0x13,
    w200h070 = 0x14,
    w010h200 = 0x15,
    w020h200 = 0x16,
    w070h200 = 0x17
};
imgOptsScale getClosestSizeTo(int width, int height);

コーディングに取り掛かる前に、助けを求めようと思いました。リソースに制約のあるシステムで実行することになっているコンテナよりもアルゴリズムに興味がありますが、精巧すぎるライブラリから離れることを強調する必要があります。

4

3 に答える 3

2

構造体の配列をいくつか使用して、これにアプローチすると思います。1 つは水平方向の測定用で、もう 1 つは垂直方向の測定用です。

配列を読み取って次に大きいサイズを見つけ、対応するキーを返します。2 つのキーから最終的なボックス メジャーを作成します。(32 では 5 ビットしか許可されないため、これはおそらくあまり理想的ではありません。おそらく、水平に 2.5 ビット、垂直に 2.5 ビットが必要ですが、ここでの私の単純なアプローチでは、水平に 3 ビット、垂直に 3 ビットの 6 ビットが必要です。 .<< 3自由度の低いディメンションの 1 つを使用しても問題ない場合は、リストの 1 つから要素の半分を削除できます (さらに調整することもできます)。両方のディメンションをより適切に表現したい場合は、おそらくこのアプローチが適切でない可能性があるほどの十分なやり直し)。

テストされていない疑似コード:

struct dimen {
    int x;
    int key;
}

struct dimen horizontal[] = { { .x = 10, .key = 0 },
                              { .x = 20, .key = 1 },
                              { .x = 50, .key = 2 },
                              { .x = 90, .key = 3 },
                              { .x = 120, .key = 4 },
                              { .x = 200, .key = 5 },
                              { .x = 300, .key = 6 },
                              { .x = 10000, .key = 7 }};

struct dimen vertical[] = { { .x = 10, .key = 0 },
                           { .x = 20, .key = 1 },
                           { .x = 50, .key = 2 },
                           { .x = 90, .key = 3 },
                           { .x = 120, .key = 4 },
                           { .x = 200, .key = 5 },
                           { .x = 300, .key = 6 },
                           { .x = 10000, .key = 7 }};

/* returns 0-63 as written */
int getClosestSizeTo(int width, int height) {
    int horizontal_key = find_just_larger(horizontal, width);
    int vertical_key = find_just_larger(vertical, height);
    return (horizontal_kee << 3) & vertical_key;
}

int find_just_larger(struct dimen* d, size) {
    int ret = d.key;
    while(d.x < size) {
        d++;
        ret = d.key;
    }
    return ret;
}
于 2012-02-11T00:30:35.820 に答える
2

はい...32の異なるサイズを事前に構築されたバイナリ検索ツリーに配置し、ツリーを再帰的に検索して「最適な」サイズを見つけます。基本的に、現在のノードの四角形の左の子の事前構築された四角形が入力の四角形よりも小さく、現在のノードの四角形が入力の四角形よりも大きい場合、検索を停止します。次に、2 つの間の入力四角形に「最も近い」定義済みの四角形を返します。

再帰的検索が作成するクリーンなコードへの 1 つの優れた追加は、検索時間が線形ではなく対数的であることです。

ところで、事前に定義された最初の四角形の値をバイナリ検索ツリーに挿入する順序をランダム化する必要があります。そうしないと、リンクされたリストのように見える縮退したツリーになり、対数検索時間が得られません。ツリーの高さは、ノード数の対数ではなく、ノード数になるためです。

たとえば、ツリーを長方形の面積で並べ替えた場合 (同じ面積の長方形が 2 つ存在しない場合)、次のようにすることができます。

//for brevity, find the rectangle that is the 
//greatest rectangle smaller than the input
const rec_bstree* find_best_fit(const rec_bstree* node, const rec& input_rec)
{
    if (node == NULL)
        return NULL;

    rec_bstree*  return_node;

    if (input_rec.area < node->area)
        return_node = find_best_fit(node->left_child, input_rec);
    else if (input_rec.area > node->area)
        return_node = find_best_fit(node->right_child, input_rec);

    if (return_node == NULL)
        return node;
}

ところで、ツリーが複雑すぎる場合は、配列またはstd::vector四角形のインスタンスを単純に実行し、 を使用して何らかの基準を使用して並べ替えstd::sort、配列でバイナリ検索を実行することもできます。

于 2012-02-10T23:54:39.567 に答える
1

これが私の提案する解決策です。

enum imgOptsScale {
    notScaled = 0x0,
    //7 relative scales upto = 0x7
    w010h010, w010h025, w010h060, w010h120, w010h200, w010h310, w010h450,
    w025h010, w025h025, w025h060, w025h120, w025h200, w025h310, w025h450,
    w060h010, w060h025, w060h060, w060h120, w060h200, w060h310, w060h450,
    w120h010, w120h025, w120h060, w120h120, w120h200, w120h310, w120h450,
    w200h010, w200h025, w200h060, w200h120, w200h200, w200h310, w200h450,
    w310h010, w310h025, w310h060, w310h120, w310h200, w310h310, w310h450,
    w450h010, w450h025, w450h060, w450h120, w450h200, w450h310, w450h450,
    w730h010, w730h025, w730h060, w730h120, w730h200, w730h310, w730h450
};
//Only call if width and height are actually specified. else 0=>10px 
imgOptsScale getClosestSizeTo(int width, int height) {
    static const int possSizes[] = {10, 25, 60, 120, 200, 310, 450, 730};
    static const int sizesHalfways[] = {17, 42, 90, 160, 255, 380, 590};
    int widthI = 6;
    while (sizesHalfways[widthI - 1] > width && --widthI>0);
    int heightI = 6;
    while (sizesHalfways[heightI - 1] > height && --heightI>0);
    return (imgOptsScale)(8 + 7 * widthI + heightI);
}
于 2012-02-11T01:31:09.373 に答える