Discussion :

[maryooman]

Bonjour,

J'ai besoin de prendre d'un tableau les éléments qui possèdent n occurrences ou plus.


Exemple :

tab = 1,2,1,3,4,4
nbOcc = 2
Résultat = 1,4

tab = 1,2,3,1,2,5,1,6
nbOcc = 1
Résultat = 1,2,3,5,6

tab = 1,2,2,1,2,2,2
nbOcc = 3
Résultat = 2


J'ai fais un petit script en PHP pour exemple

2)Il fonctionne bien pour une occurence cherché car c'est un cas traité à part, grâce à 'array_unique()' de PHP.

2)Il fonctionne bien quand on demande 2 ou plus occurrences, cependant, dans le tableau résultat les chiffres copiés sont juste mais parfois en plusieurs.

3)Ce script va traiter plusieurs milliers de résultats, une optimisation ne serai pas de refus

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
 
$nbNum = 1; //le nombre d'occurrences que je cherche
 
$ids=array(5,6,4,5,6); //un tableau avec quelques chiffes
 
$nbIds = count($ids); //le nombre de d'éléments dans le tableau
 
echo "nbIds : " . $nbIds . "<br/>"; //un affichage dans le navigateur
 
$newIds = array(); //tableau de résultat
 
if ($nbNum==1){ //si on veux juste une occurrences de chaque, PHP le gère grâce à 'array_unique'
    $newIds = array_unique($ids);
} else {
    for($i=0; $i<$nbIds-1; $i++)
    {
        $nb=1; //le nombre d'occurrences d'un nombre, 1 la 1ere fois
        for($j=$i+1; $j<$nbIds; $j++)
        {
            if ($ids[$i]==$ids[$j]) //comparaison avec l'élément suivant
                $nb++; //ils sont égaux alors il y a une occurrence en plus
            if ($nb==$nbNum){ //si on atteint le nombre d'occurrences cherché
                $newIds[] = $ids[$i]; //on copie le nombre dans un nouveau tableau
                break; //et on sort du de la boucle for
            }
        }
    }
}print_r($newIds); //pour voir le contenu du tableau

Exemple


$ids=array(5,6,4,5,6);
$nbNum = 2;
Resultat :
nbIds : 5
Array ( [0] => 5 [1] => 6 )
C'est juste


$ids=array(5,6,4,5,6,5,7);
$nbNum = 2;
Resultat :
nbIds : 7
Array ( [0] => 5 [1] => 6 [2] => 5 )
C'est juste cependant le 5 est présent 2 fois dans le résultat
Ce problème est réglé avec $newIds = array_unique($newIds) Mis tout à la fin avant l’affichage du tableau.
Mais je trouve que c’est lourd au vue du nombre d’actions que je fais et de la taille du tableau qui pourra avoir plusieurs milliers d’éléments




Je souhaiterai avoir votre avis par rapport à l’algorithme et si une optimisation est faisable.
Merci.

[pseudocode]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
for($i=0; $i<$nbIds-1; $i++)
    {
        for($j=$i+1; $j<$nbIds; $j++)
...

Sacré complexité en nombre d'opération.

Ca ne serait pas plus simple de construire l'histogramme des occurrences (dans un tableau associatif), puis de parcourir cet histogramme pour extraire les entrées qui ont l'occurrence voulue ?

[maryooman]

Bonne idée.

Si j'ai bien compris : je construis un tableau avec pour chaque valeur, le nombre d'occurrences.

exemple :

tab = (1,1,2,1,3)
histTab = (1=>3, 2=>1, 3=>1)


Mais je me pose une question,
dans le tableau de départ, je risque d'avoir des milliers de nombres différents

exemple :

tab = (1,2,957,77899,3256,3256,1,456)

1) histTab1 = (1=>2, 2=>1, 3=>0, 4=>0, ..., 455=>0,456=>1, ..., 957=>1, ..., 3256=>2, ..., 77899=>1)

2) histTab2 = (1=>1, 2=>1, 957=>1, 77899=>1, 32556=>2, 456=>1)


Dans le cas du 1) J'aurais un tableau pouvant avoir plusieurs dizaines, voir centaines de milliers de cases.
Par contre pour augmenter une occurrence c'est très simple : histTab1[$i]++

Pour le 2), j'aurais un tableau plus petit, mais dans ce cas je dois le parcourir à chaque fois pour trouver un nombre et rajouter une occurrence, ça ce rapproche de 2 boucles imbriqué.

Après il faut extraire les nombres qui correspondent au nombre d'occurrence voulu, dans tout les cas il faut parcourir 1 fois le tableau histTab
Dans le cas 1), le parcoure peut être extrement long.
Dans le cas 2) c'est nettement plus rapide.


Selon vous quel est la bonne solution ?
EDIT : ou bien il existe un algo puissant pour ce genre de problème (comme le tri fusion ou tri rapide)

[pseudocode]

Dans le cas du 1) J'aurais un tableau pouvant avoir plusieurs dizaines, voir centaines de milliers de cases.
Par contre pour augmenter une occurrence c'est très simple : histTab1[$i]++

Pour le 2), j'aurais un tableau plus petit, mais dans ce cas je dois le parcourir à chaque fois pour trouver un nombre et rajouter une occurrence, ça ce rapproche de 2 boucles imbriqué.

Je crois que en PHP tous les tableaux sont associatifs.

D'après la doc.

Code PHP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
<?php
// This array is the same as ...
array(5 => 43, 32, 56, "b" => 12);
 
// ...this array
array(5 => 43, 6 => 32, 7 => 56, "b" => 12);
?>

Donc en fait c'est un mélange du cas (1) et du cas (2). Tu peux accéder directement à une case du tableau par "histTab1[$i]", et seules les cases que tu as explicitement utilisées sont stockées en mémoire.

[maryooman]

C’est vrai, ils sont associatifs

J’ai eu l'idée de faire ç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
 
    $nbNum = 2;
    $ids = array(1,2,1,5,9,5);
    $nbIds = count($ids);
    $newIds = array();
    if ($nbNum ==1){ 
        $newIds = array_unique($ids);
    } else {
        foreach($ids as $key =>$value)
        {
            $newIds[$value] ++;
        }
        $tab = array();
        foreach($newIds as $key => $value)        --------->le changement est ici
        {
            if ($value==$nbNum ) $tab[$key] = $value;
        }                                                       ----------
      }
    Zend_Debug::dump($tab);

voici l'affichage produit :

Notice: Undefined offset: 1 in C:\wamp\www\test\application\views\scripts\index\index.phtml on line 17

Notice: Undefined offset: 2 in C:\wamp\www\test\application\views\scripts\index\index.phtml on line 17

Notice: Undefined offset: 5 in C:\wamp\www\test\application\views\scripts\index\index.phtml on line 17

Notice: Undefined offset: 9 in C:\wamp\www\test\application\views\scripts\index\index.phtml on line 17
array(2) {
[1] => int(2)
[5] => int(2)
}

On constate que le tableau est bien créé avec de bonnes valeurs
Mais il y a des erreurs, de ce fait ce code est inexploitable.

Je pense que l'erreur vient du fait que le tableau est au départ de taille 0, et que malgré tout, PHP arrive à le construire.
Alors je ne peux pas créer un tableau de taille fixe, ne connaissance pas le nombre max, et puis il risque d'être très grand!

Niveau algo, je ne vois pas comment faire mieux.

Voilà !

[pseudocode]

Je ne m'y connait pas trop en PHP, mais cette partie

Code PHP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
foreach($ids as $key =>$value)
{
    $newIds[$value] ++;
}

fait l'incrémentation... d'une valeur qui n'existe peut-être pas !

Il faudrait rajouter un truc du genre (je ne sais pas si ca s'ecrit comme ca) :

Code PHP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
foreach($ids as $key =>$value)
{
    if(!isset( $newIds[ $value ] )) {
        $newIds[$value] = 1;
    } else {
        $newIds[$value] ++;
    }
}

[maryooman]

C'est exactement ça
J'ai même pas changé une lettre!

Merci beaucoup pour ton aide