Dictionnaire Python avec plusieurs clés pointant vers la même liste de manière efficace en mémoire

9

J'ai cette exigence unique qui peut être expliquée par ce code. C'est du code fonctionnel mais pas efficace en mémoire.

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']

En bref, je veux que chaque élément de la sous-liste soit indexable et devrait renvoyer la sous-liste.

La méthode ci-dessus fonctionne, mais elle prend beaucoup de mémoire lorsque les données sont volumineuses. Existe-t-il un meilleur moyen, compatible avec la mémoire et le processeur? Les données sont stockées sous forme de fichier JSON.

Modifier J'ai essayé les réponses pour le plus grand scénario de cas d'utilisation possible (1000 sous-listes, 100 éléments dans chaque sous-liste, 1 million de requêtes) et voici les résultats (moyenne de 10 exécutions):

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
Rahul
la source
{item: sublist for sublist in data for item in sublist}pourrait être un peu plus efficace et direct…?!
décomposer
Oui. pour mon cas d'échantillon. Dans mon scénario réel, la sous-liste contient des centaines d'articles et des milliers de telles sous-listes. l'utilisateur du code a une petite mémoire (<2 Go), donc quand une autre application lourde est en cours d'exécution, il se plaint que votre script est lent.
Rahul
Quel problème essayez-vous de résoudre exactement? Peut-être qu'une approche hybride fonctionnerait, dans laquelle vous indexez par la première lettre, puis parcourez quelques listes de candidats pour trouver votre valeur exacte, un peu comme un algorithme de résolution de collision de table de hachage.
décomposer
Pour un moyen efficace, utilisez des générateurs comme yield ().
Saisiva A
Merci. J'apprendrai ce que signifie «résolution de collision de table de hachage».
Rahul

Réponses:

2

Vous êtes vraiment dans un espace de compromis entre le temps / la mémoire nécessaire pour générer le dictionnaire par rapport au temps nécessaire pour analyser l'ensemble des données pour une méthode à la volée.

Si vous souhaitez une méthode de mémoire faible, vous pouvez utiliser une fonction qui recherche chaque valeur pour chaque sous-liste. L'utilisation d'un générateur obtiendra les résultats initiaux plus rapidement pour l'utilisateur, mais pour les grands ensembles de données, cela sera lent entre les retours.

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)

Comme mentionné dans les commentaires, la construction d'une table de hachage basée uniquement sur la première lettre ou le premier caractère 2 ou 3 peut être un bon point de départ. Cela vous permettra de créer une liste de sous-listes candidates, puis de les analyser pour voir si la valeur est dans la sous-liste.

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)

Dans ce code quick_hash, la construction prendra du temps, car vous analysez l'intégralité de votre structure de données. Cependant, l'empreinte mémoire sera beaucoup plus petite. Votre paramètre principal pour le réglage des performances est size. Une taille plus petite aura une empreinte mémoire plus petite, mais prendra plus de temps lors de l'exécution find_list_by_hashcar votre pool de candidats sera plus grand. Vous pouvez faire des tests pour voir quel sizedevrait être le droit de vos données. N'oubliez pas que toutes vos valeurs sont au moins aussi longues size.

James
la source
Et je pensais que je connaissais le python et la programmation. Merci. Il y a beaucoup à apprendre.
Rahul
2

Vous pouvez essayer quelque chose comme ceci:

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

Pas besoin de faire une structure de cartographie.

Pantalon Bhushan
la source
Merci mec. Je vais devoir vérifier si c'est plus rapide.
Rahul
1
il sera beaucoup plus rapide au démarrage car il n'y a pas de compréhension à calculer, mais beaucoup plus lent à utiliser car pour chaque élément à trouver, cette méthode va re-scanner l'ensemble des données.
Edouard Thiel
Bien sûr, faites-moi savoir si cela fonctionne pour vous.
Bhushan Pant
@EdouardThiel: Je ressens aussi la même chose. Mon utilisation réelle est d'avoir plus de cas d'utilisation que les cas de départ.
Rahul
@EdouardThiel true. Mais je ne suis pas sûr du cas d'utilisation exact.
Bhushan Pant
2

essayez ceci, en utilisant des pandas

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

cela semble une solution simple, même si vos données deviennent volumineuses, cela traitera cela efficacement

vgp2018
la source
vérifiez la taille de votre df: elle est considérablement plus grande que la liste data(> x12) et le dict temp_dict(~ x2) pour les données d'exemple données - pas exactement économes en mémoire, je dirais
MrFuppes
@MrFuppes Je ne pense pas que cet argument soit valide, car les pandas ne copient pas physiquement les chaînes dans ce cas
mcsoini
@mcsoini, j'avoue que mon commentaire est un peu superficiel - une analyse plus détaillée serait nécessaire pour déterminer si pandasgère ce problème plus efficacement que la fonctionnalité python intégrée.
MrFuppes
@MrFuppes: je suis d'accord. Pourquoi utiliser pandassi cela peut être fait en utilisant stdlib. Juste parce que ça a l'air chic?
Rahul
1
Mais vous n'avez pas précisé comment je vais interroger la trame de données. Pouvez-vous me montrer comment votre solution résoudra mon problème. J'ai essayé la solution de @ mcsoini pour les pandas mais cela prend une éternité pour 1 million de requêtes. Je ne sais pas pourquoi. Veuillez consulter ma question mise à jour pour les résultats de diverses méthodes.
Rahul
0

Je ne sais pas exactement comment cela se comporterait pour des données plus importantes, mais vous pouvez essayer quelque chose dans le sens de:

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

Edit: ne semble pas être bénéfique en termes de temps, basé sur un test rapide avec de fausses données à plus grande échelle.

mcsoini
la source