1

私は今Androidアプリケーションを開発しています。そして、多くの入力を多くのデータに等しくするための最良のアルゴリズムを作成できないため、アプリの1つの重要な方法で問題が発生しました。

シナリオは次のとおりです。メソッドの入力はオーバーライドメソッドからの座標でonTouchEvent()あるため、画面に触れて指を動かすと、入力が非常に多くなります。私はその非常に多くの座標を配列内の24の値と同一視する必要があります。配列の値も座標です。したがって、入力の値が配列の値と同じである場合、ポイントを獲得します。

これが私が使用したコードです：

public void checkCoordinate(float x, float y){
    int sensitivity = 30; 
    for(int z = 0; z < 24; z++){
        if(x > (cxy[z][0]-sensivity) && x < (cxy[z][0]+sensivity) && y > (cxy[z][1]-sensivity) && y < (cxy[z][1]+sensivity)){
            points += 1; 
            Log.i("CheckCoordinate", "Total Points = "+points); 
    }
}

私はそれを同等にする2つの方法があります。1つは、上記のアルゴリズムを使用するか、すべての入力をチェックする場合は24を使用します。しかし、この場合、2つの方法が良いとは思いません。だから、あなたが私のものと同じケースを持っていて、あなたがそれを解決したか、あなたがより良いまたは最良の解決策を持っているなら、私はあなたの助けが必要です私に教えてください。

前もって感謝します。私の英語が下手ならごめんなさい。

4

2 に答える 2

1

そうは言っても、あなたの一般的な考えは正しいです。問題は、それをどうにかして最適化できるかということです。

ここで採用できる可能性のある方法はたくさんあります。秘訣は、データを整理する方法にあります。現在のケースでは、感度変数をスパンとして中心点を実行しています。最初の最適化は、中心点から左右に上下に移動する感度を使用する代わりに、左上の点から左右にのみ移動するスパンを持つ左上の点を実装することであると想像できます。その場合、ifステートメントは次のようになります。

if(x > cxy[z][0] && x < (cxy[z][0]+sensivity) && y > cxy[z][1] && y < (cxy[z][1]+sensivity))

それで、これはあなたのために何をしますか：この上記の最適化はあなたが同じ全体量のデータを保持することを可能にしますが、チェックごとに2つの数学演算を取り除きます。入力パラメータが両方とも浮動小数点であることを考慮すると、これによりかなりの時間を節約できます。

すべてのピクセルベースの操作を実行している場合は、次の最適化に進みます。浮動小数点の代わりに整数を使用してすべての計算を実行します。これにより、アルゴリズム全体の時間が大幅に短縮されます。

さらに最適化すると、パフォーマンスを向上させるためにより多くのRAMを使用する場合は、リージョンごとに1ポイントを設定する代わりに、リージョンごとに左上と右下のポイントを設定できます。これにより、ifステートメントは次のようになります。

if(x > tlxy[z][0] && x < brxy[z][0] && y > tlxy[z][1] && y < brxy[z][1])

where tlxy is the array of top-left points, brxy is the array of bottom-right points
and z is still the "region" you are checking against

これはどのように役立ちますか：上記のifステートメントでわかるように、これには明示的な数学演算がまったくありません。このアルゴリズムをサポートするには、配列cxyの元の2倍のメモリを使用する必要があります。

これでループ内で、24のリージョンポイントすべてを通過します。どのリージョンもオーバーラップしていないことを確実に知っている場合、ポイントは実際には一度に1つのリージョンにしか分類できません。ポイントをインクリメントするポイントでforループを解除することにより、ほとんどのxy入力ポイントで時間を節約できます。これは次のようになります。

public void checkCoordinate(float x, float y){
    for(int z = 0; z < 24; z++){
        if(x > tlxy[z][0] && x < brxy[z][0] && y > tlxy[z][1] && y < brxy[z][1]){
            points += 1; 
            break;
        }
    }
}

上記は、重複する領域がない（エッジさえない）ことが確実にわかっている場合にのみ機能します。

最終的な最適化では、可能性があることがわかります。リージョンがどのように見えるかに応じて、すべてのリージョンを象限に事前に分離することができます。このようにして、xポイントが画面の左側または右側にあるかどうかをテストしてから、yポイントが上部または下部にあるかどうかをテストできます。リージョンの分布がかなり均一である場合、象限内のリージョンをテストする必要があるだけでなく、テスト時間を4短縮できる可能性があります（指定された統計分布が私が言ったことである場合）。最悪の場合、すべての領域が単一の象限にあり、テストするすべてのポイントがその象限にあります。この場合、複雑さの観点からの問題は以前よりも悪くはありません。入力xとyにセットアップテストを追加するだけです。

これで、少なくとも途中で始めるのに十分な情報が得られることを願っています!!!

于 2012-06-19T02:32:41.177 に答える
0

24 個の値の場合、これはやり過ぎかもしれませんが、プレーン配列ハッシュ テーブルの使用を検討することもできます(オープン アドレッシングの衝突解決を使用)。

  1. 簡単にするために、y値を使用してジャンプ位置を取得するとします (領域が垂直方向に十分に分離されている場合、これによりチェックの数が減るはずです)。画面の解像度が 600x800 であると仮定すると y、60 で割ると ~13 のスロットを取得できます。8 ビット テーブルを使用している場合、スロットあたり最大 18 個のアイテムに相当します ( round(800/60)=13、round(255/13)=18)。

  2. 計算を高速化するには、すべてを丸くシンプルに保つ必要があります。これにより、次を使用してスロット番号を取得できます。

    int yi = (int)y;

// this is your "hash function". depending on your actual data,
// you might want to modify it to get a lesser chance of collisions
byte slot = (byte)((yi / 60) * 18);

  3. スロット インデックスを取得したので、ハッシュ テーブルにジャンプして、チェックするアイテムがなくなるまでチェックします。

    rectangle r;
int yi = (int)y;
for (byte slot=(byte)(yi / 26); slot < 256; slot++)
{
    r = hashtable[slot];

    // is this an empty slot?
    if (r.brxy == 0)
       break;

    // perform exact check
    if (r.left < x && x < r.right && 
        r.top < y && y < r.bottom)
       break;
}

  4. 同様の方法で初期化中にハッシュ テーブルを作成する必要があります。24 のリージョンごとに、そのハッシュ (スロット) インデックスを計算します。ハッシュ テーブルの位置が占有されている場合は、空の場所が見つかるまで単純に 1 ずつ増やします。注: 重複するすべてのスロットに各リージョンを追加する必要があります。最も簡単な方法は、スロットsに追加することです。s-1s+1

現在、ループは平均で12 回のルックアップを実行しますが、ハッシュベースのアプローチでは 1 回のハッシュ計算が実行され、平均で 2 ～ 3 回のルックアップしか必要ありません (ハッシュ テーブルはO(1)、適切なハッシュ関数を前提として、平均して複雑であると言われています)。

例

理想hashtable的には次のようになります。

hashtable[0]: rectangle(0, 0, 60, 60);
hashtable[1]: rectangle(20, 20, 80, 80);
hashtable[2]: (empty)
hashtable[3]: (empty)
...
// next slot starts at [18]
hashtable[18]: rectangle(20, 20, 80, 80); // this region is in slots 0 and 1
hashtable[19]: rectangle(30, 70, 90, 130);
hashtable[20]: rectangle(400, 70, 460, 130);
hashtable[21]: (empty)
...

したがって、タッチポイントがの場合(430, 100)、計算は次のように続行されます。

a) slot = (byte)((100/60) * 18) = 18;
b) check hashtable[18], overlapping? no
c) check hashtable[19], overlapping? no
c) check hashtable[20], overlapping? yes, found after 3 checks

パフォーマンスは、選択したハッシュ関数のみに依存します。

x座標が似ているアイテムが多数ある場合、一部のスロットで多くの衝突が発生する可能性があります。そのため、適切なハッシュ関数を選択することが重要です。領域が固定されている場合は、完全なハッシュを作成することもできます.

于 2012-06-19T10:35:08.980 に答える