python - 如何快速用字典识别列表中的重复数字

Question

我有一个关于搜索相同数字的问题。

我所拥有的:

我有一个带有字典的清单。在此词典中，有2对key-val，一个是唯一的id，另一个是带有数字的列表。

我需要做什么:

如果其他字典中的其他列表中有相同的数字，则需要定义，然后在parent字典中写入processed_data id和相同的数字。但是我的all列表非常大，此过程大约需要3.6天。

所以这是一个问题

我想找到其他任何方法来更快地处理它，如果可能的话，大约要花12个小时，感谢您的帮助。

PS(也许一些多处理或线程处理将以某种方式有所帮助，但我对是否可能存在很大疑问)

(在相同的字典及其列表中查找相同的数字时，我们将省略此处的情况)

# List with dictionaries:
all = [
 {'id' : 0, 'numbers' : [1, 2, 3, 4, 5]},
 {'id' : 1, 'numbers' : [5, 7, 9]},
 {'id' : 2, 'numbers' : [10, 12, 14]},
 {'id' : 3, 'numbers' : [3, 12, 5]}
]

# Here I will store the results
processed_data = {}

# For every row
for every in all:

 id = every['id']
 numbers_list = every['numbers']

 for every_2 in all:
 numbers_list_2 = every_2['numbers']

 # If number exists in the other row
 # I remember id of the list wich contain this number
 # And number
 for number in numbers_list_2:
 if number in numbers_list:
 processed_data[id] = number

print(processed_data)

预期产量:

{0: 5, 1: 5, 2: 12, 3: 5}

Answer 1

确实，您的列表处理效率非常低下，因为您将每个字典与其他每个字典组合(一个O(N ^ 2)顺序处理)，然后通过将长度为K的列表中的每个值与另一个数字列表相组合来复合该列表连续扫描具有类似的长度，因此最终得到O(N ^ 2 * K ^ 2)。这将需要很长时间。这是顺序扫描，因为您对数字(number in numbers_list)进行的容纳测试必须逐一测试numbers_list列表中的每个值，直到找到匹配项或列表用尽。

您想了解sets。 Sets让您测试数字是否恒定存在，因为每个值本身都是通过其哈希值指向其在数据结构中位置的键(因此something in setvalue只需要查看sett表中是否存在hash(something))。您还可以非常有效地获得它们的交点，因此两组中都存在一组数字。对于两组平均大小K，这需要O(K)线性时间。交集就是setA & setB。

我会将您的数据结构转换为包含以开头的集合，然后针对两个列表之间的交集，记录集合中每个数字的和两个 ID，因为这两个列表都有相同的数字。这样一来，您就可以减少O(N ^ 2)配对，因为当您用ID B测试了ID A时，您不必针对ID A对ID B做相同的事情。从技术上讲，这仍然是O(N ^ 2) )，但实际上是triangle number or arithmetic series; N + N-1 + N-2 ....即(N *(N + 1))// 2，对于实际问题，迭代次数要低得多，要比完整的N ^ 2好得多;将方法与实际情况和有限的输入大小进行比较时，将花费的时间减半仍然很重要。

看起来像这样:

all = [
    {'id' : 0, 'numbers' : [1, 2, 3, 4, 5]},
    {'id' : 1, 'numbers' : [5, 7, 9]},
    {'id' : 2, 'numbers' : [10, 12, 14]},
    {'id' : 3, 'numbers' : [3, 12, 5]},
]
# conversion to sets
for d in all:
    d['numbers'] = set(d['numbers'])

processed_data = {}

for i, entry in enumerate(all):
    id1 = entry['id']
    for j in range(i + 1, len(all)):
        id2 = all[j]['id']
        for num in entry['numbers'] & all[j]['numbers']:
            processed_data.update({id1: num, id2: num})

可以使用 itertools.combinations() 为我们进行配对，从而进一步简化嵌套循环:

from itertools import combinations

# everything before the loop the same up to setting `processed_data`

for entry1, entry2 in combinations(all, r=2):
    id1, id2 = entry1['id'], entry2['id']
    for num in entry1['numbers'] & entry2['numbers']:
        processed_data.update({id1: num, id2: num})

因此，这使您拥有的词典之间的组合数量减少了一半，每个组合的工作时间是线性时间而不是二次时间。那已经很容易将处理时间减少到6小时，甚至可能少于6小时。这是因为用O(K)时间(每步固定成本类似)替换O(K ^ 2)算法可以让您将时间除以K。如果列表的长度为1000个元素，我们可以期望所需时间减少了1000倍； 3.6天约为311000秒，因此期望3100秒的运行时间(略大于5个小时，并且仅非常保守地将速度提高100倍，而不是1000倍)并不超出此处的可能性范围。听起来好像您的列表比这更长，想象一下避免O(K ^ 2)比较循环可以证明快了多少!

接下来，由于您的输出使用 id作为唯一值，但是对于给定的 all，您在 id中的输入可能具有多个条目，因此您可以在此处进一步减少N和K，方法是首先将每个 id值的数字合并为一个单独的集合。您可以通过将 all映射到以 id为键并设置为值的字典来实现。因为我们仍然受O(N ^ 2)算法约束以组合 all中的条目，所以减少N会产生很大影响；如果N = 1000，则转到N = 999会从考虑中删除1000个交集(替换为一个集更新以首先合并重复的id)。

转换为集合时，首先合并输入，然后变为:

from itertools import combinations

all = [
    {'id' : 0, 'numbers' : [1, 2, 3, 4, 5]},
    {'id' : 1, 'numbers' : [5, 7, 9]},
    {'id' : 2, 'numbers' : [10, 12, 14]},
    {'id' : 3, 'numbers' : [3, 12, 5]},
    # I've added another entry with id 1, but different numbers
    {'id' : 1, 'numbers' : [17, 42, 11]},
]
# conversion to sets
all_sets = {}
for d in all:
    all_sets.setdefault(d['id'], set()).update(d['numbers'])

# if memory is an issue at this point, consider adding 'del all'.

processed_data = {}

for (id1, numbers1), (ids2, numbers2) in combinations(all_sets.items(), r=2):
    for num in numbers1 & numbers2:
        processed_data.update({id1: num, id2: num})

这个双循环实际上很简单，足以转化为字典理解。除了降低每个步骤执行Python字节码的固定成本之外，没有其他好处:

processed_data = {
    id: num
    for (id1, num1), (ids2, num2) in combinations(all_sets.items(), r=2)
    for num in num1 & num2
    for id in (id1, id2)
}

请注意，我们只记录与给定 id的另一个列表共享的最后一个数字。如果要记录所有此类数字，则需要制作 processed_data值列表或集合，以便可以容纳多个数字的容器。

然后，您将无法使用dict理解。而是使用 dict.setdefault()来确保有一个空容器，并将其添加到返回的容器中:

processed_data = {}

for (id1, numbers1), (ids2, numbers2) in combinations(all_sets.items(), r=2):
    for num in numbers1 & numbers2:
        processed_data.setdefault(id1, set()).add(num)
        processed_data.setdefault(id2, set()).add(num)

这将创建集合，但您也可以使用列表，例如 processed_data.setdefault(id1, []).append(num)等。对于您的示例 all数据，将产生:

>>> processed_data
{0: {3, 5}, 3: {3, 5, 12}, 1: {5}, 2: {12}}

上述方法要求 numbers包含可哈希值，即整数。如果您的实际设置没有可散列的值，请通过将其转换为该作业来使其可散列。节省时间是值得的。

例如。如果您有必须找到匹配项的整数列表，请先将其转换为元组。这很容易做到:

all_sets = {}
for d in all:
    all_sets.setdefault(d['id'], set()).update(map(tuple, d['numbers']))

其中 map(tuple, d['numbers'])将 tuple()应用于每个元素，然后再将这些元组添加到集合中。