Gros dictionnaire

Accélérer l'accès

a marqué ce sujet comme résolu.

Bonjour,

J’ai un très gros dictionnaire (map, key/value, clé de type str et valeur une structure quelquonque), je voudrais faire des accès très rapidement sans avoir besoin de charger l’ensemble du dictionnaire.

Pour l’instant, c’est un fichier au format msgpkg de 450MB. Sauf que lorsque je le charge avec Python, il prend 4G de RAM et surtout 25s à se charger.

Mon but, c’est d’optimiser le bousin pour que ça prenne max 500ms de checker une entrée. L’idée c’est d’avoir un exécutable indépendant qui charge les données, pas un service qui tourne en tâche de fond.

Pour l’instant j’ai ça :

# To load with python interpreter

import msgpack
import ui

with open('result.pack', 'rb') as f:
    r = f.read()

d = msgpack.unpackb(r, raw=False)
del r

def give_entry(w):
    ui.show_terminal(d[w])

Que je lance avec python -i bigdict.py, ça charge 25s et ensuite j’appele give_entry('entrée').

Ce que je voudrais à la fin c’est juste faire bigdict entrée et avoir mon entrée bien affichée rapidement.

Vous auriez une idée de comment je peux faire ça ?

J’ai pensé à sqlite mais ça m’obligerait à formaliser mes données dans des tables, c’est un peu dur à faire, j’ai pas envie de tester juste pour tester. Si c’est là bonne solution, je le ferais mais comme j’ai des doûtes, je demande avant.

+0 -0

1 624 338. J’en ajouterais un peu encore, environ 2 millions quoi.

Effectivement, j’aurais du le dire. C’est le nombre d’entrées qui est génant. Une entrée fait max 40KB je dirais pour être large.

+0 -0

Donc trop pour te contenter d’un fichier par entrée (ça resterait techniquement possible, mais très pénible à gérer).

Je ne sais pas comment implémenter ça spécifiquement en Python, mais d’un point de vue général je ferais comme ça :

  1. Je choisirais une partie de la clé comme sous-clé (par exemple, les 2 premières lettres).
  2. Je découperait le gros dictionnaires en N dictionnaires (N = le nombre de sous-clés possibles).
  3. Quand tu appelles ton programme, il calcule la sous-clé, récupère le dictionnaire pertinent et va chercher dedans.

En plus d’un peu d’algo, ça nécessite surtout que tu puisses découper facilement ton dictionnaire et l’enregistrer dans plein de fichiers différents.

Il faut aussi choisir la sous-clé pour que :

  • Les dictionnaires restent de taille raisonnable pour être rapides (de l’ordre du Mo, pour rester dans le cache de la plupart des processeurs)
  • Ça ne produise pas des dizaines de milliers de fichiers pour éviter d’effondrer le système de fichier.

Je pense que tu as très bien compris le problème.

Ton idée me plaie, même si ça fait un peu bidouille. Ça demande un peu de réflection quand même pour découper le dictionnaire en N dictionnaires car si je me base sur les 2 première lettres, j’aurais d’énorme différences de taille entre les sous-dictionnaires.

Basiquement, les clés sont des mots de la langue française. Donc « en » serra un super gros sous dictionnaire alors que « wa » pas du tout.

Le principe est compris, donc je dois encore y réfléchir pour correctement choisir ma sous clée.

Merci en tout cas ! Ça m’aide vraiment. :D

+0 -0

C’est un problème assez classique en vrai.

Ça demande un peu de réflection quand même pour découper le dictionnaire en N dictionnaires car si je me base sur les 2 première lettres, j’aurais d’énorme différences de taille entre les sous-dictionnaires.

ache

La solution dans ce cas-là, c’est de découper selon un hash de la clé et pas directement selon la clé. Tu prends ton mot, tu le hache, et tu prends les N premiers / derniers caractères pour découper des dictionnaires (pas la peine de prendre un machin crypotgraphique, CRC32 ou MD5 feront très bien l’affaire).

Mais si ça équilibre directement les sous-dictionnaires, ça rends leur création plus compliquée.

Sauf erreur de ma part Git fonctionne comme ça pour stocker les objets, cf. .git/objects.

Comme il y a énormément d’objets, on les sous-divise d’abord en sous-dossiers sinon le filesystem galère devant le nombre colossal de fichiers (4 000 000 d’objets dans le dépôt de Linux)

Salut,

Je n’ai pas vraiment essayé mais il me semble que ça pourrait être plus adapté : as-tu essayé d’utiliser une base de données sqlite plutôt qu’un fichier msgpack ?

entwanne

Comme je le disais, j’y ai pensé aussi, mais comme ça nécessitais de normaliser mes objets et que c’était un peu compliqué j’ai préféré demander plutôt que le faire. C’est pas si dur mais les listes et les listes de listes en SQL. 😒

Bref, je tenterais quand même et je te dirais. ^^"

+0 -0

Ah désolé, je n’avais loupé ton dernier paragraphe.

Je n’ai pas testé sur des données aussi grosses, mais avec un fichier de 200Mo environ (composé de petites entrées (clé, valeur)) je ne constatais pas de lenteur au chargement, ni de pic de mémoire.

Pourquoi tu veux avoir a normaliser tes entrees? Si tu as clef/valeur tu peux juste stocker dans deux colonnes. Tu peux indexer la table sur la colonne qui correspond a la clef et avoir une performance gross-modo equivalente a acceder au dictionnaire chargee en memoire.

(apres, l’overhead de l’ouverture et fermeture de la connection peut-etre un peu problematique selon ton use case derriere)

EDIT: pour clarifier, l’index SQL te permettra d’avoir du O(log(n)) qui sur des deux millions d’entrees sera un peu plus lent que du O(1) avec un dictionnaire en memoire mais bien plus rapide si tu consideres aussi le temps de chargement du fichier en memoire / access a la BDD.

+0 -0

À quel point tu veux conserver le format mkgpack?

Une solution possible serait de changer le format du fichier pour contenir chaque entrée du dictionaire les unes après les autres et conserver un index de toutes tes entrées (un dictionnaire qui comporte la position et la taille des données pour chaque clé). Au lieux de devoir charger toutes tes données à chaque fois que tu veux checker une entrée, tu as juste besoin de charger l’index et ensuite d’aller chercher directement les données qui t’intéressent.

Si l’index est malgré tout trop gros pour être chargé rapidement, tu peux le découper comme suggéré par SpaceFox.

Salut,

Mets du MessagePack dans du SQLite, voire du JSON dans du SQLite (je ne propose pas Pickle pour des raisons de compatibilité). Les indexes d’un DBMS relationnel sont faits pour résoudre ton problème de performances (pense juste bien à les créer, si ta clef primaire est définie comme primaire alors ça se fera tout seul).

Du moins c’est la manière propre de résoudre le problème. Un système de fichiers n’est pas fait pour ça (trop d’entrées et blocs de taille fixe).

Bonne soirée,

+0 -0

Oui @r0anne, depuis que @KFC m’a soumis l’idée que je n’avais pas besoin de faire proprement une table relationnelle, c’est ce que je comptais faire, le msgpack directe dans le SQLite.

@Berdes: Je ne souhaites pas du tout conserver le format msgpack, mais bon, c’est pratique là. C’est du prototypage et je ne sais pas dans quel language je vais faire le logiciel alors j’ai pris un format simple et lisible par tous.

Au final ça marche nickel, merci beaucoup et à tous !
Hyper réactif (moins de 50ms ?! Yeah !). Je vais peut-être recoder ça en python.

J’index avec sqlite et j’enregistre les données importante en msqpack. La clé primaire est constituée de deux colonnes plutôt qu’un id mais ça marche nickel quand même.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte