python - 从列表集合中查找最相似的列表,在线
问题描述
我有一组列表,每个列表都代表图表上的一条路径:
list1 = [1,2,3,6] # directed edge from 1->2, 2->3, 3->6
list2 = [8,3,5,6]
list3 = [9,1,3,4]
list4 = [7,8,1,4]
我也有图的邻接矩阵。
在每个时间步我都有一个优势:例如时间步 0: [1,2]
,时间步 1: [3,6]
,并且在每个时间步我必须找到最相似的列表,同时考虑到以前的时间步。意思是,最完整的列表。
什么是有效的方法?
我尝试使用一种简单的方法,将传入边缘与每个列表中的每个边缘进行比较,但考虑到我有大量列表,每个列表都有大量边缘,这太慢了。
更新:在每个时间步写一个示例输入和输出。
时间步 0:输入[1,2]
,输出:list1
时间步1:输入[8,3]
,输出:list1, list2 #equally complete
时间步2:输入[3,6]
,输出:list1
更新 2:感谢@Nuclearman,我编写了解决方案(也许是天真?)
list1 = [1,2,3,6] # directed edge from 1->2, 2->3, 3->6
list2 = [8,3,5,6]
list3 = [9,1,3,4]
list4 = [7,8,1,4]
lists_dict = {
'list1' : list1,
'list2' : list2,
'list3' : list3,
'list4' : list4
}
edges = {
'list1' : len(list1) - 1,
'list2' : len(list2) - 1,
'list3' : len(list3) - 1,
'list4' : len(list4) - 1
}
covered_edges = {
'list1' : 0,
'list2' : 0,
'list3' : 0,
'list4' : 0
}
completeness = {
'list1' : covered_edges['list1']/edges['list1'],
'list2' : covered_edges['list2']/edges['list2'],
'list3' : covered_edges['list3']/edges['list3'],
'list4' : covered_edges['list4']/edges['list4']
}
graph = {}
for list_name in lists_dict.keys():
idx = 0
while idx < len(lists_dict[list_name])-1:
node1 = lists_dict[list_name][idx]
node2 = lists_dict[list_name][idx+1]
if node1 in graph.keys(): #if exist
graph[node1][node2] = list_name
else: #if doesnt exist
graph[node1] = {node2: list_name}
idx+=1
times= [[1,2],[3,5],[5,6],[8,1],[7,8]]
for time in times:
edge_in_list = graph[time[0]][time[1]] #list name
covered_edges[edge_in_list] +=1
print(covered_edges)
completeness = {
'list1' : covered_edges['list1']/edges['list1'],
'list2' : covered_edges['list2']/edges['list2'],
'list3' : covered_edges['list3']/edges['list3'],
'list4' : covered_edges['list4']/edges['list4']
}
mx = max(completeness.values())
max_list = [k for k, v in completeness.items() if v == mx]
print(max_list)
print('')
解决方案
尝试使用邻接列表设置作为嵌套散列来表示图形
IE:您可以通过这种方式设置整个示例(不记得这是否是有效的 python):
graph = {
1: {2: [1], 3: [3], 4: [4] },
2: {3: [1] },
3: {6: [1], 5: [2], 4: [3] },
5: {6: [2] },
7: {8: [4] },
8: {3: [2], 1: [4] },
9: {1: [3] },
}
然后,您只需记录每个列表中剩余的数量,并将其存储到具有O(log N)
或更好的 find-min(或 find-max 只需调整键)、查找、添加项目和删除项目的数据结构中。根据您如何定义完整性,您可能需要做一些数学运算。IE:您可能需要存储总边和覆盖边,然后使用[(total - covered) / total, list #]
or 作为数据结构的键。这样,即使有多个具有相同完整性的列表,您也可以快速找到该列表。对于您想要的结果,返回所有具有最高完整性的列表。
上图让您快速确定每条边进入哪个列表,然后在剩余计数中查找该边,并将每个列表的计数减一。IE:你可以看到graph[1][2]
是列表 1,graph[8][3]
是列表 2,graph[3][6]
也是列表 1。
为了性能,您可能还希望保留一组已经看到的边缘并跳过任何已经看到的边缘,尽管这可能需要也可能不需要,并且可能会或可能不会是您想要处理它的方式。
性能与您需要更改的列表数量成正比,使其输出敏感。如果提供的示例继续进行,那么与列表数量相比,您需要为每个传入边更新的列表计数数量可能非常小。如果所有列表中都有E
总边L
并且您需要K
在线处理边并且这些K
边导致处理总A
列表 (A
是一个输出敏感变量,取决于列表之间有多少重叠,您给出的示例的重叠为零每个边缘都有一个与之关联的列表,但不清楚是否会保留更多列表和边缘)。那么性能是O(E + K + AlogL)
我相信的,因为那些A
处理过的列表每个都需要一个log L
查找以查找 + 更新列表计数。E
是构建图所需的预处理。这似乎基本上是最优的,除非有别的东西。可能比O(K*E)
您目前拥有的要好得多,除非您有极高的重叠 ( A
)。
推荐阅读
- java - 高于 Integer.MAX_VALUE 的映射条目
- perl - 在 OpenSSH 中重定向调试输出
- python - 将 Spark Scala 连接语句转换为 Python
- c# - 裁剪图像的一部分
- c# - 如何在TextBoxes中获取所选行的dataGridView的所有列值
- javascript - (反应)侦听由作为道具传播的更改数据列表触发的下拉/选择值更改
- java - 根据单元格值更改单元格背景颜色
- xamarin - Xamarin 表单:IOS 不会加载 webview
- node.js - NodeJS ReactJS 部署的应用程序返回 404
- python - Tensorflow:ImportError:libcudnn.so.7:无法打开共享对象文件:没有这样的文件或目录