sen*_*nic 8 c# algorithm matching
我必须编写一个程序,将10'000'000个实体相互比较.这些实体基本上是数据库/ csv文件中的平行.
比较算法必须非常灵活,它基于规则引擎,最终用户输入规则,每个实体与每个其他实体匹配.
我正在考虑如何将此任务拆分为较小的工作负载,但我还没有找到任何东西.由于规则是由最终用户输入的,因此预先排序DataSet似乎是不可能的.
我现在要做的是将整个DataSet放在内存中并处理每个项目.但这不是很高效,需要大约.20 GB内存(压缩).
你知道如何分割工作量或减少它的大小吗？
谢谢
Sas*_*sha 12
如果您的规则处于最高抽象级别(例如任何未知的比较函数),则无法实现目标.10 ^ 14比较操作将运行很长时间.
如果规则不完全通用,我会看到3种优化不同情况的解决方案:
如果比较是传递的,你可以计算哈希(有人已经推荐过这个),那就去做吧.哈希也可能很复杂,不仅仅是你的规则=).找到好的哈希函数,在许多情况下它可能会有所帮助.
如果实体是可排序的,则对它们进行排序 为此,我建议不要就地排序,而是建立一个项目索引(或ID)数组.如果您的比较可以转换为SQL(我理解您的数据在数据库中),您可以更有效地在DBMS端执行此操作并读取已排序的索引(例如3,1,2,这意味着ID = 3的项目)是最低的,ID = 1在中间,ID = 2是最大的).然后,您只需要比较相邻的元素.
如果事情是值得的,我会尝试使用一些启发式排序或散列.我的意思是我会创建哈希,它不一定唯一地标识相等的元素,但可以将数据集分成组,在这些组之间肯定没有一对相等的元素.然后所有相等的对将在内部组中,您可以逐个读取组,并在不是10 000 000的组中进行手动复杂函数计算,但是例如100个元素.另一个子方法是具有相同目的的启发式排序,以保证相等元素不在数据集的不同结尾.之后,您可以逐个读取元素,并与之前的1000个元素进行比较(已经读取并保留在内存中).我会留下内存,例如1100个元素,每次新的100来时免费最老的100个.这将优化您的数据库读取.如果您的规则包含诸如(Attribute1 = Value1)AND(...)之类的规则,或者像(Attribute1 <Value2)AND(...)之类的规则或任何其他简单规则,则其他实现也是可能的.然后,您可以通过此标准首先进行聚类,然后比较创建的聚类中的项目.
顺便说一句,如果你的规则认为所有10 000 000个元素相等,怎么办？你想获得10 ^ 14个结果对吗？这个案例证明在一般情况下你无法解决这个问题.尝试制定一些限制和假设.