Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Discussion: Croiser deux fichiers

  1. #1
    Membre régulier
    Homme Profil pro
    Développeur Java
    Inscrit en
    mars 2007
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Industrie

    Informations forums :
    Inscription : mars 2007
    Messages : 154
    Points : 89
    Points
    89

    Par défaut Croiser deux fichiers

    Bonjour,

    Je voudrais ouvrir une discussion au sujet d'un problème qui a été posé dans une école d'ingénieur il y a quelques semaines. J'ai actuellement un stagiaire qui terminera ses études en juin 2019, il m'a alors donné l'énoncé. Cependant... j'ai un peu de mal à m'y mettre.

    Imaginons un très gros fichiers ARCHIVES qui contiennent les archives de familles dans un département, certaines remontant jusqu'au XVI siècle. Un million de personnes y sont enregistrées, chacune d'elle respectant la structure de données suivantes :
    - un identifiant unique [donc une clé],
    - le nom de la personne, lequel peut être composé de plusieurs mots séparés par un blanc,
    - les prénoms de la personne, séparés par un blanc (pas de tiret comme par exemple Jean-Luc),
    - les identifiants de la mère et du père, par défaut 0 s'ils ne sont pas connus.

    Ainsi, ce fichier ARCHIVES permet de dresser des arbres généalogiques. Ce fichier est réputé ne contenir aucune erreur d'orthographe ou de saisie. Cependant, l'ordre des prénoms n'est pas garanti. De même, les mots composant le nom peuvent être intervertis.

    Propriétés de ARCHIVES :
    - En moyenne, la profondeur des généalogies est 5 générations ,
    - En moyenne, chaque personne a 4 enfants.

    C'est alors que la Préfecture envoie une liste de 18000 personnes, NOTABLES, structuré comme suit :
    - identifiant unique,
    - nom de la personne, pouvant être composé de plusieurs mots, alors séparés par un blanc,
    - prénoms, avec la même propriété/contrainte que le nom.

    Propriétés de NOTABLES :
    - En moyenne, le nom de chaque personne est composé de 2 noms, le maximum répertorié est 6,
    - Quant aux prénoms, la moyenne est de 3 par personne, le maximum étant de 6.

    Les identifiants des deux fichiers sont indépendants.

    Les fichiers ARCHIVES et NOTABLES peuvent être stockés en mémoire.

    Arrivent donc les questions :
    1) La Préfecture demande d'identifier les personnes du fichier NOTABLES dans ARCHIVES, en insistant sur la nécessité que les noms et prénoms doivent correspondre en nombre et ordre des mots. Par exemple Louis Georges DU VALNEUF n'est pas la même personne que Georges Louis DU VALNEUF.

    2) Même question, mais l'ordre des prénoms des personnes peut être quelconque dans les deux fichiers. Il est donc possible qu'il y ait des homonymies.

    Dans les deux questions, concevoir un algorithme rapide et performant qui permette de marquer les personnes de NOTABLES qui seraient identifiées dans ARCHIVES.
    Voici donc ma propre réflexion :

    Chercher 18 000 personnes et balayer un fichier de 1 000 000 personnes par deux boucles imbriquées, cela me semble très naïf et surtout désastreux : cela représente quand même 18 milliards de recherche, nombre très élevé.

    Je suppose qu'il y a donc un travail de préparation, comme par exemple trier une fois pour toutes les deux fichiers, puisque l'énoncé n'indique pas qu'il y ait le moindre tri. Le tri s'effectue sur le nom puis les prénoms. Les noms les plus courts sont placés avant les plus longs, si les premiers constituent les lettres des derniers, par exemple : DE MARIA est placé avant DE MARIANT. Si les noms sont identiques, les prénoms constituent le second discriminant.

    Mais là, ça coince pour moi : existe-t-il un moyen de trier 1 000 000 de personnes "rapidement" ? Comme il est dit que ce fichier peut-être placé en mémoire, je me dis que la solution réside là. J'ai bien un algorithme à proposer qui procède à un balayage unique et simultané des deux fichiers.

    De même, les clés d'identification ne servent nullement ici, bien qu'elles puissent être employées à marquer les personnes qui sont présentes dans les deux fichiers.

    Merci par avance de vos remarques, critiques, observations, conseils...

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    Je viens de faire l'expérience avec Excel. J'ai généré 1 000 000 de nombres aléatoires. Et j'ai demandé à Excel de trier ces nombres. Le tri s'est fait en 2 secondes environ.
    Même expérience avec des chaines de caractères, le tri s'est fait en 5 secondes environ.
    Et même expérience, avec 2 colonnes de texte, et j'ai demandé de trier sur Colonne A // colonne B en cas de doublon sur la colonne A. Le tri s'est fait en 5 secondes environ.

    Oui, je pense que dans la réponse à cet exercice, on peut dire : 'on trie le fichier Archives sur Nom+Prénom'.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre régulier
    Homme Profil pro
    Développeur Java
    Inscrit en
    mars 2007
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Industrie

    Informations forums :
    Inscription : mars 2007
    Messages : 154
    Points : 89
    Points
    89

    Par défaut

    Bonsoir tbc92,

    Merci pour ta réponse. J'ignorais que Excel était capable d'une telle prouesse, ce qui est véritablement impressionnant. Un poignée de secondes pour trier un million d'articles, cela mérite le respect. J'ai bien envie demain de tenter l'expérience en Java en exécutant un tri par pivot sur une liste aléatoirement constituée.

    Bien entendu, j'en profiterai pour élaborer les deux algorithmes demandés dans ce DS. Petite chose, il y avait quatre questions en tout, pour une heure en tout ! A priori, cet exercice devait être bouclé en environ 30 minutes.

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    23 919
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 23 919
    Points : 153 156
    Points
    153 156

    Par défaut

    Si tu as accès à la bibliothèque standard de Java, avec Arrays.sort(), ça doit être plié en un rien de temps (pour le code au moins). Sinon, au niveau algorithmique, j'aurais tendance à proposer une variante du tri par fusion : tu peux effectuer un tri sur les deux fichiers séparément ; ensuite, retrouver les correspondances se fait très vite (tu passes les items de l'autre tableau jusqu'à trouver celui que tu cherches, sans besoin de faire une recherche exhaustive). Tu aurais donc un appel récursif du tri par fusion (libre à toi de faire ce que tu veux pour chacun des fichiers) ; l'opération de fusion serait adaptée à ton besoin (mais en suivant la même pensée pour l'implémentation). (https://tcuvelier.developpez.com/tut...onnees/#LIII-C, https://fr.wikipedia.org/wiki/Tri_fusion, par exemple.)
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre régulier
    Homme Profil pro
    Développeur Java
    Inscrit en
    mars 2007
    Messages
    154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Industrie

    Informations forums :
    Inscription : mars 2007
    Messages : 154
    Points : 89
    Points
    89

    Par défaut

    Bonjour,

    J'ai fait l'expérience en ce début d'après-midi en langage Java, j'avoue être bluffé. En instaurant un simple tri par pivot sur une liste de 1 000 000 éléments (ArrayList<Integer> pour ceux qui connaissent), il faut 4 secondes pour générer la liste, et environ 12 pour faire le tri sachant que les doublons sont autorisés. De même, le pivot est choisi de façon aléatoire.

    Ainsi donc, la lecture et le tri des fichiers ARCHIVES et NOTABLES ne demandent pas beaucoup de temps, à peine une minute pour les deux.

    Je souligne bien que je n'ai pas utilisé des tableaux, ce qui devrait normalement être plus performant. Je passe donc à la seconde phase, à savoir construire une classe Personne ayant pour attributs Nom et Prenom, puis à nouveau opérer un tri dessus. Dès que c'est fait, je reviens vers vous.

    Naturellement, je peux mettre à disposition le code source Java.

    Citation Envoyé par dourouc05 Voir le message
    Si tu as accès à la bibliothèque standard de Java, avec Arrays.sort(), ça doit être plié en un rien de temps (pour le code au moins). Sinon, au niveau algorithmique, j'aurais tendance à proposer une variante du tri par fusion : tu peux effectuer un tri sur les deux fichiers séparément ; ensuite, retrouver les correspondances se fait très vite (tu passes les items de l'autre tableau jusqu'à trouver celui que tu cherches, sans besoin de faire une recherche exhaustive). Tu aurais donc un appel récursif du tri par fusion (libre à toi de faire ce que tu veux pour chacun des fichiers) ; l'opération de fusion serait adaptée à ton besoin (mais en suivant la même pensée pour l'implémentation). (https://tcuvelier.developpez.com/tut...onnees/#LIII-C, https://fr.wikipedia.org/wiki/Tri_fusion, par exemple.)
    Merci pour le conseil, je suis bien décidé à me pencher sur cette problématique d'algorithmes de tri.

Discussions similaires

  1. [OS X] [SH] Croiser deux fichiers csv sur plusieurs critères
    Par medmaysais dans le forum Shell et commandes POSIX
    Réponses: 3
    Dernier message: 19/04/2016, 22h25
  2. Code VBA afin de croiser deux fichiers excel avec un SI et un rechercher V
    Par rodriguez nzuzi dans le forum Général VBA
    Réponses: 1
    Dernier message: 12/12/2015, 02h16
  3. Concaténer deux fichiers Ligne/Ligne avec SH
    Par guiltouf dans le forum Linux
    Réponses: 7
    Dernier message: 22/05/2007, 15h35
  4. Réponses: 22
    Dernier message: 29/01/2005, 12h29
  5. Réponses: 5
    Dernier message: 09/01/2005, 20h54

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo