Сравнение двух больших списков, чтобы найти пары элементов, которые удовлетворяют условию в Python - PullRequest
Новая
       12

Сравнение двух больших списков, чтобы найти пары элементов, которые удовлетворяют условию в Python

1 голос
/ 11 апреля 2019

У меня есть два больших списка чисел (возможно, по миллиону элементов в каждом). Я хотел бы сравнить оба из них поэлементно, чтобы определить пары элементов, которые имеют разницу менее 0,5. Я знаю, что два вложенных для циклов не вариант. Есть ли какой-нибудь быстрый способ сделать это, используя наборы или почтовый индекс?

Например, если мои списки имеют значения list1 = [1,2,3,4] и list2 = [3,4,5,6], а условие равно разнице 1, то решение будет иметь пары, расположенные в списке [элемент из list1, элемент из list2, разница]. Решение будет [[2,3,1],[3,3,0],[3,4,1],[4,3,1],[4,4,0],[4,5,1]]

Спасибо

Ответы [ 3 ]

3 голосов
/ 11 апреля 2019

Это должно работать.(Критика приветствуется)

По сути, моя идея состоит в том, чтобы отсортировать два списка O (nlogn), а затем пройти по списку, сохраняя в памяти расстояние до следующего элемента, и, следовательно, не вычисляя все пары, но только подмножество дает мне O (2 * m * n) m максимально допустимое расстояние 

x = sorted([0, 2, 3, 4])
y = sorted([1,3, 4, 5, 6])
index = 0
delta = 1
output = []
j = 0
value_2 = y[0]
no_more = False
number_of_operation = 0
for i,value_1 in enumerate(x[:]):
    print(f'Testing for this {value_1}')
    skip = False
    try:
        next_value_at = x[i+1] - value_1 
        if next_value_at > delta:
            skip = True
            print('We can directly skip to next')
    except:
        print('At the end of list')
    while value_2 - value_1 <= delta:
        number_of_operation+=1
        print(value_1,value_2)
        try:
            if abs(value_1 - value_2) <= delta:
                output += [[value_1,value_2,value_1-value_2]]
            j+=1
            value_2 = y[j]
            print(value_1,value_2) 
            continue
        except:
            no_more = True
            print('end of list')
            break
    if not skip:
        print("Going back")
        j=index
        value_2 = y[index]
    else:
        index = j
    if no_more:
        print('end')
        break
    print(number_of_operation)
2 голосов
/ 11 апреля 2019

Вы можете избежать поведения O (N²), если сначала отсортируете свои списки (или еще лучше, если ваши списки уже отсортированы). Тогда вы можете пройти через них поэлементно. Это даст вам O (nLogn) для сортировок плюс O (n) для пошагового прохождения элементов. Например: 

list1 = range(0, 1000000)
list2 = range(999999, 1999999)

def getClose(list1, list2):
    c1, c2 = 0, 0
    while c1 < len(list1) and c2 < len(list2):
        if abs(list1[c1] - list2[c2]) <= 1:
            yield (list1[c1], list2[c2], abs(list1[c1] - list2[c2]))
        if list1[c1] < list2[c2]:
            c1 += 1
        else:
            c2 += 1

for n in getClose(list1, list2):
    print(n)

Производит ...

999998 999999 1
999999 999999 0
999999 1000000 1

... относительно быстро и намного быстрее, чем сначала найти продукт.

2 голосов
/ 11 апреля 2019

Используйте трансляцию numpy 

import numpy as np
x = np.array([1, 2, 3, 4]).reshape(-1, 1)
y = np.array([3, 4, 5, 6]).reshape(1, -1)
diff = x - y

Однако вы не можете избежать N ^ 2 сравнений, воспользуйтесь только оптимизацией скорости numpy.

...