在 java 中有效地连接 2 个节点列表
Connecting 2 lists of nodes efficiently in java
我正在构建一个流网络，我有两个列表，其中包含具有关联属性的节点。我必须根据这些属性连接两个列表。
我现在正在做的是遍历列表 A 并为每个元素遍历列表 B 的所有元素并连接至少有 1 个匹配的节点 属性。这意味着我必须为列表 A 中的每个元素访问列表 B 中的所有节点一次。
有没有更快的方法连接两个列表？
也许保留一个包含所有属性的矩阵，然后只处理 属性 的列并基于该列进行连接？会占用更多内存。
编辑：对于这个问题，两个列表都包含具有技能列表（比如 1、2、3）的节点，然后我需要使用该技能将列表 a 的节点连接到列表 b 的同一节点。
编辑：
我现在给人们一堆技能和所有工作所需技能的哈希集。
然后我弹出一项技能并遍历所有工作，如果它包含一项技能我将两者连接起来。
在不深入研究语言的情况下，这里有一些关于算法的思考。
在某些特殊情况下，您可以根据您的属性对列表进行预处理来改进这一点。
例如，假设您的节点有 2 个属性：一个 id (int) 和一个权重，并且您需要匹配 id。然后作为预处理，您可以根据您的 id
对两个列表 A 和 B 进行排序
=> 复杂度：O(nA.log(nA)) + O(nB.log(nB))
之后，您将在具有 2 个索引的 2 个列表之间进行匹配，并且每个列表仅迭代一次。假设您按 id 升序排序，在每一步中，您有 xA、iA 排序列表的第 sortA 个元素，id 为 idA 和 xB, iB - 已排序列表 sortB 的第一个元素，id idB 和 :
- 如果
idA = idB 匹配，则执行 iA++ 和 iB++
- 如果
idA > idB没有匹配，则执行iB++
- 如果
idA < idB 没有匹配，执行 iA++
=> 复杂度：O(nA + nB)
=> 总复杂度：O(nA + nB) + O(nA.log(nA)) + O(nB.log(nB))。蛮力复杂度为 O(nA.nB)
您可能会找到其他方法来根据您的属性预处理列表：
- 也许您有办法对列表进行全部或部分排序？
- 也许您可以 organize/store 您的属性或检查任何有用的树结构，以便您改进比较工作流程，并减少列表 A 中每个节点访问列表 B 的节点？[=80= ]
- 也许您可以根据您的属性计算一些类似哈希码的 属性，以便您可以轻松匹配您的匹配检查？
- 也许您有任何方法来隔离已经匹配的节点（如果在您的情况下有意义），以减小列表 B 的大小？
- 也许还有其他原因？
这里的关键是，如果你分成多个步骤，你可以在最后节省时间，因为在你的复杂性中加法而不是乘法
希望对你有帮助
PS：在某些情况下，您还可以存储更多内容并通过增加 space-复杂度来节省时间复杂度。因此，您可以预处理列表的多个方面，但您需要存储更多数据 -> 您的选择也取决于您的约束
编辑（整合评论）：
使用更多space（我不知道你有多少技能，有多少space可以用来存储预处理的东西）：你可以为每个技能计算一个列表，contaning the id每个具有此技能的候选人（您可以将所有这些存储到 HashMap> 中）需要 O(nCandidates) 来填充所有这些列表（仅一次迭代）。
例如：
- skill1 : [candidate1, candidate2]
- 技能2：[候选人1，候选人3，候选人4，候选人5]
- skill3 : [candidate1, candidate2, candidate3, candidate5]
- skill4 : [candidate2, candidate3, candidate5]
然后对于每一个工作，你都选择匹配第一个技能的候选人，用他们过滤第二个技能的候选人列表，等等，直到最后一个技能，你得到匹配所有技能的所有候选人的列表。
从理论上讲，每项工作仍然是 O(nCandidates)，但在 "real life" 中，您可以将候选人最少的技能作为第一技能，并迭代增加候选人数量的技能，这样它就会少于 O(nCandidates )
例如，对于之前的列表，以及需要技能 1、技能 3 和技能 4 的工作，您将拥有：
- step : skill selected : candidates for this skill => remaining candidates
- 第 1 步：技能 1：[候选人 1，候选人 2] => [候选人 1，候选人 2]
- 第 2 步：技能 4：[候选人 2，候选人 3，候选人 5] => [候选人 2]
- 第 3 步：技能 3：[候选人 1，候选人 2，候选人 3，候选人 5]=>[候选人 2]
=> 操作：在[candidate1, candidate2]中寻找candidate1和candidate2 + 在[candidate2, candidate3, candidate5]中寻找candidate1和candidate2 + 在[candidate2, candidate3, candidate5]中寻找candidate2
可以反过来做同样的事情（候选人 -> [技能]）让职位与候选人的技能相匹配
我正在构建一个流网络，我有两个列表，其中包含具有关联属性的节点。我必须根据这些属性连接两个列表。
我现在正在做的是遍历列表 A 并为每个元素遍历列表 B 的所有元素并连接至少有 1 个匹配的节点 属性。这意味着我必须为列表 A 中的每个元素访问列表 B 中的所有节点一次。
有没有更快的方法连接两个列表？
也许保留一个包含所有属性的矩阵，然后只处理 属性 的列并基于该列进行连接？会占用更多内存。
编辑：对于这个问题，两个列表都包含具有技能列表（比如 1、2、3）的节点，然后我需要使用该技能将列表 a 的节点连接到列表 b 的同一节点。
编辑： 我现在给人们一堆技能和所有工作所需技能的哈希集。 然后我弹出一项技能并遍历所有工作，如果它包含一项技能我将两者连接起来。
在不深入研究语言的情况下，这里有一些关于算法的思考。
在某些特殊情况下，您可以根据您的属性对列表进行预处理来改进这一点。
例如，假设您的节点有 2 个属性：一个 id (int) 和一个权重，并且您需要匹配 id。然后作为预处理，您可以根据您的 id
对两个列表 A 和 B 进行排序=> 复杂度：O(nA.log(nA)) + O(nB.log(nB))
之后，您将在具有 2 个索引的 2 个列表之间进行匹配，并且每个列表仅迭代一次。假设您按 id 升序排序，在每一步中，您有 xA、iA 排序列表的第 sortA 个元素，id 为 idA 和 xB, iB - 已排序列表 sortB 的第一个元素，id idB 和 :
- 如果
idA = idB匹配，则执行iA++和iB++ - 如果
idA > idB没有匹配，则执行iB++ - 如果
idA < idB没有匹配，执行iA++
=> 复杂度：O(nA + nB)
=> 总复杂度：O(nA + nB) + O(nA.log(nA)) + O(nB.log(nB))。蛮力复杂度为 O(nA.nB)
您可能会找到其他方法来根据您的属性预处理列表：
- 也许您有办法对列表进行全部或部分排序？
- 也许您可以 organize/store 您的属性或检查任何有用的树结构，以便您改进比较工作流程，并减少列表 A 中每个节点访问列表 B 的节点？[=80= ]
- 也许您可以根据您的属性计算一些类似哈希码的 属性，以便您可以轻松匹配您的匹配检查？
- 也许您有任何方法来隔离已经匹配的节点（如果在您的情况下有意义），以减小列表 B 的大小？
- 也许还有其他原因？
这里的关键是，如果你分成多个步骤，你可以在最后节省时间，因为在你的复杂性中加法而不是乘法
希望对你有帮助
PS：在某些情况下，您还可以存储更多内容并通过增加 space-复杂度来节省时间复杂度。因此，您可以预处理列表的多个方面，但您需要存储更多数据 -> 您的选择也取决于您的约束
编辑（整合评论）： 使用更多space（我不知道你有多少技能，有多少space可以用来存储预处理的东西）：你可以为每个技能计算一个列表，contaning the id每个具有此技能的候选人（您可以将所有这些存储到 HashMap> 中）需要 O(nCandidates) 来填充所有这些列表（仅一次迭代）。
例如：
- skill1 : [candidate1, candidate2]
- 技能2：[候选人1，候选人3，候选人4，候选人5]
- skill3 : [candidate1, candidate2, candidate3, candidate5]
- skill4 : [candidate2, candidate3, candidate5]
然后对于每一个工作，你都选择匹配第一个技能的候选人，用他们过滤第二个技能的候选人列表，等等，直到最后一个技能，你得到匹配所有技能的所有候选人的列表。 从理论上讲，每项工作仍然是 O(nCandidates)，但在 "real life" 中，您可以将候选人最少的技能作为第一技能，并迭代增加候选人数量的技能，这样它就会少于 O(nCandidates )
例如，对于之前的列表，以及需要技能 1、技能 3 和技能 4 的工作，您将拥有：
- step : skill selected : candidates for this skill => remaining candidates
- 第 1 步：技能 1：[候选人 1，候选人 2] => [候选人 1，候选人 2]
- 第 2 步：技能 4：[候选人 2，候选人 3，候选人 5] => [候选人 2]
- 第 3 步：技能 3：[候选人 1，候选人 2，候选人 3，候选人 5]=>[候选人 2]
=> 操作：在[candidate1, candidate2]中寻找candidate1和candidate2 + 在[candidate2, candidate3, candidate5]中寻找candidate1和candidate2 + 在[candidate2, candidate3, candidate5]中寻找candidate2
可以反过来做同样的事情（候选人 -> [技能]）让职位与候选人的技能相匹配