Быстрый способ поиска индексов дубликатов в списках> 2000000 наименований

Question

У меня есть список, где каждый элемент представляет собой комбинацию двух идентификаторов событий: (Это просто фрагмент гораздо большего списка пар)

['10000381 10007121', '10000381 10008989',' 10005169 10008989 ',' 10008989 10023817 ',' 10005169 10043265 ',' 10008989 10043265 ',' 10023817 10043265 ',' 10047097 10047137 ',' 10047097 10047265 ',' 10047137 10047265 ',' 1003655656 1003453 1003453 1003455563) 1003456 1003455563) 1003455 1003455563) 10033056 1003455 100345530561 1003455 1003455303 1003456 1003455 1003455 1003 1003 1003 1003455 1003455303 '1003456 100345630' '100003856' ',' 10005169 10008989 ',' 10008989 10023817 ',' 10005169 10043265 ',' 10008989 10043265 ',' 10023817 10043265 ',' 10047097 10047137 ',' 10047097 10047265 '',' 10000381 10060557 ',' 10007121 10060557 ',' 10056453 10060557 ',' 10000381 10066013 ',' 10007121 10066013 ',' 10008989 10066013 ',' 10026233 10066013 ',' 10056453 10066013 ',' 10056453 100015 1001 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1003 1001 1003',' 10066013 10070153 ',' 10000381 10083798 ',' 10047265 10083798 ',' 10056453 10083798 ',' 10066013 10083798 ',' 10000381 10099969 ',' 10056453 10099969 ',' 10066013 10099969 ',' 1007 '1009 9999999',' 10056453 10167029 ',' 10066013 10167029 ',' 10083798 10167029 ',' 10099969 10167029 ',' 10182073 10182085 ',' 10182073 10182177 ',' 10182085 10182177 ',' 10000381 10187233 ',' 100564530187233 ',' 10060557 10187233 ',' 10066013 10187233 ',' 10083798 10187233 ',' 10099969 10187233 ',' 10167029 10187233 ',' 10007121 10200685 ',' 10099969 10200685 ',' 10066013 10218350 '' 10214005 '10214005' 10214005 '10214305' 10214005 '10214005' 10214005 '10214005' 10214005 '10214005' 10214005 '10214003' 10214003 '10214003' 10214003 '' 10214003 '' 10 '' 10 100%*

Мне нужно найти каждый экземпляр каждой пары идентификаторов и внести его в новый список.Прямо сейчас у меня есть несколько строк кода, которые делают это для меня.Тем не менее, мой список содержит более 2 000 000 строк и будет увеличиваться по мере обработки данных.

На данный момент расчетное время завершения составляет около 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, 21997, 20938), 20938.и т. д. и т. п.

Где каждое число в скобках является индексом этой пары в idlist.

По сути, я хочу, чтобы он посмотрел на пару значений id (т. е. 10000381 10007121'), проходит по списку и находит каждый экземпляр этой пары и документирует каждый индекс в списке, в котором встречается эта пара.Мне нужно что-то, что делает это для каждого элемента в списке.В более короткие сроки.

Answer 1

Вы можете использовать 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()) содержит ваш окончательный результат.

Answer 2

Если у вас много данных, я бы предложил вам использовать Pypy3 вместо интерпретатора CPython, и вы получите x5-x7 более быстрое выполнение кода.

Вот реализацияоснованный на времени тест с использованием CPython и Pypy3 с 1000 iterations:

Код:

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

Answer 3

Вместо списка используйте диктовку, которая заставляет искать существование O(1):

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