快速查找超过2000000个项目列表中重复项的索引方法

Question

我有一个列表，其中每个项目都是两个事件ID的组合：（这只是更大的一堆配对中的一小部分）

['10000381 10007121'， '10000381 10008989'， '10005169 10008989'， '10008989 10023817'， '10005169 10043265'， '10008989 10043265'， '10023817 10043265'， '10047097 10047137'， '10047097 10047265'， '10047137 10047265'， '10000381 10056453'， '10047265 10056453'， '10000381 10060557'， '10007121 10060557'， '10056453 10060557'， '10000381 10066013'， '10007121 10066013'， '10008989 10066013'， '10026233 10066013'， '10056453 10066013'， '10056453 10070153'， '10060557 10070153'， '10066013 10070153'， '10000381 10083798'， '10047265 10083798'， '10056453 10083798'， '10066013 10083798'， '10000381 10099969'， '10056453 10099969'， '10066013 10099969'， '10070153 10099969'， '10083798 10099969'， '10056453 10167029'， '10066013 10167029'， '10083798 10167029'， '10099969 10167029'， '10182073 10182085'， '10182073 10182177'， '10182085 10182177'， '10000381 10187233'， '10056453 10187233'， '10060557 10187233'， '10066013 10187233'， '10083798 10187233'， '10099969 10187233'， '10167029 10187233'， '10007121 10200685'， '10099969 10200685'， '10066013 10218005'， '10223905 10224013']

我需要找到每个ID对的每个实例，并将其索引到新列表中。目前我有几行代码可以为我完成此操作。但是，我的列表超过200万行，随着我处理更多数据，它会变得更大。

此时，预计完成时间约为2天。

我真的只需要一种更快的方法来解决这个问题。

我在Jupyter Notebooks上工作（在Mac笔记本电脑上）

def compiler(idlist):
    groups = []
    for i in idlist:
        groups.append([index for index, x in enumerate(idlist) if x == i])
    return(groups)

我也尝试过：

def compiler(idlist):
    groups = []
    for k,i in enumerate(idlist):
        position = []
        for c,j in enumerate(idlist):
            if i == j:
                position.append(c)
        groups.append(position)
    return(groups)

我想要的是这样的：

'10000381 10007121': [0]
'10000381 10008989': [1]
'10005169 10008989': [2, 384775, 864173, 1297105, 1321798, 1555094, 1611064, 2078015]
'10008989 10023817': [3, 1321800]
'10005169 10043265': [4, 29113, 864195, 1297106, 1611081]
[5, 864196, 2078017]
'10008989 10043265': [6, 29114, 384777, 864198, 1611085, 1840733, 2078019]
'10023817 10043265': [7, 86626, 384780, 504434, 792690, 864215, 1297108, 1321801, 1489784, 1524527, 1555096, 1595763, 1611098, 1840734, 1841280, 1929457, 1943701, 1983362, 2093820, 2139917, 2168437] 等等。 等等。

其中每个括号中的数字是该对id在idlist中的索引。

基本上，我希望它能查看一对id值（即“10000381 10007121”），并运行列表并找到该对的每个实例，并记录此对出现的列表中的每个索引。我需要为列表中的每个项目都执行此操作。在较短的时间内完成。

- Kyle Macy

---

你可以先将它们分割，然后转换为NumPy数组，然后像这里所示使用unique。链接 - Sheldore

你需要一个不同的数据结构来解决这个问题，大约在几百万行之前。如果允许更改，请查看字典。 - Paritosh Singh

现在你正在遍历每个项目的列表，即您具有O(n^2)性能。 您可以使用groups = collections.defaultdict(list)，然后执行for index, item in enumerate(idlist): groups[item].append(index)，这是O(n)。 - a_guest

可能是[如何有效地在两个列表中查找匹配元素的索引]的重复问题(https://dev59.com/NlUM5IYBdhLWcg3wJ9rV) - Olivier Melançon

你能否更新你的问题，展示与之匹配的样本数据和“我想要”的输出？此外，你是在寻找重复的ID（'10000381'和'10007121'），还是重复的ID对（'10000381 10007121'）？ - PaulMcG

从示例代码中很明显可以看出，单个项目不应该被拆分，而应该按原样进行比较。 - a_guest

Answer 1

不要使用列表，而是使用字典，这样查找存在性的时间复杂度为O(1)：

def compiler(idlist):
    groups = {}
    for idx, val in enumerate(idlist):
        if val in groups:  
            groups[val].append(idx)
        else:
            groups[val] = [idx]

- Quang Hoang

---

将groups更改为defaultdict(list)，看看这如何简化您的代码（for循环体将折叠为单个语句）。但是您仍然需要创建OP请求的列表列表。 将groups更改为defaultdict(list)可以简化代码（for循环体将变成一条语句），但您仍需要创建OP要求的列表嵌套列表。 - PaulMcG

Answer 2

您可以使用collections.OrderedDict来将时间复杂度降至O(n)。由于它记住插入顺序，值的顺序类似于它们出现的编号。

from collections import OrderedDict

groups = OrderedDict()
for i, v in enumerate(idlist):
    try:
        groups[v].append(i)
    except KeyError:
        groups[v] = [i]

那么list(groups.values())包含你的最终结果。

- a_guest

---

与其捕获 KeyError，你可以直接使用 setdefault：groups.setdefault(v, []).append(i)。 - Daniel Pryden

@DanielPryden try/except 更快（例如对于 idlist = np.random.randint(10_000, size=2_000_000)，它的运行时间为 717 毫秒 ± 14.2 毫秒，而 setdefault 的运行时间为 997 毫秒 ± 29.3 毫秒）。 - a_guest

Answer 3

如果你有大量的数据，我建议你使用 Pypy3 而不是 CPython 解释器，这样你的代码执行速度可以提高 x5-x7 倍。

下面是一个基于时间的基准测试实现，使用 CPython 和 Pypy3 进行了 1000 次迭代：

代码：

from time import time
from collections import OrderedDict, defaultdict


def timeit(func, iteration=10000):
    def wraps(*args, **kwargs):
        start = time()
        for _ in range(iteration):
            result = func(*args, **kwargs)
        end = time()
        print("func: {name} [{iteration} iterations] took: {elapsed:2.4f} sec".format(
            name=func.__name__,
            iteration=iteration,
            args=args,
            kwargs=kwargs,
            elapsed=(end - start)
        ))
        return result
    return wraps


@timeit
def op_implementation(data):
    groups = []
    for k in data:
        groups.append([index for index, x in enumerate(data) if x == k])
    return groups


@timeit
def ordreddict_implementation(data):
    groups = OrderedDict()
    for k, v in enumerate(data):
        groups.setdefault(v, []).append(k)
    return groups


@timeit
def defaultdict_implementation(data):
    groups = defaultdict(list)
    for k, v in enumerate([x for elm in data for x in elm.split()]):
        groups[v].append(k)
    return groups


@timeit
def defaultdict_implementation_2(data):
    groups = defaultdict(list)
    for k, v in enumerate(map(lambda x: tuple(x.split()), data)):
        groups[v].append(k)
    return groups


@timeit
def dict_implementation(data):
    groups = {}
    for k, v in enumerate([x for elm in data for x in elm.split()]):
        if v in groups:
            groups[v].append(k)
        else:
            groups[v] = [k]
    return groups



if __name__ == '__main__':
    data = [
        '10000381 10007121', '10000381 10008989', '10005169 10008989', '10008989 10023817', 
        '10005169 10043265', '10008989 10043265', '10023817 10043265', '10047097 10047137', 
        '10047097 10047265', '10047137 10047265', '10000381 10056453', '10047265 10056453', 
        '10000381 10060557', '10007121 10060557', '10056453 10060557', '10000381 10066013', 
        '10007121 10066013', '10008989 10066013', '10026233 10066013', '10056453 10066013', 
        '10056453 10070153', '10060557 10070153', '10066013 10070153', '10000381 10083798', 
        '10047265 10083798', '10056453 10083798', '10066013 10083798', '10000381 10099969', 
        '10056453 10099969', '10066013 10099969', '10070153 10099969', '10083798 10099969', 
        '10056453 10167029', '10066013 10167029', '10083798 10167029', '10099969 10167029', 
        '10182073 10182085', '10182073 10182177', '10182085 10182177', '10000381 10187233', 
        '10056453 10187233', '10060557 10187233', '10066013 10187233', '10083798 10187233', 
        '10099969 10187233', '10167029 10187233', '10007121 10200685', '10099969 10200685', 
        '10066013 10218005', '10223905 10224013'
    ]
    op_implementation(data)
    ordreddict_implementation(data)
    defaultdict_implementation(data)
    defaultdict_implementation_2(data)
    dict_implementation(data)

CPython：

func: op_implementation [10000 iterations] took: 1.3096 sec
func: ordreddict_implementation [10000 iterations] took: 0.1866 sec
func: defaultdict_implementation [10000 iterations] took: 0.3311 sec
func: defaultdict_implementation_2 [10000 iterations] took: 0.3817 sec
func: dict_implementation [10000 iterations] took: 0.3231 sec

Pypy3：

func: op_implementation [10000 iterations] took: 0.2370 sec
func: ordreddict_implementation [10000 iterations] took: 0.0243 sec
func: defaultdict_implementation [10000 iterations] took: 0.1216 sec
func: defaultdict_implementation_2 [10000 iterations] took: 0.1299 sec
func: dict_implementation [10000 iterations] took: 0.1175 sec

Pypy3 跑 2000000 次迭代：

func: op_implementation [200000 iterations] took: 4.6364 sec
func: ordreddict_implementation [200000 iterations] took: 0.3201 sec
func: defaultdict_implementation [200000 iterations] took: 2.2032 sec
func: defaultdict_implementation_2 [200000 iterations] took: 2.4052 sec
func: dict_implementation [200000 iterations] took: 2.2429 sec

- Chiheb Nexus