按照与中心单元格的距离排序单元格
我曾经有人问我一个看起来很简单的问题：
我们怎么能根据距离预先定义的中心单元格来排序一个二维数组中的单元格呢？
这里有一个表格，显示了每个单元格距离预定义中心单元格的远近（中心单元格的值为0）。如果某个单元格的值是n，说明它距离中心单元格有n个单元格远：
+----+----+----+----+----+----+----+----+
| 4 | 4 | 3 | 3 | 3 | 3 | 4 | 4 |
+----+----+----+----+----+----+----+----+
| 4 | 3 | 2 | 2 | 2 | 2 | 3 | 4 |
+----+----+----+----+----+----+----+----+
| 3 | 2 | 1 | 1 | 1 | 1 | 2 | 3 |
+----+----+----+----+----+----+----+----+
| 3 | 2 | 1 | 0 | 0 | 1 | 2 | 3 |
+----+----+----+----+----+----+----+----+
| 3 | 2 | 1 | 0 | 0 | 1 | 2 | 3 |
+----+----+----+----+----+----+----+----+
| 3 | 2 | 1 | 1 | 1 | 1 | 2 | 3 |
+----+----+----+----+----+----+----+----+
| 4 | 3 | 2 | 2 | 2 | 2 | 3 | 4 |
+----+----+----+----+----+----+----+----+
| 4 | 4 | 3 | 3 | 3 | 3 | 4 | 4 |
+----+----+----+----+----+----+----+----+
我通过计算两个点（x1, y1）和（x2, y2）之间的直线距离来解决这个问题，这种计算是在一个欧几里得空间中进行的，然后用一种老派的方法叫“装饰-排序-去装饰”来排序。
最后我得到了这个结果：
import math
boardMaxRow = 8
boardMaxCol = 8
thatAbsurdLargeValue = ( 1 + boardMaxRow + boardMaxCol )
centerCells = ( ( 3, 3 ), ( 3, 4 ), ( 4, 3 ), ( 4, 4 ) )
cellsOrderedFromTheCenter = {}
for row in xrange( boardMaxRow ):
for col in xrange( boardMaxCol ):
minDistanceFromCenter = thatAbsurdLargeValue
for ( centerX, centerY ) in centerCells:
# straight line distance between ( x1, y1 ) and ( x2, y2 ) in an Euclidean space
distanceFromCenter = int( 0.5 + math.sqrt( ( row - centerX ) ** 2 + ( col - centerY ) ** 2 ) )
minDistanceFromCenter = min( minDistanceFromCenter, distanceFromCenter )
cellsOrderedFromTheCenter[ ( row, col ) ] = minDistanceFromCenter
board = [ keyValue for keyValue in cellsOrderedFromTheCenter.items() ]
import operator
# sort the board in ascending order of distance from the center
board.sort( key = operator.itemgetter( 1 ) )
boardWithCellsOrderedFromTheCenter = [ key for ( key , Value ) in board ]
print boardWithCellsOrderedFromTheCenter
输出结果是：
[(3, 3), (4, 4), (4, 3), (3, 4), (5, 4), (2, 5), (2, 2), (5, 3), (3, 2), (4, 5), (5, 5), (2, 3), (4, 2), (3, 5), (5, 2), (2, 4), (1, 3), (6, 4), (5, 6), (2, 6), (5, 1), (1, 2), (6, 3), (1, 5), (3, 6), (4, 1), (1, 4), (2, 1), (6, 5), (4, 6), (3, 1), (6, 2), (7, 3), (4, 7), (3, 0), (1, 6), (3, 7), (0, 3), (7, 2), (4, 0), (2, 0), (5, 7), (1, 1), (2, 7), (6, 6), (5, 0), (0, 4), (7, 5), (6, 1), (0, 2), (7, 4), (0, 5), (0, 7), (6, 7), (7, 6), (7, 7), (0, 0), (7, 1), (6, 0), (1, 0), (0, 1), (7, 0), (0, 6), (1, 7)]
我对自己写了这么多代码来解决一个看似简单的问题感到惊讶。
我想问的是：我能否让这个过程更快一些，或者让代码更简短一些（使用更少的临时变量/函数调用）？
2 个回答
1
更短的代码更简单：
coordinates = [(x,y) for y in range(boardMaxRow)
for x in range(boardMaxCol)]
def dist(A,B):
a,b = A
c,d = B
# real euklidian distance without rounding
return (a-c)**2+(b-d)**2
print list(sorted(coordinates,
key=lambda x: min(dist(x,c) for c in centerCells)))
1
为了让它更简短（并使用稍微不同的标准）：
>>> rows, cols, centerx, centery = 6, 6, 2.5, 2.5
>>> [p[1:] for p in sorted((((x - centerx) ** 2 + (y - centery) ** 2, x, y)
... for x in xrange(rows) for y in xrange(cols)))]
[(2, 2), (2, 3), (3, 2), (3, 3), (1, 2), (1, 3),
(2, 1), (2, 4), (3, 1), (3, 4), (4, 2), (4, 3),
(1, 1), (1, 4), (4, 1), (4, 4), (0, 2), (0, 3),
(2, 0), (2, 5), (3, 0), (3, 5), (5, 2), (5, 3),
(0, 1), (0, 4), (1, 0), (1, 5), (4, 0), (4, 5),
(5, 1), (5, 4), (0, 0), (0, 5), (5, 0), (5, 5)]
为了让它更快：
- 不要计算平方根（就像我上面的代码那样）：用距离的平方来排序和用距离排序效果一样好，而计算平方根是
相对慢不必要的。 - 利用八向对称性：只需排序一个八分之一的区域，然后复制8次。
在评论中，PoorLuzer问：“我也不明白为什么你把centerx和centery初始化为2.5, 2.5。”我希望这个图能让你明白：
PoorLuzer还想知道，既然我们都在使用欧几里得距离公式，为什么我们的标准会不同。其实，我的标准是计算每个方块中心到整个网格中心的距离。例如，对于这8个单元，距离中心的距离是√2.5，大约是1.58：
而PoorLuzer是计算到四个中心方块中最近的那个的欧几里得距离（并将其四舍五入为整数）。对于同样的8个单元，PoorLuzer给出的距离是1：
