Licence CC BY

Chercher dans un CSV de 3 Go en quelques instants

Ou comment gagner le jeu du "Plus ou Moins" facilement

Votre premier cours d’algorithmique introduisait sûrement la notion de dichotomie pour jouer efficacement au Plus ou Moins, le jeu dans lequel le sphinx choisit un nombre entier entre nn et mm à deviner. La solution optimale étant alors de proposer n+m2\frac{n+m}{2} afin d’éliminer à chaque coup la moitié des possibilités totales dans l’intervalle [n,m][n, m]. Très rapidement, on converge vers la solution.

Aussi étonnant que cela puisse paraître, je n’ai eu que très peu l’occasion d’implémenter ce grand classique dans de véritables projets professionnels.
Eh oui ! il faut dire qu’il y a toujours une lib à portée de main (style bisect) qui implémente déjà le bon algorithme pour le problème, ou bien parce que l’on se repose souvent sur une base de données qui utilise déjà des structures efficaces en interne.

Mais récemment, j’ai enfin eu l’occasion d’implémenter l’algorithme du sphinx. L’exercice : une recherche dans une base de données CSV de 3 Go, 1 524 580 lignes. Il s’agit d’une base de données d'Open Food Facts dans laquelle il faut trouver les informations d’un produit avec comme clef d’accès son code barre, en première colonne.

Évidemment, il n’est pas concevable de charger 3 Go dans un programme à chaque fois que l’on a besoin d’une entrée. Il faut donc procéder autrement, sans jamais charger le fichier en mémoire.

Solution

On va chercher dans un intervalle entre mini et maxi. Au début, mini = 0 et maxi = file_size (en octets).

À chaque itération on se place sur l’octet du milieu grâce à f.seek(). Comme on ne peut pas être sûr de tomber exactement en début de ligne CSV, on fait un f.readline() dans le vide pour se placer au début de la ligne suivante. Dès lors, il n’y a plus qu’à lire et parser cette ligne CSV pour voir si l’on tombe sur le code barre recherché. Si c’est le cas, on peut retourner la ligne CSV complète, on a fini. Si non, on compare simplement le code barre courant avec le code barre cible pour ré-ajuster les bornes mini et maxi en retranchant le précédent intervalle de moitié.

Le code explique tout ça mieux :

def lookup_product(target):
    filename = DATAFILE_OPENFOODFACTS  # Le fichier CSV de 3 Go
    file_size = os.stat(filename).st_size
    max_steps = int(math.log(file_size) / math.log(2)) + 1
    
    with open(filename, 'r') as f:
        mini = 0
        maxi = file_size
        for _ in range(max_steps + 1):
            mid = (mini + maxi) // 2
            f.seek(mid)  # Se placer au milieu de l'intervalle
            f.readline()  # Avancer à la prochaine ligne
            line = f.readline()  # Consommer la ligne courante
            code = line.split('\t', 1)[0]  # lire le code barre, 1re colonne du CSV
            if target < code:
                maxi = mid
            elif target > code:
                mini = mid
            else:
                return line.split('\t')  # Trouvé

Pour être sûr de ne pas tomber dans une boucle infinie, le for _ in range(max_steps + 1) impose une limite du nombre d’itérations. Avec un savant calcul, j’ai estimé au feeling que c’était log2(s)+1log_2(s) + 1, avec s=s = file_size. (c’est sûrement un peu brouillon, je suis une quiche en maths…)

On peut remarquer un problème dans la fonction : on ne peut jamais atteindre la toute première ligne du CSV. En effet, même si l’on tombait sur le premier octet, le f.readline() nous amènerait aussitôt sur la deuxième ligne. En fait, ce n’est pas un problème puisque la première ligne est le header du CSV qu’on cherchera à éviter.

Sur un dédié aux capacités plutôt modestes (disque dur SATA) les accès avec seek successifs sont plutôt satisfaisants, en cache froid. Cela ne dépasse guère quelque millisecondes.



Voilà comment, après des années dans le domaine, j’ai enfin implémenté l’exercice 1 du chapitre 1 de n’importe quel livre d’algo dans un cas réel ^^

Crédits

Crédits pour l’image : Bisection_method.svg de Tokuchan, sous licence CC BY-SA 3.0 (source : https://commons.wikimedia.org/w/index.php?curid=9382140)

4 commentaires

Avec un savant calcul, j’ai estimé au feeling que c’était log2(s)+1\log_2(s)+1, avec s=s = file_size. (c’est sûrement un peu brouillon, je suis une quiche en maths…)

C’est le nombre de lignes qui compte, pas le nombre de bytes du fichier. Tu surestimes "beaucoup" (ça reste qu’un log) la longueur de ta boucle. Tu pourrais plutôt boucler jusqu’à ce que maxi et mini sont à un readline d’écart (en faisant gaffe que l’astuce avec readline() permette à cette situation d’arriver et ne laisse pas de trou dans l’exploration, sinon t’es pas bon de toute façon).

EDIT : au fait math.log2 existe directement.

+2 -0

On est d’accord que ça ne fonctionne que si ton fichier CSV est correctement trié à l’origine ?

SpaceFox

Oui, tout à fait ! J’aurais dû le préciser, mais le CSV est bel et bien trié par code barre quand on le récupère (ordre lexicographique).

C’est le nombre de lignes qui compte, pas le nombre de bytes du fichier. Tu surestimes "beaucoup" (ça reste qu’un log) la longueur de ta boucle. Tu pourrais plutôt boucler jusqu’à ce que maxi et mini sont à un readline d’écart (en faisant gaffe que l’astuce avec readline() permette à cette situation d’arriver et ne laisse pas de trou dans l’exploration, sinon t’es pas bon de toute façon).

Ah, vraiment ? Pourtant, ne connaissant pas le nombre de lignes en avance (contrairement au nombre d’octets que l’OS connaît), je saute bien d’offset en offset et non pas de ligne en ligne.

Je ne me souviens plus exactement comment j’avais trouvé ce résultat. Par tâtonnement, je pense. J’ai calculé le nombre d’itérations pour le pire des cas (première ligne) et j’ai dû remarquer que ça tombait plutôt juste comme ça.

EDIT : au fait math.log2 existe directement.

Bien vu, je n’avais jamais fait attention.

+0 -0

Ah, vraiment ? Pourtant, ne connaissant pas le nombre de lignes en avance (contrairement au nombre d’octets que l’OS connaît), je saute bien d’offset en offset et non pas de ligne en ligne.

Certes, mais ça c’est juste un détail d’implémentation dû au fait que se déplacer de ligne en ligne est lent par rapport à un seek. De fait, avec ta combinaison de seek et de readline(), tu te déplaces sur les lignes mais de façon intelligente au vu du fonctionnement des stream. La recherche par bissection est faite sur les lignes, pas sur les octets du fichier. Une façon triviale de le voir est de prendre un fichier de 3 lignes. Deux itérations suffisent au pire (ligne du milieu et ligne au-dessus ou en-dessous) alors que log2(s)+1\log_2(s) + 1 peut être arbitrairement large. Évidemment, si tu as une seule ligne très grande en fin de fichier, ta méthode s’écroule parce que tu vas commencer par tester la dernière ligne plusieurs fois et effectivement te retrouver avec log2(s)\log_2(s) itérations dans le pire des cas. Je suppose que tes lignes sont équilibrées (si elles ne le sont vraiment pas, l’algo n’est pas très bon de toute façon, il faudrait ajouter une vérification que tu as bien changé de ligne d’une itération à l’autre).

L’approximation fonctionne bien par ailleurs parce qu’on parle d’une complexité en log. Même si tes lignes font 1 ko chacune, tu ajoutes 10 itérations au pire.

+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