0

さて、ここで興味深い問題があります。x、y座標（正の象限）で満たされたSQLデータベースにテーブルがあり、それぞれに色の値があるとします。つまり、スキーマは<x , y, color>. タスクは、同じ色で可能な最大の正方形を検出することです。私は何時間もこの問題を解決しようとしてきましたが、それにへこみを作ることはできません.

私は解決策を探しているのではなく、ヒントを探しています。

これはすべて、主にさまざまな結合、グループ化、および集計操作を使用して SQL で発生する必要があることに注意してください。いくつかのサンプルコードがいいでしょう。

4

2 に答える 2

2

角だけを同じ色にするように要求する場合は、次のことができます。

top left corner
join top right corner on equal x and color and greater y
join bottom left corner on equal y and color and greater x
join bottom right on equal x, y and color
order by (x1-x2)*(y1-x2) descending
limit 1

もちろん、制限 1 は、とにかくすべての正方形を生成する必要があるため、パフォーマンスに大きな影響はありません。

(color,x,y) および (color,y,x) インデックスを追加することで、(大幅に) 速度を向上させることができます。実行計画はおそらく次のようになります。

(1) full scan for all top left corners
(2) dependent index scan for all top right corners
(3) dependent index scan for all bottom left corners
(4) dependent index scan for the bottom right corner expecting at most one match
(5) (partial) table sort of the entire set of squares (cannot use indexes)
于 2012-10-12T04:27:32.847 に答える
2

問題空間が小さいと仮定すると、たとえば 10x10 (x は 1 から 10 の範囲) としましょう。単純で残忍なアプローチです。

  1. BotLeft: 2 セットの 10 の数字 (Numbersテーブルのサブセットなど) を CROSS JOIN して、すべての可能な正方形 (100 ポイント) の左下隅を取得します。
  2. 右上: 同じ 2 つのセットを CROSS JOIN して、すべてのポイントを再度取得します。
  3. 四角形: 2 つの間の INNER JOIN、BotLeft が左と TopRight の下にある必要がある場所によってフィルタリングされます
  4. 考えられるすべての正方形が与えられたら、最終的に (x,y) 座標が正方形の境界内に収まるデータに結合して、それぞれをテストしますleft <= x <= right。これにより、巨大なセットが生成されます
  5. GROUP BY (左下、右上) を使用して前のセットを折りたたみ、グループ化されたサブセット内の異なる色をテストしますHAVING COUNT(DISTINCT color) = 1。
  6. データセットが完全に満たされていない場合はCOUNT、各正方形のピクセル数 = 見つかったデータ ポイントの数もテストする必要があります。
于 2012-10-12T03:50:26.360 に答える