python - kd树构建排序优化

Question

用 Python 编程语言实现的 kd-tree 的算法构建如下（来自http://en.wikipedia.org/wiki/K-d_tree）：

class Node: pass

def kdtree(point_list, depth=0):

  if not point_list:
    return None

  # Select axis based on depth so that axis cycles through all valid values
  k = len(point_list[0]) # assumes all points have the same dimension
  axis = depth % k

  # Sort point list and choose median as pivot element
  point_list.sort(key=lambda point: point[axis])
  median = len(point_list) // 2 # choose median

  # Create node and construct subtrees
  node = Node()
  node.location = point_list[median]
  node.left_child = kdtree(point_list[:median], depth + 1)
  node.right_child = kdtree(point_list[median + 1:], depth + 1)
  return node

每一步都进行排序。如何减少分拣量？

Answer 1

看起来您只是在排序以围绕中位数进行拆分。相反，您可以实现线性时间选择算法，例如quickselect，然后对point_list. 然后，您根本不需要排序。