如何有效地找到两个列表中匹配元素的索引
How to efficiently find the indices of matching elements in two lists
我正在处理两个大型数据集，我的问题如下。
假设我有两个列表：
list1 = [A,B,C,D]
list2 = [B,D,A,G]
除了 O(n2) 搜索之外，如何使用 Python 高效地找到匹配索引？结果应如下所示：
matching_index(list1,list2) -> [(0,2),(1,0),(3,1)]
无重复
如果您的对象是可散列的并且您的列表没有重复项，您可以创建第一个列表的倒排索引，然后遍历第二个列表。这只遍历每个列表一次，因此是 O(n).
def find_matching_index(list1, list2):
inverse_index = { element: index for index, element in enumerate(list1) }
return [(index, inverse_index[element])
for index, element in enumerate(list2) if element in inverse_index]
find_matching_index([1,2,3], [3,2,1]) # [(0, 2), (1, 1), (2, 0)]
有重复项
您可以扩展之前的解决方案以解决重复问题。您可以使用 set.
跟踪多个索引
def find_matching_index(list1, list2):
# Create an inverse index which keys are now sets
inverse_index = {}
for index, element in enumerate(list1):
if element not in inverse_index:
inverse_index[element] = {index}
else:
inverse_index[element].add(index)
# Traverse the second list
matching_index = []
for index, element in enumerate(list2):
# We have to create one pair by element in the set of the inverse index
if element in inverse_index:
matching_index.extend([(x, index) for x in inverse_index[element]])
return matching_index
find_matching_index([1, 1, 2], [2, 2, 1]) # [(2, 0), (2, 1), (0, 2), (1, 2)]
不幸的是，这不再是 O(n)。考虑输入 [1, 1] 和 [1, 1] 的情况，输出是 [(0, 0), (0, 1), (1, 0), (1, 1)]。因此，根据输出的大小，最坏的情况不能比 O(n^2).
尽管如此，如果没有重复，这个解决方案仍然是O(n)。
Non-hashable 个对象
现在出现了您的对象不可散列但可比较的情况。这里的想法是以保留每个元素的原始索引的方式对列表进行排序。然后我们可以对等于的元素序列进行分组以获得匹配的索引。
由于我们在下面的代码中大量使用 groupby 和 product，所以我制作了 find_matching_index return 一个用于长列表内存效率的生成器。
from itertools import groupby, product
def find_matching_index(list1, list2):
sorted_list1 = sorted((element, index) for index, element in enumerate(list1))
sorted_list2 = sorted((element, index) for index, element in enumerate(list2))
list1_groups = groupby(sorted_list1, key=lambda pair: pair[0])
list2_groups = groupby(sorted_list2, key=lambda pair: pair[0])
for element1, group1 in list1_groups:
try:
element2, group2 = next(list2_groups)
while element1 > element2:
(element2, _), group2 = next(list2_groups)
except StopIteration:
break
if element2 > element1:
continue
indices_product = product((i for _, i in group1), (i for _, i in group2), repeat=1)
yield from indices_product
# In version prior to 3.3, the above line must be
# for x in indices_product:
# yield x
list1 = [[], [1, 2], []]
list2 = [[1, 2], []]
list(find_matching_index(list1, list2)) # [(0, 1), (2, 1), (1, 0)]
事实证明，时间复杂度并没有受到太大影响。排序当然需要 O(n log(n))，但是 groupby 提供的生成器可以通过仅遍历我们的列表两次来恢复所有元素。结论是我们的复杂性主要受 product 输出大小的限制。因此给出算法为 O(n log(n)) 的最佳情况和再次为 O(n^2).
的最坏情况
使用 dict 可以减少查找时间，而 collections.defaultdict 专业化可以帮助记账。目标是一个 dict ，其值是您所追求的索引对。重复值会覆盖列表中较早的值。
import collections
# make a test list
list1 = list('ABCDEFGHIJKLMNOP')
list2 = list1[len(list1)//2:] + list1[:len(list1)//2]
# Map list items to positions as in: [list1_index, list2_index]
# by creating a defaultdict that fills in items not in list1,
# then adding list1 items and updating with with list2 items.
list_indexer = collections.defaultdict(lambda: [None, None],
((item, [i, None]) for i, item in enumerate(list1)))
for i, val in enumerate(list2):
list_indexer[val][1] = i
print(list(list_indexer.values()))
此问题的一个 brute-force 答案，如果只是为了验证任何解决方案，则由以下人员给出：
[(xi, xp) for (xi, x) in enumerate(list1) for (xp, y) in enumerate(list2) if x==y]
如何优化它在很大程度上取决于数据量和内存容量，因此了解这些列表有多大可能会有所帮助。我想我在下面讨论的方法至少适用于具有数百万个值的列表。
由于字典访问是 O(1)，似乎值得尝试将第二个列表中的元素映射到它们的位置。假设可以重复相同的元素，collections.defaultdict 将很容易让我们构造必要的字典。
l2_pos = defaultdict(list)
for (p, k) in enumerate(list2):
l2_pos[k].append(p)
表达式 l2_pos[k] 现在是 list2 中出现元素 k 的位置列表。只剩下将这些中的每一个与 list1 中相应键的位置配对。列表形式的结果是
[(p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k]]
但是，如果这些结构很大，生成器表达式可能会更好。要将名称绑定到上面列表理解中的表达式，您可以编写
values = ((p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k])
如果您随后遍历 values，您可以避免创建包含所有值的列表的开销，从而减少 Python 的内存管理和垃圾收集的负载，这几乎是全部就解决您的问题而言，开销。
当您开始处理大量数据时，了解生成器可能意味着是否有足够的内存来解决您的问题。在许多情况下，它们比列表理解具有明显的优势。
编辑： 可以通过使用集合而不是列表来保存位置来进一步加速此技术，除非顺序的更改是有害的。此更改留作 reader.
的练习
如果您的对象不可哈希，但仍可订购，您可能需要考虑使用 sorted 来匹配两个列表
假设两个列表中的所有元素都匹配
您可以对列表索引进行排序并对结果进行配对
indexes1 = sorted(range(len(list1)), key=lambda x: list1[x])
indexes2 = sorted(range(len(list2)), key=lambda x: list2[x])
matches = zip(indexes1, indexes2)
如果并非所有元素都匹配，但每个列表中都没有重复项
您可以同时对两者进行排序，并在排序时保留索引。然后，如果您捕获到任何连续的重复项，您就会知道它们来自不同的列表
biglist = list(enumerate(list1)) + list(enumerate(list2))
biglist.sort(key=lambda x: x[1])
matches = [(biglist[i][0], biglist[i + 1][0]) for i in range(len(biglist) - 1) if biglist[i][1] == biglist[i + 1][1]]
这是一个简单的方法 defaultdict。
给定
import collections as ct
lst1 = list("ABCD")
lst2 = list("BDAG")
lst3 = list("EAB")
str1 = "ABCD"
代码
def find_matching_indices(*iterables, pred=None):
"""Return a list of matched indices across `m` iterables."""
if pred is None:
pred = lambda x: x[0]
# Dict insertion
dd = ct.defaultdict(list)
for lst in iterables: # O(m)
for i, x in enumerate(lst): # O(n)
dd[x].append(i) # O(1)
# Filter + sort
vals = (x for x in dd.values() if len(x) > 1) # O(n)
return sorted(vals, key=pred) # O(n log n)
演示
在两个列表中查找匹配项（每个 OP）：
find_matching_indices(lst1, lst2)
# [[0, 2], [1, 0], [3, 1]]
按不同的结果索引排序：
find_matching_indices(lst1, lst2, pred=lambda x: x[1])
# [[1, 0], [3, 1], [0, 2]]
匹配两个以上的可迭代对象（长度可选）：
find_matching_indices(lst1, lst2, lst3, str1)
# [[0, 2, 1, 0], [1, 0, 2, 1], [2, 2], [3, 1, 3]]
详情
字典插入
每个项目都附加到 defaultdict 的列表中。结果看起来像这样，稍后过滤：
defaultdict(list, {'A': [0, 2], 'B': [1, 0], 'C': [2], 'D': [3, 1], 'G': [3]})
乍一看，从双 for 循环来看，人们可能会说时间复杂度为 O(n²)。但是，外循环中的容器列表的长度为 m。内循环处理每个长度为n的容器的元素。我不确定最终的复杂度是多少，但基于 this answer，我怀疑它是 O(n*m) 或至少低于 O(n²)。
过滤
Non-matches（长度为 1 的列表）被过滤掉，并对结果进行排序（主要用于 Python < 3.6 中的无序字典）。
通过 sorted 使用 timsort 算法按某个索引对字典值（列表）进行排序，最坏的情况是 O(n log n)。由于在 Python 3.6+ 中保留了字典键插入，因此 pre-sorted 项降低了复杂度 O(n)。
总的来说，最好的情况时间复杂度是O(n)；如果在 Python < 3.6 中使用 sorted，最坏情况是 O(n log n)，否则是 O(n*m)。
我正在处理两个大型数据集，我的问题如下。
假设我有两个列表：
list1 = [A,B,C,D]
list2 = [B,D,A,G]
除了 O(n2) 搜索之外，如何使用 Python 高效地找到匹配索引？结果应如下所示：
matching_index(list1,list2) -> [(0,2),(1,0),(3,1)]
无重复
如果您的对象是可散列的并且您的列表没有重复项，您可以创建第一个列表的倒排索引，然后遍历第二个列表。这只遍历每个列表一次，因此是 O(n).
def find_matching_index(list1, list2):
inverse_index = { element: index for index, element in enumerate(list1) }
return [(index, inverse_index[element])
for index, element in enumerate(list2) if element in inverse_index]
find_matching_index([1,2,3], [3,2,1]) # [(0, 2), (1, 1), (2, 0)]
有重复项
您可以扩展之前的解决方案以解决重复问题。您可以使用 set.
def find_matching_index(list1, list2):
# Create an inverse index which keys are now sets
inverse_index = {}
for index, element in enumerate(list1):
if element not in inverse_index:
inverse_index[element] = {index}
else:
inverse_index[element].add(index)
# Traverse the second list
matching_index = []
for index, element in enumerate(list2):
# We have to create one pair by element in the set of the inverse index
if element in inverse_index:
matching_index.extend([(x, index) for x in inverse_index[element]])
return matching_index
find_matching_index([1, 1, 2], [2, 2, 1]) # [(2, 0), (2, 1), (0, 2), (1, 2)]
不幸的是，这不再是 O(n)。考虑输入 [1, 1] 和 [1, 1] 的情况，输出是 [(0, 0), (0, 1), (1, 0), (1, 1)]。因此，根据输出的大小，最坏的情况不能比 O(n^2).
尽管如此，如果没有重复，这个解决方案仍然是O(n)。
Non-hashable 个对象
现在出现了您的对象不可散列但可比较的情况。这里的想法是以保留每个元素的原始索引的方式对列表进行排序。然后我们可以对等于的元素序列进行分组以获得匹配的索引。
由于我们在下面的代码中大量使用 groupby 和 product，所以我制作了 find_matching_index return 一个用于长列表内存效率的生成器。
from itertools import groupby, product
def find_matching_index(list1, list2):
sorted_list1 = sorted((element, index) for index, element in enumerate(list1))
sorted_list2 = sorted((element, index) for index, element in enumerate(list2))
list1_groups = groupby(sorted_list1, key=lambda pair: pair[0])
list2_groups = groupby(sorted_list2, key=lambda pair: pair[0])
for element1, group1 in list1_groups:
try:
element2, group2 = next(list2_groups)
while element1 > element2:
(element2, _), group2 = next(list2_groups)
except StopIteration:
break
if element2 > element1:
continue
indices_product = product((i for _, i in group1), (i for _, i in group2), repeat=1)
yield from indices_product
# In version prior to 3.3, the above line must be
# for x in indices_product:
# yield x
list1 = [[], [1, 2], []]
list2 = [[1, 2], []]
list(find_matching_index(list1, list2)) # [(0, 1), (2, 1), (1, 0)]
事实证明，时间复杂度并没有受到太大影响。排序当然需要 O(n log(n))，但是 groupby 提供的生成器可以通过仅遍历我们的列表两次来恢复所有元素。结论是我们的复杂性主要受 product 输出大小的限制。因此给出算法为 O(n log(n)) 的最佳情况和再次为 O(n^2).
使用 dict 可以减少查找时间，而 collections.defaultdict 专业化可以帮助记账。目标是一个 dict ，其值是您所追求的索引对。重复值会覆盖列表中较早的值。
import collections
# make a test list
list1 = list('ABCDEFGHIJKLMNOP')
list2 = list1[len(list1)//2:] + list1[:len(list1)//2]
# Map list items to positions as in: [list1_index, list2_index]
# by creating a defaultdict that fills in items not in list1,
# then adding list1 items and updating with with list2 items.
list_indexer = collections.defaultdict(lambda: [None, None],
((item, [i, None]) for i, item in enumerate(list1)))
for i, val in enumerate(list2):
list_indexer[val][1] = i
print(list(list_indexer.values()))
此问题的一个 brute-force 答案，如果只是为了验证任何解决方案，则由以下人员给出：
[(xi, xp) for (xi, x) in enumerate(list1) for (xp, y) in enumerate(list2) if x==y]
如何优化它在很大程度上取决于数据量和内存容量，因此了解这些列表有多大可能会有所帮助。我想我在下面讨论的方法至少适用于具有数百万个值的列表。
由于字典访问是 O(1)，似乎值得尝试将第二个列表中的元素映射到它们的位置。假设可以重复相同的元素，collections.defaultdict 将很容易让我们构造必要的字典。
l2_pos = defaultdict(list)
for (p, k) in enumerate(list2):
l2_pos[k].append(p)
表达式 l2_pos[k] 现在是 list2 中出现元素 k 的位置列表。只剩下将这些中的每一个与 list1 中相应键的位置配对。列表形式的结果是
[(p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k]]
但是，如果这些结构很大，生成器表达式可能会更好。要将名称绑定到上面列表理解中的表达式，您可以编写
values = ((p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k])
如果您随后遍历 values，您可以避免创建包含所有值的列表的开销，从而减少 Python 的内存管理和垃圾收集的负载，这几乎是全部就解决您的问题而言，开销。
当您开始处理大量数据时，了解生成器可能意味着是否有足够的内存来解决您的问题。在许多情况下，它们比列表理解具有明显的优势。
编辑： 可以通过使用集合而不是列表来保存位置来进一步加速此技术，除非顺序的更改是有害的。此更改留作 reader.
的练习如果您的对象不可哈希，但仍可订购，您可能需要考虑使用 sorted 来匹配两个列表
假设两个列表中的所有元素都匹配
您可以对列表索引进行排序并对结果进行配对
indexes1 = sorted(range(len(list1)), key=lambda x: list1[x])
indexes2 = sorted(range(len(list2)), key=lambda x: list2[x])
matches = zip(indexes1, indexes2)
如果并非所有元素都匹配，但每个列表中都没有重复项
您可以同时对两者进行排序，并在排序时保留索引。然后，如果您捕获到任何连续的重复项，您就会知道它们来自不同的列表
biglist = list(enumerate(list1)) + list(enumerate(list2))
biglist.sort(key=lambda x: x[1])
matches = [(biglist[i][0], biglist[i + 1][0]) for i in range(len(biglist) - 1) if biglist[i][1] == biglist[i + 1][1]]
这是一个简单的方法 defaultdict。
给定
import collections as ct
lst1 = list("ABCD")
lst2 = list("BDAG")
lst3 = list("EAB")
str1 = "ABCD"
代码
def find_matching_indices(*iterables, pred=None):
"""Return a list of matched indices across `m` iterables."""
if pred is None:
pred = lambda x: x[0]
# Dict insertion
dd = ct.defaultdict(list)
for lst in iterables: # O(m)
for i, x in enumerate(lst): # O(n)
dd[x].append(i) # O(1)
# Filter + sort
vals = (x for x in dd.values() if len(x) > 1) # O(n)
return sorted(vals, key=pred) # O(n log n)
演示
在两个列表中查找匹配项（每个 OP）：
find_matching_indices(lst1, lst2)
# [[0, 2], [1, 0], [3, 1]]
按不同的结果索引排序：
find_matching_indices(lst1, lst2, pred=lambda x: x[1])
# [[1, 0], [3, 1], [0, 2]]
匹配两个以上的可迭代对象（长度可选）：
find_matching_indices(lst1, lst2, lst3, str1)
# [[0, 2, 1, 0], [1, 0, 2, 1], [2, 2], [3, 1, 3]]
详情
字典插入
每个项目都附加到 defaultdict 的列表中。结果看起来像这样，稍后过滤：
defaultdict(list, {'A': [0, 2], 'B': [1, 0], 'C': [2], 'D': [3, 1], 'G': [3]})
乍一看，从双 for 循环来看，人们可能会说时间复杂度为 O(n²)。但是，外循环中的容器列表的长度为 m。内循环处理每个长度为n的容器的元素。我不确定最终的复杂度是多少，但基于 this answer，我怀疑它是 O(n*m) 或至少低于 O(n²)。
过滤
Non-matches（长度为 1 的列表）被过滤掉，并对结果进行排序（主要用于 Python < 3.6 中的无序字典）。
通过 sorted 使用 timsort 算法按某个索引对字典值（列表）进行排序，最坏的情况是 O(n log n)。由于在 Python 3.6+ 中保留了字典键插入，因此 pre-sorted 项降低了复杂度 O(n)。
总的来说，最好的情况时间复杂度是O(n)；如果在 Python < 3.6 中使用 sorted，最坏情况是 O(n log n)，否则是 O(n*m)。