javascript - 每个簇选取 m 个点

Question

我有 1 亿对这种形式:

(point_index, cluster_index)

目标是为每个集群选择(第一个？没关系)m 个点。簇的数量最多为 16k。如何有效地做到这一点？

m 应该很小，<=100。

---

我的第一次尝试:

1. 按 cluster_index 对对进行排序。
2. 线性遍历对，如果小于 m 个点当前簇被选中，然后打印点，否则什么都不做直到找到下一个集群。

这会产生一个:

O(nlogn)

时间复杂度，其中 n = 100m。但是请注意，我只对实际应用感兴趣，而不是对具有巨大常数的下界感兴趣!该算法将在 javascript 中执行通过笔记本电脑。

Answer 1

具有以下假设的解决方案:

• 没有特定的数据结构，只是一个带簇的点列表
• 集群大小均衡
• m << n/c 其中n是点数，c是聚类数

根据这些假设，随机取点可以快速得出结果。要进行随机排列，您可以使用@zerkms 算法。

取一个质数 p > n。

clustercount = Array(size = c, filled_with = 0)
i = randint(0, p)
complete = 0
while (complete < c*m) {
   if (clustercount[points[i].cluster] < m) {
      clustercount[points[i].cluster] = 1 + clustercount[points[i].cluster]
      plot(points[i])
      complete = complete + 1
  }
i = i + p % n
}

平均而言，此方法需要 c*log(c) + m * c * log(log(c)) + O(c) 迭代。