我試圖比較兩個列表的集合(或列表列表),并且正在努力尋找有效的解決方案。給出的是兩個具有不同長度的列表,并且每個位置可能具有不同的大小集。集合的大小介于 1-6 個整數之間,列表的大小大約為 4000 個元素(較大的元素)和 100 個元素(較小的元素)。list_1= [{42, 189, 31}, {32, 75, 189}, {42, 31}, {100, 63}, {75, 37}]
list_2=[{75, 37}, {42, 37}]然后,我想在數組中找到兩個列表之間重疊最大的點,并計算每個集合之間的交集有多少個元素。在這種情況下,最好的對齊方式是list_1[1:3],其中有兩個重疊的元素{32, 75, 189} 在 list_1 的索引 1 和 {75, 37} 在 list_2 的索引 0 與 {42, 31} 在 list_1 的索引 2 和 {42, 37} 在索引 1 的 list_2 給出計數 2,因為我們有兩個匹配項。對于上面的示例,輸出數組應如下所示sequence_alligenment(list_1,list_2): [0,2,0,1]列表的順序很重要,因為這樣,我試圖找到重疊最大的時間點。我一直在嘗試使用集合和凍結集的交集,但由于它們周圍有一些笨拙的for循環,所以沒有太多的運氣。
3 回答

蕪湖不蕪
TA貢獻1796條經驗 獲得超7個贊
如果你需要效率(如果你需要經常使用這個代碼,并且有時等待它),你可能會使用模糊匹配算法。
大多數模糊匹配算法似乎都針對字符串,但它們可能是一個起點。
如果這不是您要查找的內容,您可以嘗試執行反向索引,例如:{42: {42, 189, 31}, 189: {{42, 189, 31}}, 31: {42, 189, 31}, 32: {32, 75, 189}, 75: {32, 75, 189}, 189: {32, 75, 189}, 42: {42, 31}, 31: {42, 31}, 100: {100, 63}, 63: {100, 63}, 75: {75, 37}, 37: {75, 37: {75, 37}}
然后以這種方式計算在任何兩對之間得到的重復項數。我相信它會是O(n)那樣。
添加回答
舉報
0/150
提交
取消