两个数据集之间 n 到 m 映射的高效算法
Efficient algorithm for n to m mapping between two data sets
我的一侧有 3 组动态元素。例如
a = [101,102,104] //possible values 101 to 115
b = [201,202] //possible values 201 to 210
c = [301,302,303,304] //possible values 301 to 305
我生成了这 3 组的所有组合，例如
setA = ["101|201|301,303", "101,104|202|304", "101,104|202|301,304", ...]
a,b,c 此时不在画面中。现在我想将 setA 的所有元素与另一个集合 setB 进行匹配，该集合 setB 每个类别只有一个元素。例如
setB = ["101|202|304","104|202|301" ,"102|202|303", ...]
setA 和 setB 之间存在 n 到 m 的映射。即 setA 中的一个组合可以在 setB 中有多个匹配项，反之亦然。
匹配条件：对于setB的任何元素（例如“101|202|304”）如果其所有部分（101,202,304）都包含在setA的某些组合中（例如“101,104|202|304”，“101,104” |202|301,304") 然后将其视为匹配项。所以在这个例子中，“101|202|304”被认为与“101,104|202|304”和“101,104|202|301,304”都匹配
目前我有 O(n^2) 时间和 O(n) space 算法，但我真的在寻找一些改进，因为这个计算对许多这样的集合重复。 （这实际上是 hadoop map-reduce 的缩减程序任务，我在其中生成所有符合给定组合的维度和聚合度量的组合）。也欢迎任何框架级别的优化。例如在多项工作中分解工作。
问题不清楚，如果我理解正确的话，我会这样解决：
- setA 对我来说不存在。
- a、b、c 也不在画面中。
我首先在 "setB" 中选择一个公共元素（在您的示例中为 202），对于其余元素（101、102、104、201、301、302 等），我将迭代 4他们每个人的状态：
- 0 = 不在集合 B
- 1 = 它在 setB
的第一个 "entry"
- 2 = 它在 setB
的第二个 "entry"
- 3 = 它在 setB 的两个条目中
我假设 setB 总是有 2 "entries"。
通过 B 并挑选出您拥有的所有第一个元素，将它们重新组合成一个集合。对于该集合中的每个元素，制作一个从该元素到 B 中以该元素开头的所有内容的映射。现在你有一张地图：firstElement -> subsetOfBStartingWithThat.
现在对子集和第二个元素等做同样的事情，直到你有一系列的地图
firstElement -> secondElement -> thirdElement -> ... -> entry in B.
现在您 运行 浏览 A 中的每个条目，并使用地图判断那里是否有任何东西。如果是，请将其添加到集合中。如果否，请将其留空。使用它来构建从 A 的元素到 B 的元素集的映射。
然后通过遍历 A -> B 映射并以相反方向添加对来制作从 B 到 A 集合的映射，从而反转该过程。
您有 O(m) space 来创建 B-lookup-map，并且您将花费 O(m+n) 时间进行扫描，因为集合查找是线性的。构建最终查找集将花费 space（和时间）与 m * n/2^k 成正比，其中 k 是独立集的数量（在您的情况下为 3）。没有办法避免这种情况：这实际上是有多少链接。 （要了解原因，请注意，每个源集的每个元素都可以看作是打开或关闭的位，并且您需要该位打开。这种情况只发生 1/2^k 次，即你的情况是 1/8。
所以您几乎停留在 n^2 步骤。除非您不需要全面，否则它是问题所固有的。如果没有，您可以使用我上面概述的方案来找到 a 匹配成本要低得多。
解决方案与 Rex Kerr 略有不同。首先，我从 setB 元素创建了一个 mapB。在我的用例中，每个元素都完全代表一个键和关联的值是不同的度量。
然后，我迭代了 setA 的每个子元素。从每个元素创建 3 个子列表，并以某种方式迭代每个子列表以获取一个键（3 个嵌套用于 loops）。我在 mapB 中查找了那个键。如果找到，我将 mapB 值计入此组合。因此，在所有迭代结束时，我从 setB 中聚合了符合给定 setA 组合的值。而已。让我知道是否有人希望我对此进行更详细的说明。
ps - 我的工作 运行 通过此更改快了 4 倍（从 7 小时变成 2 小时）
我的一侧有 3 组动态元素。例如
a = [101,102,104] //possible values 101 to 115
b = [201,202] //possible values 201 to 210
c = [301,302,303,304] //possible values 301 to 305
我生成了这 3 组的所有组合，例如
setA = ["101|201|301,303", "101,104|202|304", "101,104|202|301,304", ...]
a,b,c 此时不在画面中。现在我想将 setA 的所有元素与另一个集合 setB 进行匹配，该集合 setB 每个类别只有一个元素。例如
setB = ["101|202|304","104|202|301" ,"102|202|303", ...]
setA 和 setB 之间存在 n 到 m 的映射。即 setA 中的一个组合可以在 setB 中有多个匹配项，反之亦然。
匹配条件：对于setB的任何元素（例如“101|202|304”）如果其所有部分（101,202,304）都包含在setA的某些组合中（例如“101,104|202|304”，“101,104” |202|301,304") 然后将其视为匹配项。所以在这个例子中，“101|202|304”被认为与“101,104|202|304”和“101,104|202|301,304”都匹配
目前我有 O(n^2) 时间和 O(n) space 算法，但我真的在寻找一些改进，因为这个计算对许多这样的集合重复。 （这实际上是 hadoop map-reduce 的缩减程序任务，我在其中生成所有符合给定组合的维度和聚合度量的组合）。也欢迎任何框架级别的优化。例如在多项工作中分解工作。
问题不清楚，如果我理解正确的话，我会这样解决：
- setA 对我来说不存在。
- a、b、c 也不在画面中。
我首先在 "setB" 中选择一个公共元素（在您的示例中为 202），对于其余元素（101、102、104、201、301、302 等），我将迭代 4他们每个人的状态：
- 0 = 不在集合 B
- 1 = 它在 setB 的第一个 "entry"
- 2 = 它在 setB 的第二个 "entry"
- 3 = 它在 setB 的两个条目中
我假设 setB 总是有 2 "entries"。
通过 B 并挑选出您拥有的所有第一个元素，将它们重新组合成一个集合。对于该集合中的每个元素，制作一个从该元素到 B 中以该元素开头的所有内容的映射。现在你有一张地图：firstElement -> subsetOfBStartingWithThat.
现在对子集和第二个元素等做同样的事情，直到你有一系列的地图
firstElement -> secondElement -> thirdElement -> ... -> entry in B.
现在您 运行 浏览 A 中的每个条目，并使用地图判断那里是否有任何东西。如果是，请将其添加到集合中。如果否，请将其留空。使用它来构建从 A 的元素到 B 的元素集的映射。
然后通过遍历 A -> B 映射并以相反方向添加对来制作从 B 到 A 集合的映射，从而反转该过程。
您有 O(m) space 来创建 B-lookup-map，并且您将花费 O(m+n) 时间进行扫描，因为集合查找是线性的。构建最终查找集将花费 space（和时间）与 m * n/2^k 成正比，其中 k 是独立集的数量（在您的情况下为 3）。没有办法避免这种情况：这实际上是有多少链接。 （要了解原因，请注意，每个源集的每个元素都可以看作是打开或关闭的位，并且您需要该位打开。这种情况只发生 1/2^k 次，即你的情况是 1/8。
所以您几乎停留在 n^2 步骤。除非您不需要全面，否则它是问题所固有的。如果没有，您可以使用我上面概述的方案来找到 a 匹配成本要低得多。
解决方案与 Rex Kerr 略有不同。首先，我从 setB 元素创建了一个 mapB。在我的用例中，每个元素都完全代表一个键和关联的值是不同的度量。
然后，我迭代了 setA 的每个子元素。从每个元素创建 3 个子列表，并以某种方式迭代每个子列表以获取一个键（3 个嵌套用于 loops）。我在 mapB 中查找了那个键。如果找到，我将 mapB 值计入此组合。因此，在所有迭代结束时，我从 setB 中聚合了符合给定 setA 组合的值。而已。让我知道是否有人希望我对此进行更详细的说明。
ps - 我的工作 运行 通过此更改快了 4 倍（从 7 小时变成 2 小时）