Forum Programmation.c Accès aléatoire à un fichier d'un répertoire

Posté par ploum (site web personnel, Mastodon) le 26 août 2004 à 22:09.

Étiquettes : aucune

août

2004

(et oui, ce soir, je fais du C ;-) )

la fonction que je suis en train d'écrire reçoit en paramètre le nom d'un répertoire.
Elle renvoie un fichier, le plus aléatoire possible, contenu dans le répertoire ou le sous-répertoire.
Le problème, c'est que je viens de me rendre compte qu'en la faisant récursive, plus un fichier est profond dans la structure, moins il a de chances d'être choisi. Et j'aimerais que chaque fichier aie sa chance de manière équitable.

Les fichiers doivent pouvoir changer souvent, et un nouveau fichier doit avoir autant de chance que les autres d'être sélectionné même si on ajoute le fichier alors que le programme est lancé.

La seule solution que je vois actuellement :

- construction d'une table des fichiers "applatis" lors du démarage du programme et reconstruction de cette table lorsque que quelque chose change dans le répertoire (notification via FAM ou D-bus, c'est pas le plus urgent, ça peu attendre).

Seulement, je dois l'avouer, ce design ne me plait pas du tout. J'aimerais accéder directement au fichier, pas à une table qu'il faut construire, ce qui peut être lourd si l'arborescence est fournie.

Merci aux codeurs qui me lisent ce soir ;-)

# rand($.) < 1 && ($line = $_) while <>

Posté par Krunch (site web personnel) le 26 août 2004 à 22:27. Évalué à 3.
En Perl quand on veut prendre un élément aléatoire d'une liste dont on ne connait a priori pas la taille, on fait comme ça:
rand($.) < 1 && ($line = $_) while <>;
(ça vient de la FAQ qui dit que ça vient du Camel Book) En C ça donnerait un truc dans ce genre là:
```
i = 1;
while (file = next_file()) {
  if (rand(i) < 1)
    result = file;
  i++;
}
```
Avec rand(x) qui retourne un nombre aléatoire strictement compris entre 0 et 1 et next_file() qui retourne le fichier suivant (en allant fouiller récursivement) ou 0 si c'était le dernier. Il y a surement moyen de faire plus rapide si on sait à l'avance à quoi ressemble le répertoire en utilisant un fichier d'index ou quelque chose comme ça et ça éviterait les "race conditions". Pour ça je pense que tu pourrais t'inspirer des programmes fortune et strfile. PS: c'est embétant de pas avoir droit à la balise <br>.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
- [^] # Re: rand($.) < 1 && ($line = $_) while <>
  
  Posté par Krunch (site web personnel) le 26 août 2004 à 22:29. Évalué à 2.
  
  Avec rand(x) qui retourne un nombre aléatoire strictement compris entre 0 et 1
  entre 0 et x bien sur
  pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
- [^] # Re: rand($.) < 1 && ($line = $_) while <>
  
  Posté par ploum (site web personnel, Mastodon) le 26 août 2004 à 22:44. Évalué à 2.
  
  Y'a un truc que je pige pas.
  
  Le premier fichier à une chance de 1 d'être sélectionné : rand(1) < 1 est toujours vrai.
  
  Et ensuite, plus tu augmentes, moins le fichier à des chances d'être sélectionné.
  
  Je me gourre ou c'est toi ? ;-) (la première solution est fort possible hein, je dis pas..)
  Mes livres CC By-SA : https://ploum.net/livres.html
  - [^] # Re: rand($.) < 1 && ($line = $_) while <>
    
    Posté par Krunch (site web personnel) le 26 août 2004 à 23:00. Évalué à 2.
    
    D'après la FAQ Perl:
    You can find a proof of this method in The Art of Computer Programming, Volume 2, Section 3.4.2, by Donald E. Knuth.
    J'ai mis du temps à comprendre comment ça marche mais ça marche et tous les fichiers ont autant de chance d'être sélectionnés (et sans lire le bouquin en question :op).
    
    Le 1er à 100% de chance d'être sélectionné, forcément. Le deuxième a une chance sur deux d'être sélectionné donc 50% pour le 1er, 50% pour le 2ème. Le 3ème a 1/3 d'être pris donc 1/3 pour le 3ème, (2/3)*(1/2) = 1/3 pour le 2ème et pareil pour le 3ème et ainsi de suite.
    
    Doit y avoir moyen de démontrer ça mathématiquement par récurrence mais je suis en vacances là :op
    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
    - [^] # Re: rand($.) < 1 && ($line = $_) while <>
      
      Posté par Krunch (site web personnel) le 26 août 2004 à 23:02. Évalué à 2.
      
      Au fait j'y pensait pas mais elle est aussi en HTML sur internet cette FAQ: http://faq.perl.org/perlfaq5.html#How_do_I_select_a_ra(...)
      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
    - [^] # Re: rand($.) < 1 && ($line = $_) while <>
      
      Posté par ploum (site web personnel, Mastodon) le 26 août 2004 à 23:15. Évalué à 2.
      
      Le 1er à 100% de chance d'être sélectionné, forcément.
      
      Ben donc, l'algo s'arrête à tout les coup sur le premier. Et c'est pas aléatoire du tout.
      
      Me trompe-je ?
      Mes livres CC By-SA : https://ploum.net/livres.html
      - [^] # Re: rand($.) < 1 && ($line = $_) while <>
        
        Posté par Krunch (site web personnel) le 26 août 2004 à 23:29. Évalué à 3.
        
        Non le premier est selectionné mais tu continues quand même jusqu'à ce que tu ais parcouru tous les fichiers et tu ne retourne le résultat qu'une fois la boucle terminée.
        pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
        
        [^] # Re: rand($.) < 1 && ($line = $_) while <>
        
        Posté par ploum (site web personnel, Mastodon) le 26 août 2004 à 23:46. Évalué à 2.
        
        wééé ! compris...
        
        Je suis con. Mais au final, t'as quand même parcouru tous les fichiers. Mais j'ai réfléchi, et j'ai je crois démontré que ce que j'avais exactement en tête est en fait impossible.
        
        Donc je me tourne vers autre chose. Néanmoins, je note l'algo dans un coin de ma tête. Merci :-)
        Mes livres CC By-SA : https://ploum.net/livres.html
      - [^] # Re: rand($.) < 1 && ($line = $_) while <>
        
        Posté par iznogoud le 26 août 2004 à 23:40. Évalué à 3.
        
        tu te trompè-je.
        On reprend (d'ailleurs l'algo est vraiment astucieux je trouve)
        
        i = 1;
        while (file = next_file()) {
        if (rand(i) < 1)
        result = file;
        i++;
        }
        
        Donc, tu prends result qui au début ne contient rien.
        Puis, tu as result qui fait effectivement file1.
        Ensuite, tu as une chance sur deux pour que result prenne la valeur file2, puisque tu as une chance sur deux pour avoir rand(2) < 1, et l'autre chance est à file1.
        Donc pour l'instant, ça marche pour deux fichiers dans next_file()
        
        Si ça marche pour n fichiers, tu as alors une chance sur n d'avoir result=filex, avec x entre 1 et n.
        Bon, on rajoute un fichier. On fait donc une nouvelle boucle. Tu as alors 1/(n+1) chance de tomber sur rand(n+1) < 1.
        Et les autres valeurs de result suivent du même coup (cette étape je saurai pas te l'expliquer simplement, j'ai laissé mes maths de côté depuis trop longtemps, mais on sent bien que c'est ce que ça fait).
        
        Donc ça marche.
        
        [^] # Re: rand($.) < 1 && ($line = $_) while <>
        
        Posté par Krunch (site web personnel) le 26 août 2004 à 23:57. Évalué à 3.
        
        Si on pose que ça marche pour le n ème fichier, chacun de ces n fichier a 1/n chance d'avoir été choisi. Pour le n+1 ème fichier tu as donc 1/(n+1) chance pour que le fichier soit choisi et n/(n+1) chance pour que ça soit un fichier précédent. Parmis ces fichiers précédent, il y a 1/n pour que ça soit un fichier donné donc ça fait (1/n)*(n/(n+1)) = 1/(n+1) chance pour chacun de ces n fichiers. Chacun des n+1 fichiers a donc autant de chance que les autres d'être pris. Suffit donc de démontrer que pour n = 1 ça marche et c'est évident. Comme pour n+1 ça marche, ça marche pour tout n naturel zéro non compris (enfin c'est un cas spécial et on peut considérer ou non que ça marche mais j'ai pas envie de m'aventurer la dedans).
        
        Arg j'ai fait une démonstration en dehors de mon cour de math, au secours.
        pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
        
        [^] # Re: rand($.) < 1 && ($line = $_) while <>
        
        Posté par iznogoud le 27 août 2004 à 02:47. Évalué à 2.
        
        ben pour le cas n=0 c'est trivial : result n'est pas initialisé, tu ne rentres pas dans la boucle, donc tu as bien les chances de tomber sur le fichier x (qui bien sûr n'y est pas puisque c'est vide, mais on s'en fiche c'est pour la démo), qui sont nulles.
  - [^] # Re: rand($.) < 1 && ($line = $_) while <>
    
    Posté par grafit le 27 août 2004 à 08:56. Évalué à 2.
    
    Le premier fichier à une chance de 1 d'être sélectionné : rand(1) < 1 est toujours vrai.
    Et ensuite, plus tu augmentes, moins le fichier à des chances d'être sélectionné.
    
    le premier est selectionné à 100% au premier pas de l'algo, mais par la suite il y a très peu de chance que tous les rand suivants soient >= 1.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.