IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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

Algorithmes et structures de données Discussion :

Trouver la médiane d'un tableau


Sujet :

Algorithmes et structures de données

  1. #41
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par mat1554 Voir le message
    Ouep, mais bon en gros le prof disait de pas toucher au valeur, en parlant de tri. Mais je crois que retirer reviens a touché au valeur aussi ^^.
    Tu peux swapper les min/max en fin de liste, et itérer sur le tronçon qui reste.

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int[] list = {12, 5, 6, 89, 5, 2390, 1};
    int length = list.length;
     
    while (length>2) {
    	int index_min = indexOfMin(list, 0, length); 
    	swap(list, index_min, length-1);
    	length--;
     
    	int index_max = indexOfMax(list, 0, length); 
    	swap(list, index_max, length-1);
    	length--;
    }
     
    if (length==2) System.out.println((list[0]+list[1])*0.5);
    if (length==1) System.out.println(list[0]);

    Ou alors, comme le dit prgasp77, utiliser une liste des index à "oublier".
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #42
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Algo bête et méchant:
    En fait, je pensais (je vérfierais demain) faire la même idée que j'ai expoée plus haut (qui donne une seule itération pour tout sauf le premier cas (4) et le cas de puissance, qui donne x fois N, x étant la puissance), mais en prenant une valeur relative (qui correspond un peu à l'idée de ton algo

    Je vous tiens au courant demain..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  3. #43
    Membre éprouvé
    Avatar de Celelibi
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    1 087
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 1 087
    Points : 1 122
    Points
    1 122
    Par défaut
    Ce que je peux te proposer comme algo bête en O(N²), si tu ne veux pas du tout toucher au tableau, c'est :
    Prendre une valeur de référence, et parcourir le tableau pour à la fois compter le nombre de valeurs inférieures à la référence, et aussi trouver la plus petite valeur strictement supérieure à la valeur de référence (qui serait la suivante si le tableau était trié).
    Et de recommencer avec la valeur suivante comme valeur de référence tant que le comptage des valeurs inférieures à la référence n'est pas suffisant.

    Sous forme de pseudocode, ça donne ça :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    ref = min(tab)
     
    faire
        inf = 0
        mult = 0
        next = tab(1)
        pour I de 1 à N faire
            si tab(I) < ref alors
                inf = inf + 1
            sinon si tab(I) == ref alors
                mult = mult + 1
            sinon si tab(I) > ref et tab(I) < next alors
                next = tab(I)
            fin si
        fin pour
     
        si N est impaire alors
            si inf == (N-1)/2 alors
                // Cas classique N impaire
                retourner ref
            sinon si inf + mult >= (N-1)/2 alors
                // Cas où les multiplicités incluent la médiane [0, 1, 1, 2, 3]
                retourner ref
            fin si
        sinon
            // N est paire
            si  inf == (N/2)-1 alors
                // Cas classique N paire
                retourner (ref + next) / 2.0
            sinon si inf + mult == N/2 alors
                // Cas où les multiplicités "touchent" la médiane [1, 1, 2, 3]
                retourner (ref + next) / 2.0
            sinon si inf + mult > N/2 alors
                // Cas où les multiplicités incluent la médiane [1, 1, 1, 3]
                retourner ref
            fin si
        fin si
     
        ref = next
    C'est une adaptation du tri par sélection. Sauf qu'on ne touche pas au tableau.
    (Y'a beaucoup de if pour gérer les cas spéciaux avec les multiplicité, mais c'est pas complique.)
    Les vaches ne peuvent PAS voler, quoi qu'elles aient pu vous raconter.

  4. #44
    Membre régulier
    Homme Profil pro
    Inscrit en
    Juillet 2008
    Messages
    121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations forums :
    Inscription : Juillet 2008
    Messages : 121
    Points : 84
    Points
    84
    Par défaut
    Bon, j'ai fini pas faire 2 version fonctionnel. Je vous donne la version C#.

    Avec un demi-trie (la moyenne n'est pas ajouté. Donc le plusPetit que la moyenne ne fonctionne pas plus )

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
          public double determinerMedianeV8(int[] tab, out double moyenne, out int plusPetit)
            {
                int Indice = 0, Total = 0, ppMed = 0;
                int Tempo = 0;
                double Med = 0;
                bool isPair = false;
     
                if (NbrElement % 2 == 0)
                {
                    ppMed = NbrElement / 2;
                    isPair = true;
                }
                else
                {
                    ppMed = (NbrElement-1) / 2;
                }
     
                while (Indice <= ppMed)
                {
                    int Compare = Indice+1;
                    while (Compare < NbrElement)
                    {
                        if (tab[Compare] < tab[Indice])
                        {
                            Tempo = tab[Compare];
                            tab[Compare] = tab[Indice];
                            tab[Indice] = Tempo;
                        }
                        Compare++;
                    }
                    Indice++;
                }
     
                if (isPair)
                {
                    Med = (double)(tab[ppMed] + tab[ppMed - 1]) / 2;
                }
                else
                {
                    Med = (double)tab[ppMed];
                }
     
                moyenne = Total;
                plusPetit = NbrElement / 2;
                return Med;
     
            }

    Sans trier, simplement en calculant
    (il manque le calcul du nombre de valeur inf à la moyenne)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    public double determinerMedianeV9(int[] tab, out double moyenne, out int plusPetit)
            {
                int Indice = 0, nPP = 0, Tempo = -1, Total = 0;
                double Med = 0;
                int MedPos = NbrElement/2, Comparant = 0;
     
                bool isPair = false;
                if (NbrElement%2 == 0)
                {
                    isPair = true;
                }
     
                while (Indice < NbrElement)
                {
                    Total += tab[Indice];
                    Comparant = 0; //  Indice + 1;
    	            while (Comparant < NbrElement)
                    {
                        if (tab[Comparant] < tab[Indice])
                        {
                            nPP++;
                        }
                        Comparant++;
                    }
     
                    if (!isPair)
                    {
                        if (nPP == MedPos)
                        {
                            Med = tab[Indice];
                        }
                    }
                    else
                    {
                        if ((nPP == MedPos) && (Tempo == -1))
                        {
                            Tempo = tab[Indice];
                        }
                        else if ((nPP == MedPos-1) && (Tempo == -1))
                        {
                            Tempo = tab[Indice];
                        }
                        else if ((nPP == MedPos) && (Tempo > -1))
                        {
                            Med = (double) (Tempo+tab[Indice]) / 2;
                        }
                        else if ((nPP == MedPos-1) && (Tempo > -1))
                        {
                            Med = (double) (Tempo+tab[Indice]) / 2;
                        }   
                    }
                    nPP = 0;
                    Indice++;
                }
                moyenne = (double) Total / NbrElement;
     
     
                /*
                 * Seule bogue ici
                 */
                if (isPair)
                {
                    plusPetit = NbrElement / 2;     // A vérifier
                }
                else if (NbrElement == 1)
                {
                    plusPetit = 0;
                }
                else
                {
                    plusPetit = (NbrElement+1) / 2;
                }
                return Med;
            }
     
        }
    Un peu basé sur tous ce que vous avez dis xD

  5. #45
    Membre éprouvé
    Avatar de Celelibi
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    1 087
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 1 087
    Points : 1 122
    Points
    1 122
    Par défaut
    Ton premier algo est un vrai tri par sélection. Sauf que tu t'arrêtes au milieu. Il a l'avantage de pas avoir de cas particulier pour les mutiplicités. Mais a l'inconvénient d'être en O(N^2) et de modifier le tableau.


    Par contre j'ai pas compris ton deuxième algo.
    Les vaches ne peuvent PAS voler, quoi qu'elles aient pu vous raconter.

  6. #46
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Je reviendrais vers vous cette am, mais je crois que j'ai un algo en O(N log(log(M)) dans le pire des cas.... (sans tri, et qui pourrait se faire "in place").
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  7. #47
    Membre régulier
    Homme Profil pro
    Inscrit en
    Juillet 2008
    Messages
    121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations forums :
    Inscription : Juillet 2008
    Messages : 121
    Points : 84
    Points
    84
    Par défaut
    Citation Envoyé par Celelibi Voir le message
    Ton premier algo est un vrai tri par sélection. Sauf que tu t'arrêtes au milieu. Il a l'avantage de pas avoir de cas particulier pour les mutiplicités. Mais a l'inconvénient d'être en O(N^2) et de modifier le tableau.


    Par contre j'ai pas compris ton deuxième algo.
    Oui, en gros je tri jusqu’à valeur, donc ça limite ce que je le prof disait. «Le défi est de ne pas trie (du moins au complet)»

    O(n/2) et o(n) sont bien les seules que j'arrive a calculer ^^ Comme mon second vu que je parcours 2 fois, je crois que ça serait O(n²) ? Mais vraiment pas sûr.

    Cependant, dans la version avec tri, il me manque le calcul de la moyenne et du nombre de valeur plus petit que la moyenne.

    Et dans la seconde, du nombre de valeur plus petit que la moyenne.

    Donc, ça va encore modifié la complicité de O.

  8. #48
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    Je reviendrais vers vous cette am, mais je crois que j'ai un algo en O(N log(log(M)) dans le pire des cas.... (sans tri, et qui pourrait se faire "in place").
    En fait, c'est même en O(N log^c M), c >= 2.... (le ^ est pour le logarithme itéré).

    Donc potentiellement O(N)...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  9. #49
    Membre éprouvé
    Avatar de Celelibi
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    1 087
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 1 087
    Points : 1 122
    Points
    1 122
    Par défaut
    Bien, montre-nous ton algo.
    Au pire, on trollera sur la complexité.
    Les vaches ne peuvent PAS voler, quoi qu'elles aient pu vous raconter.

  10. #50
    Membre régulier
    Homme Profil pro
    Inscrit en
    Juillet 2008
    Messages
    121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations forums :
    Inscription : Juillet 2008
    Messages : 121
    Points : 84
    Points
    84
    Par défaut
    Citation Envoyé par Celelibi Voir le message
    Par contre j'ai pas compris ton deuxième algo.
    Oups j'avais sauté cette phrase en première lecture xD

    Enfaite, je prends chaque Indice du tableau, puis je compte le nombre de valeur inférieur.

    Ensuite, celui qui a NbrElement/2 élement inférieur. Bien ça me donne mon Median.

    Cependant, dans le cas d'un tableau de NbrElement pair, j'ai besoin de 2 nombre pour déterminer mon médiane sois : N/2 et N/2+1. Je cherche donc c'est 2 résultat.

  11. #51
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    Citation Envoyé par mat1554 Voir le message
    Le défi est de ne pas trie (du moins au complet)
    Mais raison de plus pour un quickselect. On ne trie que ce qu'il faut (c'est à dire que l'on positionne quelques éléments, et c'est tout). Pourquoi tourner autour du pot ?
    -- Yankel Scialom

  12. #52
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Celelibi Voir le message
    Bien, montre-nous ton algo.
    Au pire, on trollera sur la complexité.
    En fait, j'en ai 2..

    Un comme dérivé du premier que j'avais indiqué, qui est en O(N logc M), et l'autre linéaire, en O(N), ressemblant furieusement à ce qu'on peut lire dans les Selection algorithm à la rubrique Linear minimum/maximum algorithms.

    Je les posterrais tout à l'heure..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  13. #53
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    OK, alors voilà..


    • D'abord l'algo en O(N logc M)

      La remarque de base est que pour classer des points, on a juste besoin d'une fonction croissante... Le log est une fonction croissante.. Là je présente avec un log simple, mais on peut augmenter en doublant, triplant, etc (mais ça fait des expression plus complquées).

      La seconde remarque est que pour ne pas avoir de problèmes avec les logs, il faut que x soit > 0. Donc, dans le cas du log simple on se ramène à [1, +infini], pour le log double à [10, +infini], etc etc...

      Enfin, ça marche par dichotomie comme indiqué dans un de mes premiers posts..

      Note1 : comme je n'ai pas de 64 bits mais 32, j'ai testé avec 2^1000 et non 2^4000 ;

      Note2 : il reste un cas à problème : les cas dégénérés dans le cas impair.. J'ai la femme
      .


      Resultat :

      Moyenne 0.584856 et 3 iterations pour mediane
      Tableau 1 mediane 2

      Moyenne 0.415836 et 1 iterations pour mediane
      Tableau 2 mediane 2

      Moyenne 0.400515 et 1 iterations pour mediane
      Tableau 3 mediane 2

      Moyenne 0.345053 et 1 iterations pour mediane
      Tableau 4 mediane 1.5

      Moyenne 60.482 et 8 iterations pour mediane
      Tableau 5 mediane 2

      Moyenne 0.0752575 et 1 iterations pour mediane
      Tableau 6 mediane 0

    • Algo linéaire O(N) : aucun cas particulier.

      Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.

      Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..

      Donc normalement on devrait avoir au plus un facteur constant de 4 pour les cas impairs et 6 pour les cas pairs...



      Resultat :

      Moyenne 8 et 2 iterations pour mediane
      Tableau 1 mediane 2

      Moyenne 2 et 1 iterations pour mediane
      Tableau 2 mediane 2

      Moyenne 2 et 1 iterations pour mediane
      Tableau 3 mediane 2

      Moyenne 1.5 et 1 iterations pour mediane
      Tableau 4 mediane 1.5

      Moyenne 2.14302e+300 et 2 iterations pour mediane
      Tableau 5 mediane 2

      Moyenne 0.25 et 1 iterations pour mediane
      Tableau 6 mediane 0

    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  14. #54
    Membre régulier
    Homme Profil pro
    Inscrit en
    Juillet 2008
    Messages
    121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations forums :
    Inscription : Juillet 2008
    Messages : 121
    Points : 84
    Points
    84
    Par défaut
    Citation Envoyé par prgasp77 Voir le message
    Mais raison de plus pour un quickselect. On ne trie que ce qu'il faut (c'est à dire que l'on positionne quelques éléments, et c'est tout). Pourquoi tourner autour du pot ?
    Enfaite, il laisse possibilité de pas trier au complet. Mais si on peut y arriver sans rien trier du tous, c'est encore mieux selon moi

    Mais mes 2 algo fonctionnelle sont citer un peu plus haut.

  15. #55
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    [*]Algo linéaire O(N) : aucun cas particulier.

    Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.

    Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..
    J'ai l'impression que c'est équivalent à faire un équilibrage de deux listes "valeurs basses" et "valeurs hautes".

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    int[] list = {12, 5, 6, 89, 5, 2390, 1};
     
    List<Integer> low   = new LinkedList<Integer>();
    List<Integer> high  = new LinkedList<Integer>();
     
    // initial guess
    int pivot = computeArithmeticMean(list);
    for(int i=0;i<list.length;i++) 
    	if (list[i]<=pivot) low.add(list[i]); else high.add(list[i]);
     
    // Equilibrate the two lists by moving elements
    while(low.size() < high.size()) {
    	Integer minhigh = Collections.min(high);
    	low.add(minhigh); high.remove(minhigh);
    }
    while(low.size() > high.size()) {
    	Integer maxlow = Collections.max(low);
    	low.remove(maxlow); high.add(maxlow);
    }
     
    // display median
    Integer minhigh = Collections.min(high);
    Integer maxlow  = Collections.max(low);
    if (low.size()==high.size())
    	System.out.println((maxlow+minhigh)*0.5);
    else
    	System.out.println(minhigh);


    Auquel cas, je ne pense pas que la recherche des 2 candidats soit en O(1). C'est plutôt que tu profites de ta boucle d'équilibrage (en O(N)) pour identifier les 2 candidats.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #56
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Auquel cas, je ne pense pas que la recherche des 2 candidats soit en O(1). C'est plutôt que tu profites de ta boucle d'équilibrage (en O(N)) pour identifier les 2 candidats.
    Oui, j'aime bien le terme, et ça ressemble comme principe.... Bien que n'étant pas familier avec ces choes.....

    Comme on n'ordonne pas, on est obligé de passer à travers tous les points, du coup j'ai encadré la valeur de référence par une valeur sup et une valeur inf..

    Disons que je n'ai pas de gros tests à faire toruner, mais il me semble qu'au max on ne devrait tourner que très peu de fois (sans doute 2 itérations en moyenne) : soit on est au dessus et la valeur est celle du dessous, soit on est en dessous et la valeur est celle du dessus...

    M'enfin, peut-être que je me trompe...


    En fait, c'est comme si on avait ordonné et qu'on prenne le milieu, sauf qu'on n'ordonne pas et qu'on s'approche extrêmement vite.

    Il faudrait tester sur de très grands tableaux... En fait vraisemblablement le pire cas serait avec plein de valeurs autour de la moyenne...


    Bien entendu, on peut améliorer encore en divisant en intervalles (DPR)... Mais j'aime pas ce qui complique

    Mais en tous cas ça me semble simple, sans tri, et rapide....

    Quant à l'autre, avec un log double au lieu du log simple, ça devrait être pratiquement là aussi 2 itérations max.. (puisque là ça ferait log itéré 3 fois).. (mais faudrait régler le pbe des cas dégénérés impairs). Déjà avec un log simple pour des cas "normaux" (et pas du genre quil y a dans le test) ça devrait être très efficace.. (puisque c'est log(log))



    C'était le fun à chercher une solution
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  17. #57
    Membre éprouvé
    Avatar de Celelibi
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    1 087
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 1 087
    Points : 1 122
    Points
    1 122
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    D'abord l'algo en O(N logc M)

    La remarque de base est que pour classer des points, on a juste besoin d'une fonction croissante... Le log est une fonction croissante.. Là je présente avec un log simple, mais on peut augmenter en doublant, triplant, etc (mais ça fait des expression plus complquées).

    La seconde remarque est que pour ne pas avoir de problèmes avec les logs, il faut que x soit > 0. Donc, dans le cas du log simple on se ramène à [1, +infini], pour le log double à [10, +infini], etc etc...

    Enfin, ça marche par dichotomie comme indiqué dans un de mes premiers posts..

    Note1 : comme je n'ai pas de 64 bits mais 32, j'ai testé avec 2^1000 et non 2^4000 ;

    Note2 : il reste un cas à problème : les cas dégénérés dans le cas impair.. J'ai la femme
    .
    Deux remarques sur la forme :
    - Tu utilises un tableau temporaire. Donc quitte à avoir un algo qui nécessite un espace en O(N), autant faire un quickselect (qui sera en O(N) en temps) sur une copie du tableau.
    Cela dit, il est facile dans ton code se passer de ce tableau en utilisant log(tab[i]-min+1) chaque fois que tu utilises temp[i].
    - Je trouve que ta recherche de valeurs immédiatement supérieures et inférieures à la "médiane temporaire" est... compliquée. Ça n'est pourtant qu'une recherche de min et max.

    Et sur le fond, ce qui me dérange dans ton algo, c'est qu'en prenant le log des valeurs du tableau, on perd en précision. Les double ne sont pas des réels, ni même des rationnels limités à un intervalle. C'est un truc complètement bâtard avec un nombre de bits de mantisse limité. En bref : dans le cas général, l'exponentielle du log n'est pas égale à la valeur de départ.

    Mais même en imaginant qu'on ait des réels, prendre le log des valeurs ne fait que "resserrer" l'intervalle entre la valeur max et la valeur min.
    Si tu travailles sur des double, ton algo initial (sans prendre le log des valeurs) est en O(N*log((max-min)/delta)) avec delta le plus petit écart entre deux valeurs consécutives qu'on va noter delta = d1 - d2.

    Si tu travailles sur des entiers, delta = 1 et on avait noté précédemment max-min = M (sans le dire parce que c'était pas important).
    Maintenant, avec le log des valeurs, ton algo est en O(N*log( log(max-min)/(log(d1)-log(d2)) ))
    C'est pas très beau, on peut réécrire la partie à l'intérieur du premier log.
    log(max-min)/(log(d1)-log(d2)) = log(M)/log(d1/d2)
    Si d1 et d2 sont proches d1/d2 va tendre vers 1 par valeurs positives, donc log(d1/d2) va tendre vers 0. Donc log(M)/log(d1/d2) va augmenter rapidement quand d1 et d2 sont proches.

    Donc si on met des valeurs assez proches, ça fait exploser le nombre d'itérations (quand ça termine). Par exemple : {0, 1e-16, 2e-16, 1, 2}, il trouve la médiane (dont la valeur est approximative) en 52 itérations.
    (Parce que oui j'aime bien faire chier. )


    Citation Envoyé par souviron34 Voir le message
    Algo linéaire O(N) : aucun cas particulier.

    Le pirncipe de base est de trouver la moyenne, puis le point le plus proche dans le tableau (par valeur inférieure), puis à chaque fois qu'on explore de trouver les valeurs les plus proches, la plus proche superieure et la plus proche inférieure.

    Là si on n'a pas le résultat, on fait une sorte de dichotomie, mais simplement entre l'ancienne valeur et l'une ou l'autre.. On n'a donc que des valeurs du tableau initial... Et une convergence que je ne saurais pas analyser, mais il me semble en O(1) : on cherche juste parmi les 2 points voisins..

    Donc normalement on devrait avoir au plus un facteur constant de 4 pour les cas impairs et 6 pour les cas pairs...
    J'ai du mal à comprendre ton "délire" avec les "Delta0" quand il s'agit de trouver la valeur immédiatement supérieure ou inférieure à une valeur donnée. D'ailleurs l'initialisation Delta0 = minval/10.0 va être foireuse pour un minval négatif.

    Par contre cet algo c'est rien d'autre qu'une variante de l'algo dérivé du tri par sélection que j'ai présenté un peu plus haut. Il est en O(N²). Commencer avec la moyenne comme valeur initiale n'est qu'une heuristique. La médiane peut être aussi éloignée qu'on veut de la moyenne.
    Par exemple {0, 1, 2, 3, 4, 5, ... k, 2^4000}. Cet algo va faire (k-1)/2 itérations (c'est à dire O(N)). Et dans chaque itération il recherche la valeur immédiatement inférieure (en O(N)).


    Oui souviron, t'as tout à fait le droit de me trouver insolent. ^^
    Les vaches ne peuvent PAS voler, quoi qu'elles aient pu vous raconter.

  18. #58
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Vite fait :

    Citation Envoyé par Celelibi Voir le message
    Deux remarques sur la forme :
    - Tu utilises un tableau temporaire. Donc quitte à avoir un algo qui nécessite un espace en O(N), autant faire un quickselect (qui sera en O(N) en temps) sur une copie du tableau.
    Cela dit, il est facile dans ton code se passer de ce tableau en utilisant log(tab[i]-min+1) chaque fois que tu utilises temp[i].
    Oui, je l'avais noté au début de cette page (que ça pouvait être fait "in place") (post #46)

    Citation Envoyé par Celelibi Voir le message
    - Je trouve que ta recherche de valeurs immédiatement supérieures et inférieures à la "médiane temporaire" est... compliquée. Ça n'est pourtant qu'une recherche de min et max.
    Pas tout à fait : c'est pour limiter la dichotomie à une valeur correcte. C'est le min de la partie supérieure et le max de la partie inférieure. Elle est un tout petit peu alambiquée à cause de la définition de la médiane dans les cas dégénérés (<= par rapport à < )


    Citation Envoyé par Celelibi Voir le message
    Et sur le fond, ce qui me dérange dans ton algo, c'est qu'en prenant le log des valeurs du tableau, on perd en précision. Les double ne sont pas des réels, ni même des rationnels limités à un intervalle. C'est un truc complètement bâtard avec un nombre de bits de mantisse limité. En bref : dans le cas général, l'exponentielle du log n'est pas égale à la valeur de départ.
    On peut tout à fait s'en passer , et ne stocker que l'indice trouvé quand on cherche le plus proche en sortie. Et alors, au lieu de calculer l'exponentielle, on a la vraie valeur...




    Citation Envoyé par Celelibi Voir le message
    J'ai du mal à comprendre ton "délire" avec les "Delta0" quand il s'agit de trouver la valeur immédiatement supérieure ou inférieure à une valeur donnée. D'ailleurs l'initialisation Delta0 = minval/10.0 va être foireuse pour un minval négatif.
    J'ai fait ça vite fait.. On peut redresser en valeurs positives en soustrayant (puis ajoutant) minval..

    Le "délire" encore une fois est lié aux problèmes <= et <...


    Citation Envoyé par Celelibi Voir le message
    Oui souviron, t'as tout à fait le droit de me trouver insolent. ^^
    loin de moi cette idée..

    Je dis juste que c'est possible à faire, mais je n'ai pas que ça à faire, donc pour raffiner... Je présente une idée, sans plus.. Qui se passe de tris (ce qui était demandé) et semble tourner correctement (à quelques corrections à faire), tout en étant strictement < O(N2)...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  19. #59
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Bon, encore plus fort

    En mixant les 2 approches :


    Moyenne 0.584856 et 1 iterations pour mediane
    Tableau 1 mediane 2

    Moyenne 0.415836 et 1 iterations pour mediane
    Tableau 2 mediane 2

    Moyenne 0.400515 et 1 iterations pour mediane
    Tableau 3 mediane 2

    Moyenne 0.345053 et 1 iterations pour mediane
    Tableau 4 mediane 1.5

    Moyenne 60.482 et 2 iterations pour mediane
    Tableau 5 mediane 2

    Moyenne 0.0752575 et 1 iterations pour mediane
    Tableau 6 mediane 0

    Moyenne 0.15563 et 1 iterations pour mediane
    Tableau 7 mediane 2e-16

    Moyenne 5.566 et 20 iterations pour mediane
    Tableau 8 mediane 499998
    (pour le dernier tableau, j'ai pris 1 million de points croissants jusqu'à 999998 plus 1 point à 2^1000)

    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  20. #60
    Membre éprouvé
    Avatar de Celelibi
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    1 087
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 1 087
    Points : 1 122
    Points
    1 122
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    Bon, encore plus fort

    En mixant les 2 approches
    Effectivement, c'est une solution à laquelle j'avais vaguement pensé sans la formaliser. (Je me suis arrêté quand j'ai vu que sa complexité allait avoir un "min".)

    À chaque itération tu élimines au moins une valeur du tableau, et t'espères en moyenne* en éliminer la moitié. C'est donc du O(N*min(N, log(M)/log(d1/d2))) ou un truc du genre. C'est donc au pire du O(N²).

    Y'a juste un truc qui m'intrigue, c'est si on a plein de valeurs très proches et que le log les rend égales (parce qu'on est sur des double). Tu risques de pas pouvoir trouver la bonne valeur.

    * Pour avoir un cas moyen il faut trouver une hypothèse moyenne de répartition des valeurs entre min et max. Répartition uniforme peut-être ?
    Les vaches ne peuvent PAS voler, quoi qu'elles aient pu vous raconter.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Test pour trouver la fin d'un tableau
    Par apprentito dans le forum Cobol
    Réponses: 11
    Dernier message: 25/01/2008, 02h41
  2. Réponses: 7
    Dernier message: 21/01/2008, 16h17
  3. Réponses: 2
    Dernier message: 21/01/2008, 14h25
  4. trouver un élément dans un tableau
    Par jcaspar dans le forum Collection et Stream
    Réponses: 7
    Dernier message: 21/09/2007, 15h57
  5. Trouver un champ dans un tableau
    Par snaxisnake dans le forum Delphi
    Réponses: 6
    Dernier message: 30/05/2006, 17h37

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