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

Posté par (page perso) .
Tags : aucun
0
26
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 (page perso) . É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 (page perso) . É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 (page perso) . É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..)
      • [^] # Re: rand($.) < 1 && ($line = $_) while <>

        Posté par (page perso) . É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 (page perso) . É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 (page perso) . É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 ?
          • [^] # Re: rand($.) < 1 && ($line = $_) while <>

            Posté par (page perso) . É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 (page perso) . É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 :-)
          • [^] # Re: rand($.) < 1 && ($line = $_) while <>

            Posté par . É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 (page perso) . É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 . É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 . É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 à ceux qui les ont postés. Nous n'en sommes pas responsables.