如何实现核心外的算法？

Question

我想在数据自动化系统中实现一个并行的聚类算法。我的CPU有12 4GB的RAM，GPU有4GB的内存。我想要的是整个数据集应该在磁盘上，我可以从它中选择数据块，将这些块放在CPU内存中，传递给GPU，在那里进行处理，并将结果存储回磁盘上。原(内存中)算法的步长复杂度为O(logN)，N-> no.数据点。对于外部内存算法，假设M点可以同时放进内存中，那么根据我的说法，运行应该是

(N/M)*(logM)

(N/M) ->等于必须放在内存中的这些点集的数量，并且在每次传递期间，处理它的logM时间。

这个运行时间与磁盘和内存之间的I/O时间有什么关系，也就是说，我是否已经通过使用(N/M)来考虑I/O时间，或者我是否遗漏了什么？这个分析是正确的，还是需要了解更多关于输入/输出的知识才能实现使用外部内存的算法？

Answer 1

I/O时间成本将是基于N的某个数字，因为您最终将从磁盘读取N个对象。因此，它可能包括在您的复杂性估计，假设您的方法“拾取块”是恒定的时间。

记住，这只是告诉你算法的复杂性的一般顺序，以及N的大值在这个复杂性中起最大作用的因素。