0

那么这是一个有趣的问题。假设我在一个 sql db 上有一个表，其中填充了 x,y 坐标（正象限）并且每个都有一个颜色值，即模式看起来像<x , y, color>。任务是检测具有相同颜色的最大可能正方形。我已经尝试解决这个问题好几个小时了，但似乎无法解决这个问题。

我不是在寻找解决方案，而是在寻找提示。

请注意，这一切都必须发生在 SQL 中，主要使用各种连接、分组和聚合操作。一些示例代码会很好。

4

2 回答 2

2

假设您的问题空间很小，假设为 10x10（x 介于 1 和 10 之间），那么一种天真的方法：

  1. BotLeft：CROSS JOIN 两组 10 个数字（比如Numbers表格的子集），为您提供所有可能方块的左下角（100 分）
  2. TopRight: CROSS JOIN 相同的两组再次获得所有分数
  3. Squares：两者之间的 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 回答
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 回答