Оптимизация поиска всех пар между двумя массивами

Question

Проблема: для двух массивов целых чисел A и B я пытаюсь найти все (i, j) такие, что A [i] == B [j]

Проблема в том, что мне нужно чтобы запустить это на миллионах и миллионах массивов целых чисел. (каждая до 100 в длину) Итак, скорость - это название игры! Мне бы хотелось помочь выжать из этого всю возможную скорость или даже улучшить общую функцию.

Мой подход пока состоит в том, чтобы виртуально отсортировать A и B через:

sorted(range(len(A)), key=lambda k: A[k]) 

Затем он проходит, увеличивая либо i, либо j (в зависимости от того, что ниже). Если найдено совпадение между и A и B, он сканирует A и B, пока не найдет следующее значение, которое не совпадает, и рассматривает его как "диапазон соответствия" Затем он сохраняет перекрестное произведение этих диапазонов как найденные пары. Код завершается, когда либо: A и B находятся в конце своих соответствующих массивов, либо когда один находится в конце, а другой в настоящее время указывает на значение, которое больше (так как было бы невозможно найти пару, просматривая дальше )

A = [3,7,8,2,1]#Example arrays. Lengths can be different.
B = [4,2,9,3,6,3]#Real arrays will be longer (up to 100).

SortA=sorted(range(len(A)), key=lambda k: A[k]) 
SortB=sorted(range(len(B)), key=lambda k: B[k]) 

solns = []
i = 0
j = 0
done = False

while(not done):
    if(A[SortA[i]] == B[SortB[j]]):

        if(i == len(A) - 1):
            endA = 0
        for m in range(len(A) - i - 1):
            endA = m + 1
            if(A[SortA[i]] != A[SortA[i + m + 1]]):
                endA = m 
                break;

        if(j == len(B) - 1):
            endB = 0
        for n in range(len(B) - j - 1):
            endB = n + 1
            if(B[SortB[j]] != B[SortB[j + n + 1]]):
                endB = n 
                break;

        for r in range(i, i + endA + 1):
            for s in range(j, j + endB + 1):
                solns.append((r,s))

        i = i + endA + 1
        j = j + endB + 1

    else:
        if(A[SortA[i]] < B[SortB[j]]):
            i = i + 1
        else:
            j = j + 1

    if(i == len(A)):
        if(j == len(B)):
            done = True
        else:
            if(A[SortA[len(A)-1]] < B[SortB[j]]):
                done = True
        i = i - 1
    if(j == len(B)):
        if(B[SortB[len(B)-1]] < A[SortA[i]]):
                done = True
        j = j - 1

Ожидаемые результаты для A и B в приведенном выше коде:

Match : (2, 2) Index: (3,1)
Match : (3, 3) Index: (0,3)
Match : (3, 3) Index: (0,5)

Answer 1

Вы должны просто использовать встроенные функции и модуль ==, например pandas. Вот пример:

import pandas as pd
A = pd.DataFrame({'a': [0,1], 'b': [2,3]})
B = pd.DataFrame({'a': [0,1], 'b': [2,3]})
print( (A==B).all().all() )

A = pd.DataFrame({'a': [0,-1], 'b': [2,3]})
B = pd.DataFrame({'a': [0,1], 'b': [2,3]})
print( (A==B).all().all() )

вывод:

True
False