假设您有一个三元组列表,其特征是它们之间的依赖关系定义如下:三元组的最后一个元素指定";等级;第二个元素标识层次结构内的三元组的"n"的另一个三元组;占主导地位";有问题的一个,具有更高的秩n-1。这样你就可以为列表的每个三元组生成一个路径,例如,具有以下形式:
50152,3->152,49,2->49,3,1->3,空,0
6921642,1->1642,NULL,0
目标是,给定这样一个依赖层次结构所在的列表,输出所有可能获得的路径给定起始三元组。
有没有一种方法可以在对整个列表进行最少的完整阅读的情况下做到这一点?
一种想法是读取列表一次,为每个等级创建一个字典,然后再次扫描列表,并在相关联的三元组的较高级别的相应字典中报告路径检查。
但就用于排名的数据结构而言,这是昂贵的:
一种不同的方式是假设列表中的排序,例如,三元组50152,3后面是索引152152,49,2的三元组,并且最后一个三元组后面是索引49的三元组。这应该允许只使用一个包括整个列表的数据结构来获得结果,并且对于每个元素,检查与元组第二位标识的索引相关的元素。如果订单不存在,我们需要将其强行添加到列表中,并为此创建密钥。
对于这个问题,还有其他更有效的解决方案吗?
我认为您可以通过读取列表并维护从索引到相关路径的映射来实现这一点。例如,对于列表
<code>[50, 152, 3]
[49, 3, 1]
[3, null, 0]
[692, 1642, 1]
[1642, null, 0]
</code>
你的地图应该是
<code>{
0: [50, 152, 3, 49, 3, 1, 3, null, 0],
1: [3, null, 0],
3: [50, 152, 3, 49, 3, 1, 3, null, 0],
692: [692, 1642, 1, 1642, null, 0],
1642: [692, 1642, 1, 1642, null, 0]
}
</code>