我有 1 亿对这种形式:
(point_index, cluster_index)
目标是为每个集群选择(第一个?没关系)m
个点。簇的数量最多为 16k。如何有效地做到这一点?
m
应该很小,<=100。
我的第一次尝试:
- 按
cluster_index
对对进行排序。 - 线性遍历对,如果小于
m
个点 当前簇被选中,然后打印点,否则什么都不做 直到找到下一个集群。
这会产生一个:
O(nlogn)
时间复杂度,其中 n = 100m。但是请注意,我只对实际应用感兴趣,而不是对具有巨大常数的下界感兴趣!该算法将在 javascript 中执行通过笔记本电脑。
最佳答案
具有以下假设的解决方案:
- 没有特定的数据结构,只是一个带簇的点列表
- 集群大小均衡
- 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)
迭代。
关于javascript - 每个簇选取 m 个点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39340743/