Analiza wielu tablic na raz

(nie miałem pojęcia, jaki dać krótki i opisowy tytuł…)

Mam około 10³ tablic z około 10⁴ wpisami każda (liczba wpisów się różni pomiędzy tablicami). Niektóre wpisy się powtarzają pomiędzy tablicami, inne nie, ale zawsze każdy wpis występuje w jednej tablicy co najwyżej raz. Użytkownik wybiera dwie różne tablice, a program ma mu wygenerować tablicę wspólnych elementów pomiędzy nimi posortowaną malejąco tak, że wartości każdego elementu odpowiada maksimum jego indeksu na dwóch wybranych tablicach. Chcę móc odpowiedzieć jak najszybciej na około 10⁵ takich zapytań.

Przykład obrazujący:

A = ['Lena', 'Hanna', 'Zuzanna', 'Oliwia', 'Julia', 'Laura', 'Alicja', 'Zofia']
B = ['Lena', 'Zuzanna', 'Julia', 'Alicja', 'Oliwia', 'Maria', 'Hanna', 'Maja']
Lena → 0, Hanna → 6, Zuzanna → 2, Oliwia → 4, Julia → 4, Alicja → 6  # pozostałe nie występują na obu
tablica wynikowa → ['Lena', 'Zuzanna', 'Oliwia', 'Julia', 'Hanna', 'Alicja']  # kolejność przy remisie dowolna

Jak do tego sensownie podejść? Jak trzymać dane wejściowe, jak je składać do kupy? Nic mądrzejszego nad brute-force z 10⁴ przebiegami po 10³ wartości mi nie przychodzi do głowy… A prekalkulowanie tablic też mi się nie uśmiecha, bo mamy 10⁶ możliwych par po jakieś kilka tysięcy wartości każda, a to trochę sporo pamięci jak na moje potrzeby…

Jak nie żałujesz jeszcze dwa razy więcej pamięci, to dla każdej listy możesz utworzyć słownik: word: index, z każdej listy stworzyć set; wtedy złożoność pojedynczego zapytania będzie, nlogn, gdzie n jest długością mniejszego zbioru. POC, Python:

A = ['Lena', 'Hanna', 'Zuzanna', 'Oliwia', 'Julia', 'Laura', 'Alicja', 'Zofia']
B = ['Lena', 'Zuzanna', 'Julia', 'Alicja', 'Oliwia', 'Maria', 'Hanna', 'Maja']

d1 = {x: i for (i, x) in enumerate(A)}
d2 = {x: i for (i, x) in enumerate(B)}

s1 = {x for x in A}
s2 = {x for x in B}
s = list(s1.intersection(s2))

print(sorted(s, key=lambda x: max(d1[x], d2[x])))  # -> ['Lena', 'Zuzanna', 'Oliwia', 'Julia', 'Alicja', 'Hanna']

Generujesz trie dla każdej z tablic wejściowych gdzie kluczem jest pozycja w tablicy. Wtedy wychodzi podobnie jak w przykładzie @lion137 ale z mniejszym narzutem pamięci.

Możesz każdą z tych tablic trzymać jako tablicę par (indeks, wpis) odpowiednio (malejąco) posortowaną? Bo jeśli tak, to merging powinien wystarczyć, a potem odwrócenie kolejności... Będzie Ci działało w czasie liniowym.

Tak na szybko napisałem, może coś mi umyka.