Discussion :

[DomIII]

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...

[tbc92]

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

[DomIII]

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.

[dourouc05]

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.)

[DomIII]

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.

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.