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])（注意这里是从0开始计数）。

然后我想把'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可能会有帮助，但我不太确定该怎么用。

需要注意的是，这些列表在我的例子中并不一定是整齐排列的。

还有一点非常重要——这些列表的长度可能不一样，也不能保证每个子列表都有匹配的项。如果找不到匹配项，我希望能添加一个None。

Answer 1

这是我实现的一个嵌套循环连接的方法。它需要两个列表，还有两个其他的列表，这两个列表里包含了要连接的列的索引。举个例子：如果要把a[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]))

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']]

我不太确定使用字典生成器是否会让计算更快，但可能会节省一些内存。

---

另一种变体是使用两个字典推导式，并遍历其中一个的项目：

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() ]

也许更懂Python的人可以评论一下这两种不同方法的优缺点（或者我可能会再发一个问题）。

Answer 3

使用字典来“索引”来自 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]

如果这两个元素在 listB 中从未出现过，你可能需要使用 listBstrings.get((lst[1], lst[2]), '') 来返回一个默认的空字符串。

总的来说，这个方法的时间复杂度是线性的 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']]