Słownik Pythona z wieloma kluczami wskazującymi tę samą listę w sposób efektywny pod względem pamięci

Mam ten wyjątkowy wymóg, który można wyjaśnić za pomocą tego kodu. To działa kod, ale nie jest wydajne pod względem pamięci.

data = [[
        "A 5408599",
        "B 8126880",
        "A 2003529",
    ],
    [
        "C 9925336",
        "C 3705674",
        "A 823678571",
        "C 3205170186",
    ],
    [
        "C 9772980",
        "B 8960327",
        "C 4185139021",
        "D 1226285245",
        "C 2523866271",
        "D 2940954504",
        "D 5083193",
    ]]

temp_dict = {
    item: index for index, sublist in enumerate(data)
        for item in sublist
}

print(data[temp_dict["A 2003529"]])

out: ['A 5408599', 'B 8126880', 'A 2003529']

Krótko mówiąc, chcę, aby każdy element listy podrzędnej był indeksowalny i powinien zwrócić podlistę.

Powyższa metoda działa, ale zajmuje dużo pamięci, gdy dane są duże. Czy jest jakiś lepszy sposób, przyjazny dla pamięci i procesora? Dane są przechowywane jako plik JSON.

Edytuj Próbowałem odpowiedzi dla największego możliwego scenariusza przypadku użycia (1000 list podrzędnych, 100 pozycji w każdej liście podrzędnej, 1 milion zapytań) i oto wyniki (średnio 10 przebiegów):

Method,    Time (seconds),    Extra Memory used
my,        0.637              40 Mb
deceze,    0.63               40 Mb
James,     0.78               200 kb
Pant,      > 300              0 kb
mcsoini,   forever            0 kb

Naprawdę jesteś w miejscu na kompromis między czasem / pamięcią potrzebną do wygenerowania słownika a czasem potrzebnym do przeskanowania wszystkich danych w celu znalezienia metody „w locie”.

Jeśli chcesz zastosować metodę niskiej pamięci, możesz użyć funkcji, która przeszukuje każdą podlistę pod kątem wartości. Użycie generatora przyspieszy początkowe wyniki dla użytkownika, ale w przypadku dużych zestawów danych będzie to powolne między zwrotami.

data = [[
        "A 5408599",
        "B 8126880",
        "A 2003529",
    ],
    [
        "C 9925336",
        "C 3705674",
        "A 823678571",
        "C 3205170186",
    ],
    [
        "C 9772980",
        "B 8960327",
        "C 4185139021",
        "D 1226285245",
        "C 2523866271",
        "D 2940954504",
        "D 5083193",
    ]]


def find_list_by_value(v, data):
    for sublist in data:
        if v in sublist:
            yield sublist

for s in find_list_by_value("C 9772980", data):
    print(s)

Jak wspomniano w komentarzach, dobrym pomysłem może być zbudowanie tabeli skrótów opartej tylko na pierwszej literze lub pierwszych 2 lub 3 znakach. Umożliwi to zbudowanie listy kandydackiej list podrzędnych, a następnie skanowanie ich w celu sprawdzenia, czy wartość znajduje się na liście podrzędnej.

from collections import defaultdict

def get_key(v, size=3):
    return v[:size]

def get_keys(sublist, size=3):
    return set(get_key(v, size) for v in sublist)

def find_list_by_hash(v, data, hash_table, size=3):
    key = get_key(v, size)
    candidate_indices = hash_table.get(key, set())
    for ix in candidates:
        if v in data[ix]:
            yield data[ix]

# generate the small hash table
quick_hash = defaultdict(set)
for i, sublist in enumerate(data):
    for k in get_keys(sublist, 3):
        quick_hash[k].add(i)

# lookup a value by the small hash
for s in find_list_by_hash("C 9772980", data, quick_hash, 3):
    print(s)

quick_hashBudowa tego kodu zajmie trochę czasu, ponieważ skanujesz całą strukturę danych. Jednak ślad stopy pamięci będzie znacznie mniejszy. Głównym parametrem dostrajania wydajności jest size. Mniejszy rozmiar będzie miał mniejszą pamięć, ale będzie działał dłużej, find_list_by_hashponieważ twoja pula kandydatów będzie większa. Możesz przeprowadzić testy, aby sprawdzić, jakie prawo sizepowinno przysługiwać Twoim danym. Pamiętaj tylko, że wszystkie twoje wartości są przynajmniej tak długie size.

Możesz spróbować czegoś takiego:

list(filter(lambda x: any(["C 9772980" in x]),data))

Nie trzeba tworzyć struktury mapowania.

spróbuj tego, używając pand

import pandas as pd
df=pd.DataFrame(data)
rows = df.shape[0]
for row in range(rows):
    print[[row]]    #Do something with your data

wygląda to na proste rozwiązanie, nawet jeśli Twoje dane rosną, poradzi sobie z tym skutecznie

Nie jestem do końca pewien, jak to by się zachowało w przypadku większych ilości danych, ale możesz spróbować czegoś w stylu:

import pandas as pd
df = pd.DataFrame(data).T
df.loc[:, (df == 'A 2003529').any(axis=0)]
Out[39]: 
           0
0  A 5408599
1  B 8126880
2  A 2003529
3       None
4       None
5       None
6       None

Edycja: Wydaje się nie być korzystna pod względem czasu, na podstawie szybkiego testu z fałszywymi danymi na większą skalę.