Python中加入兩個嵌套表

Question

我有一個字符串的兩個嵌套表：

listA = [["SomeString1", "A", "1"], 
     ["SomeString2", "A", "2"], 
     ["SomeString3", "B", "1"], 
     ["SomeString4", "B", "2"]] 


listB = [["OtherString1", "A", "1"], 
     ["OtherString2", "A", "2"], 
     ["OtherString3", "B", "1"], 
     ["OtherString4", "B", "2"]] 

對於A中的每一個名單，我想找到B中的列表，其中(sublistB[1] == sublistA[1]) and (sublistB[2] == sublistA[2])（零索引）。

然後我想將「B」子列表的第一個條目添加到「A」子列表，使得最終的輸出將是：

joined = [["SomeString1", "A", "1", "OtherString1"], 
     ["SomeString2", "A", "2", "OtherString2"], 
     ["SomeString3", "B", "1", "OtherString3"], 
     ["SomeString4", "B", "2", "OtherString4"]] 

甚至更​​好，插入項位置1：

joined = [["SomeString1", "OtherString1", "A", "1"], 
     ["SomeString2", "OtherString2", "A", "2"], 
     ["SomeString3", "OtherString3", "B", "1"], 
     ["SomeString4", "OtherString4", "B", "2"]] 

在python中這樣做的最好方法是什麼？我有一個實現，但有3個嵌套循環，它需要一些時間。 我有一種感覺，map,filter和/或reduce可能有幫助，但不知道如何實現？

請注意，列表不一定在我的示例中整齊排列。

此外，這是非常重要的 - 列表可能不是相同的長度，也不保證每個子列表都包含匹配。如果找不到匹配，我想追加無。

Answer 1

使用字典，以 '索引' 的字符串從listB：

listBstrings = {tuple(lst[1:]): lst[0] for lst in listB} 

這(listB[x][1], listB[x][2])元組映射到listB[x][0]字符串。現在你可以在一個循環中查看這併產生joined：

joined = [[lst[0], listBstrings[lst[1], lst[2]]] + lst[1:] for lst in listA] 

您可能需要使用listBstrings.get((lst[1], lst[2]), '')產生一個默認爲空，如果這兩個元素listB從未存在。總而言之，這需要線性時間O（N + M），其中N和M是輸入列表長度。將它與你的嵌套循環方法相比較，它需要O（N * M）二次方。不同之處在於兩個10個元素的列表每個都採用上述方法進行20次迭代，而對於嵌套循環解決方案中的100個，100個元素採用200次迭代，相對於嵌套取得10.000次迭代等。

演示：

>>> from pprint import pprint 
>>> listA = [["SomeString1", "A", "1"], 
...   ["SomeString2", "A", "2"], 
...   ["SomeString3", "B", "1"], 
...   ["SomeString4", "B", "2"]] 
>>> listB = [["OtherString1", "A", "1"], 
...   ["OtherString2", "A", "2"], 
...   ["OtherString3", "B", "1"], 
...   ["OtherString4", "B", "2"]] 
>>> listBstrings = {tuple(lst[1:]): lst[0] for lst in listB} 
>>> joined = [[lst[0], listBstrings[lst[1], lst[2]]] + lst[1:] for lst in listA] 
>>> pprint(joined) 
[['SomeString1', 'OtherString1', 'A', '1'], 
['SomeString2', 'OtherString2', 'A', '2'], 
['SomeString3', 'OtherString3', 'B', '1'], 
['SomeString4', 'OtherString4', 'B', '2']] 

Answer 2

類似的方法來@MartijnPieters回答，而是用字典生成：

from pprint import pprint 
listA = [["SomeString1", "A", "1"], 
     ["SomeString2", "A", "2"], 
     ["SomeString3", "B", "1"], 
     ["SomeString4", "B", "2"], 
     ["SomeString5", "C", "1"]] 
listB = [["OtherString1", "A", "1"], 
     ["OtherString2", "A", "2"], 
     ["OtherString3", "B", "1"], 
     ["OtherString4", "B", "2"], 
     ["OtherString5", "C", "2"]] 
dictB = dict(((x[1], x[2]), x[0]) for x in listB) 
joined = [ [ a[0], dictB.get((a[1], a[2])), a[1], a[2] ] for a in listA ] 
pprint(joined) 

結果：

[['SomeString1', 'OtherString1', 'A', '1'], 
['SomeString2', 'OtherString2', 'A', '2'], 
['SomeString3', 'OtherString3', 'B', '1'], 
['SomeString4', 'OtherString4', 'B', '2'], 
['SomeString5', None, 'C', '1']] 

我不確定如果使用dict生成器會導致更快的評估，但它可能會節省內存使用。

---

這樣做的另一個變化是使用兩個字典內涵和其中一人的項目迭代：

dictA = dict(((x[1], x[2]), x[0]) for x in listA) 
dictB = dict(((x[1], x[2]), x[0]) for x in listB) 
joined = [ [ v, dictB.get(k), k[0], k[1] ] for k, v in dictA.iteritems() ] 

Prehaps更瞭解pythonistas可以在這兩種不同方法的利弊發表評論（或者我可能會發布另一個問題）。

Answer 3

這裏是我的嵌套循環連接的實現。它包含兩個列表以及兩個包含要加入列的索引的列表。例如：如果要將[1]連接到參數b [2]和a [2]到b [3]，比如參數： join（a，[1,2]，b，[ 2,3]）

listA = [["SomeString1", "A", "1"], 
     ["SomeString2", "A", "2"], 
     ["SomeString3", "B", "1"], 
     ["SomeString4", "B", "2"]] 


listB = [["OtherString1", "A", "1"], 
     ["OtherString2", "A", "2"], 
     ["OtherString3", "B", "1"], 
     ["OtherString4", "B", "2"]] 

def join(a,a_keys,b,b_keys): 
    joined = [] 
    for i,a_rec in enumerate(a): 
     for j,b_rec in enumerate(b): 
      satisfies_keys = True 
      for l in range(0,len(a_keys)): 
       if a[i][a_keys[l]] != b[j][b_keys[l]]: 
        satisfies_keys = False 
      if satisfies_keys: 
       joined.append([a_rec, b_rec]) 
    return joined 

print(join(listA,[1,2],listB,[1,2]))