algorithm - 分析不同的集合和优化。最好的方法？

Question

在过去的几天中，我尝试完成以下有关一组对象的分析的任务，而我提出的解决方案在很大程度上依赖于内存(在某些情况下会获得OutOfMemory异常)，或者花费了不可思议的时间处理时间。我现在认为将其发布在这里是个好主意，因为我没有想法。我将详细解释该问题，并提供到目前为止我所遵循的逻辑。

方案:

首先，我们有一个对象，我们将其命名为单个，其中包含以下属性:

日期

经度-纬度对

其次，我们有另一个对象，我们将其命名为 组，其定义是:
一组满足以下条件的个人:

集合中的所有个人的日期彼此之间均不超过10天。这意味着，如果相互比较，所有个人之间的10天之间不会有差异。

每个对象之间的距离小于Y米。

一个组可以有N> 1个个体，只要每个个体彼此匹配的条件即可。
所有个人都存储在数据库中。
所有组也将存储在数据库中。

任务:

现在，考虑一个新的个人。
系统必须检查新个人是否:

属于现有组

个人现在与其他个人组成一个或多个新组。

笔记:

新个人可以位于多个现有组中，也可以创建多个新组。

“个人”子组是不允许的，例如，如果我们有一个包含“个人” {A，B，C}的组，则不存在包含“{A，B}”，“{A，C}”或“{B，C}”的组。

解决方案(受处理时间和内存的限制)

首先，我们使用匹配初始条件的所有个人过滤数据库。这将输出一个FilteredIndividuals枚举，其中包含我们知道将与新的个人组成一个(共2个)的所有个人。

Briefly, a Powerset is a set that contains all the possible subsets of a particular set. For example, a powerset of {A,B,C} would be: {[empty], A, B, C, AB, AC, BC, ABC}

注意:Powerset将输出具有2 ^ N个组合的新集合，其中N是原始集合的长度。

使用电源集的想法如下:

首先，我们创建FilteredIndividuals列表的幂集。这将提供FilteredIndividuals列表中所有组的所有可能组合。出于分析目的和定义，我们可以忽略其中少于2个人的所有组合。

我们检查幂集组合中的每个“个人”是否彼此匹配。
如果它们匹配，则意味着该组合中的所有个人与新的个人形成一个组。然后，为避免子组，我们可以消除包含Checked组合的所有子集。为此，我创建了Checked组合的幂集，然后从原始组合中删除了新的幂集。

至此，我们有了一组符合条件的组列表，以形成一个组。

在正式创建组之前，我将数据库与其他现有组进行比较，这些现有组包含与新集合相同的元素:
如果找到匹配项，则删除新创建的集合，然后将新的Individual添加到旧的Group。
如果找不到匹配项，则表示它们是新的网上论坛。因此，我将新的Individual添加到集合中，最后创建新的Groups。

当FilteredIndividuals的枚举数少于52个时，此解决方案效果很好。之后，将引发内存异常(我知道这是由于数据类型允许的最大大小，但是对于很大的集合，增加此类大小没有帮助。请考虑一下，与条件I'匹配的个人的最高数量ve是345)。

注意:我可以访问两个实体的定义。如果有一个新属性可以减少处理时间，则可以添加它。

我正在使用带有C#的.NET框架，但是如果语言需要更改，我们可以接受，只要以后可以将结果转换为主系统可以理解的对象即可。

Answer 1

All individuals in the set have a date which, within each other, is not superior to 10 days. This means that all of the Individuals, if compared within each other, don´t differ in 10 days between each other. The distance between each object is less than Y meters.

因此，您的问题就变成 ，如何将这些点聚集在3-space (一种 partitioning)中，其中X和Y是您的经度和纬度，Z是时间坐标，而度量标准是 Manhattan distance的适当缩放比例。具体来说，您可以缩放Z，以便10 * Z天等于您的Y米的最大距离。

一种可能的捷径是使用Divet et Impera并将您的积分(个人)分类到宽Y米，高10天的水桶中。您可以通过将其坐标除以Y和10天来做到这一点(可以使用儒略日期)。如果某个人位于存储桶H {X = 5，Y = 3，Z = 71}中，那么它不能超过X <(5-1)或X>(5 + 1)，Y <( 3-1)或Y>(3 + 1)或Z <(71-1)或Z>(71 + 1)在他的同一个组中，因为它们的距离肯定会高于阈值。这意味着您可以快速选择27个“存储桶”的子集，而只担心其中的那些人。

此时，您可以枚举新个人可能所在的组(如果使用数据库后端，则为 SELECT groups.* FROM groups JOIN iig USING (gid) JOIN individuals USING (uid) WHERE individuals.bucketId IN ( @bucketsId ))，然后将其与您的个人可能由其他个人组成的组进行比较( SELECT individuals.id WHERE bucketId IN ( @bucketsId ) AND ((x-@newX)*(x-@newX)+(y-@newY)*(y-@newY)) < @YSquared AND ABS(z - @newZ) < 10))。

这种方法的性能不是很好(它取决于数据库，并且您至少要在bucketId上建立索引)，但是它的优点是使用了尽可能少的内存。

在某些具有地理扩展名的数据库后端上，您可能希望使用 native 的纬度和经度函数，而不是隐式转换为米。