AccueilAccueil  FAQFAQ  RechercherRechercher  Dernières imagesDernières images  S'enregistrerS'enregistrer  Connexion  
Le Deal du moment : -50%
-50% sur les sacs à dos pour ordinateur ...
Voir le deal
19.99 €

 

 Recherche rapide dans un index

Aller en bas 
5 participants
AuteurMessage
Mass
*Excellent utilisateur*
Mass


Messages : 3351
Localisation : Dans une canonnière wookie.
Projet Actuel : Monter des trucs et des machins

Recherche rapide dans un index Empty
MessageSujet: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 14:03

Hello,

Je bosse sur un script de recherche, j'ai une base de données de mots faite à la main et pour chaque mot, je stocke son offset dans le fichier de la base de donnée. Mais du coup, je dois être capable de récupérer l'offset d'un mot connu sur un très grand nombre d'enregistrements (~1M).

Donc à l'heure actuelle j'ai fait un fichier index et je me base sur un hash (md5 soit 16 bytes) pour identifier le mot et le retrouver. J'ai bricolé un truc : je sépare l'index en plein de fichiers nommés wordsXX.index où XX sont les 2 premiers bytes du hash sous forme hexa.
Ensuite je parcours l'index, je le divise en chunks de 22 bytes (14 bytes pour la fin du hash et 8 bytes pour l'offset).
En gros c'est une rustine pour réduire mécaniquement la taille de l'index à parcourir en faisant un premier tri grâce au système de fichier.

Je cherche un moyen plus propre de faire ça, c'est à dire un index en un seul fichier. Ca se fait comment, ce genre de choses, pour que ce soit optimisé ? Car parcourir 1M d'enregistrements à chaque recherche ça me semble lourd, avec 24 bytes par entrée ça fait 24mo à parcourir, même en RAM y'a pas moyen d'organiser la structure du fichier d'une meilleure façon qu'à la force brute ?

Merci pour vos conseils gnii

_________________
Revenir en haut Aller en bas
http://madmass.mype.fr/CBNA/
Mobi
Utilisateur confirmé: Rang ****
Mobi


Messages : 1256
Localisation : Dijon

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 16:42

A tout hasard ça serait pas mieux de tout faire avec des requêtes SQL ?

(tu passes quand sur skype ?)

_________________
Recherche rapide dans un index Penguin
Revenir en haut Aller en bas
Mass
*Excellent utilisateur*
Mass


Messages : 3351
Localisation : Dans une canonnière wookie.
Projet Actuel : Monter des trucs et des machins

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 17:19

Chuis pas chez moi je rentre vendredi gnii

Au début je fonctionnait avec un SQL effectivement mais c'est absolument pas fait pour des volumes de données pareils, c'est pour ça que j'ai refait un système à la main qui est bien plus rapide et économe en IO et espace disque.

_________________
Revenir en haut Aller en bas
http://madmass.mype.fr/CBNA/
Mobi
Utilisateur confirmé: Rang ****
Mobi


Messages : 1256
Localisation : Dijon

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 18:33

SQL est fait pour les volumes énormes normalement :/

_________________
Recherche rapide dans un index Penguin
Revenir en haut Aller en bas
Mass
*Excellent utilisateur*
Mass


Messages : 3351
Localisation : Dans une canonnière wookie.
Projet Actuel : Monter des trucs et des machins

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 21:09

Non SQL c'est fait pour traiter des requêtes sur les données, les croiser, etc. Ca commence à pas bien marcher passé le million d'enregistrements :/

_________________
Revenir en haut Aller en bas
http://madmass.mype.fr/CBNA/
Mobi
Utilisateur confirmé: Rang ****
Mobi


Messages : 1256
Localisation : Dijon

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 21:35

Autant pour moi mais je ressors ce que j'apprend en cours :p

_________________
Recherche rapide dans un index Penguin
Revenir en haut Aller en bas
Asu
Utilisateur confirmé: Rang ****
Asu


Messages : 895

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyLun 24 Aoû 2015 - 21:40

Tu ne peux pas reproduire ce que tu faisais avec les différents fichiers au sein du même fichier, en classant les mots par les deux premiers octets de leur MD5 et en définissant l'offset du début de chaque catégorie dans un header de ce fichier?

@Mobi si en cours on te dit que SQL est fait pour ça alors j'ose pas imaginer de ce qu'ils pensent de Java Yum!

_________________
‎<‎Cysteine‎>‎ nON mais la touche maj s'active/se désactive toute seule
‎<‎Cysteine‎>‎ et a du mal à réponDRE QUANd j'appuie dessus
‎<‎Cysteine‎>‎ et je l'ai démont2? IL Ny a rien DEDANs
Revenir en haut Aller en bas
Mass
*Excellent utilisateur*
Mass


Messages : 3351
Localisation : Dans une canonnière wookie.
Projet Actuel : Monter des trucs et des machins

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyMar 25 Aoû 2015 - 1:47

Le problème c'est qu'il faut pouvoir ajouter des enregistrements à l'index. Du coup, il faut soit :
- Prévoir pour chaque couple de premiers bytes suffisamment d'espace libre avant le prochain dans le fichier (prend de la place inutilement)
- ou décaler tous les offsets à chaque enregistrement (donc réécrire l'index, à voir)
- ou stocker plusieurs offsets de façon à stocker les enregistrements de façon discontinue.

Je suis curieux de savoir comment ça se fait dans les logiciels de DB courants justement gnii

_________________
Revenir en haut Aller en bas
http://madmass.mype.fr/CBNA/
Térence
Utilisateur confirmé: Rang *****
Térence


Messages : 2213
Localisation : Oui

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyMar 25 Aoû 2015 - 13:32

Pas tout capté pour ton histoire d'offset, donc je donne que des idées, je sais pas si c'est faisable :
1- utiliser un peu le même genre de truc que ton système de fichier, mais avec SQL justement : au lieu de faire pleins de fichier wordsXX, tu ferais plein de tables wordsXX, du coup ca te diviserait pas mal le nombre de mots à checker (comme avec ton système de fichiers), sauf que ce serait un peu plus propre justement. C'est pas souvent utilisé, mais il existe bien sûr des commandes SQL pour créer des nouvelles tables.
2- tout simplement trier tout ca : pour ton million d'entrée, bah tu fais tourner l'algo pour le trier (par ordre alphabétique je dirais), puis ensuite, quand tu veux ajouter une nouvelle entrée ou en chercher une, tu fais une recherche dichotomique, et là t'économise un max de temps (une vingtaine de recherche dans le pire des cas pour 1M apparemment).

Voilà, je sais pas si ca te sert à quelque chose mais bon gnii


_________________
Je suis partie sur les ailes du vent et la tempête m'a ramenée.
Revenir en haut Aller en bas
Mass
*Excellent utilisateur*
Mass


Messages : 3351
Localisation : Dans une canonnière wookie.
Projet Actuel : Monter des trucs et des machins

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyMar 25 Aoû 2015 - 18:03

Simple : on ne sait pas combien d'éléments il y aura au final dans la base. Du coup quand tu dois ajouter un élément, si ils sont triés en fonction des deux premiers bytes de leur hash, il faudra à chaque fois :
1) Décaller tout le reste du fichier pour conserver un tri correct -> réécrire toute la base
2) Décaller tous les offsets supérieurs à l'offset du nouvel enregistrement -> des centaines de milliers d'op en langage de script + réécriture de l'index

Du coup le soucis de faire un tri "alphabétique" du hash c'est que à chaque nouvelle entrée il faut refaire le tri, c'est à dire réécrire toute la base, et ça fait un paquet d'I/O complètement inutiles triste2

Pour ce qui est de SQL je ne l'utilise pas. Ma précédente version utilisait MySQL et il n'est pas fait pour stocker des montants de données pareils. En outre, en créant ma propre structure au niveau binaire, j'économise beaucoup de place et je peux optimiser le stockage en fonction de mon usage gnii Ca permet de faire les I/O à un plus bas niveau qu'avec SQL.

_________________
Revenir en haut Aller en bas
http://madmass.mype.fr/CBNA/
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index EmptyMar 25 Aoû 2015 - 19:54

J'ai lu en diagonale mais un mot me viens en tête: arbre (lexicographique)

_________________
Recherche rapide dans un index Runningpotato1Recherche rapide dans un index TvF6GED Recherche rapide dans un index MdetltS
Revenir en haut Aller en bas
Contenu sponsorisé





Recherche rapide dans un index Empty
MessageSujet: Re: Recherche rapide dans un index   Recherche rapide dans un index Empty

Revenir en haut Aller en bas
 
Recherche rapide dans un index
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Programmation-
Sauter vers: