Recupere x valeurs dans un tableau

**cerede2000** · 30/11/2007, 18h50

Bonsoir,

Voila le problème va peut être vous paraître simple mais je ne trouve pas vraiment de solution

Alors voila, j'ai un tableau de N lignes qui contient par exemple des dates, et je souhaite récupérer dans ce tableau les X plus vielle dates.
Mais je ne veut pas trier le tableau, je veut simplement et le plus rapidement possible récupérer les X dates les plus anciennes.

Merci a vous

**souviron34** · 30/11/2007, 19h20

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
Nmins = X
Pour i = 0 a i < X
  min[i] = max date
 
 
pour i = 0 a i = (N-1)
 
 
   Pour j = 0 a j = (Nmins - 1)
 
       Si date[i] < min[j]
           Si j different de (Nmins - 1)
               pour k = (Nmins - 2) a k = j
                  min[k+1] = min[k] 
           Fin si
 
           min[j] = date[i]
           sort de boucle j
       Fin si
 
   Fin boucle j
 
Fin boucle i

**cerede2000** · 01/12/2007, 09h00

Pourrais tu un peut commenter s'il te plaît

Mais une triple boucle c'est un peut lourd :S
Sion on commence a avoir 100 000 dates et que l'on veut les 10 000 plus anciennes...
Rien de plus efficace n'est possible?

**Jedai** · 01/12/2007, 13h56

Tu as des techniques plus efficaces, Wikipedia a un bon exposé là-dessus.

NB : En Haskell, certaines techniques de tri te donne la meilleure complexité pour réaliser cela grâce à l'évaluation paresseuse, il suffit d'écrire :

Code :

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

kMins k xs = take k (sort xs)

Et tu as ta réponse sans gâcher de temps !! Pas mal non ?

--
Jedaï

**Graffito** · 01/12/2007, 14h14

Pour un petit nombre M de valeur Max sur un grand nombre de lignes N et si l'on suppose une répartition aléatoire, on peut parier sur la loi des grands nombres.

On regarde un échantilon (exemple : 0.1% de N) que l'on trie.
On déduit de cet échantillon des seuils probables pour 2*M valeurs, 4*M, 8*M, ... valeurs.
On fait une passe et on retient toutes les X valeurs au-dessus du premier seuil et on les trie.
Si X < M on garde les M premières.
Sinon, on refait une passe pour chercher les valeurs entre les seuils établis pour 2*M et 4*M, on trie les Y valeurs trouvées et on les ajoute aux X précédentes.
On fait une 3ème passe ou plus si nécessaire.

Si l'échantillonage est bon (distribution aléatoire), une passe devrait suffire.

**souviron34** · 01/12/2007, 14h37

Envoyé par cerede2000

Pourrais tu un peut commenter s'il te plaît

Mais une triple boucle c'est un peut lourd :S
Sion on commence a avoir 100 000 dates et que l'on veut les 10 000 plus anciennes...
Rien de plus efficace n'est possible?

Si...

Tu fais un tri style qsort :

Si tu ne veux pas trier le tableau, tu triereas les adresses des éléments du tableau)

Et tu prends les X premiers..

**cerede2000** · 01/12/2007, 15h01

Eu tout ce que vous me racontez n'est pas très claire pour moi la

**Graffito** · 01/12/2007, 16h13

Sur un exemple:
Chercher les 1000 meilleures notes sur les 200 000 résultats du bac.
Une note a donc une chance sur 200 d'être dans les 1000 meilleures ("top 0.5%").

On prend 5000 résultats au hasard (échantillon représentatif) que l'on trie et on prend comme seuils n°1 la 50ème note de l'échantilon (top 1%), comme seuil n°2 la 100ème (top2%) , etc ...
Comme les notes situées au-dessus du seuil 1 représentent 1% de l'échantillon, il y a toutes les chances qu'en sélectionnant toutes les notes au-dessus de ce seuil dans l'ensemble des résultats on obtienne un ensemble dont l'ordre de grandeur se situera autour de 2000 notes (500 ou 5000 si l'échantillon était mauvais). Ensuite, un petit tri sur ce sous-ensemble pour classer les notes obtenues.

Si on obtenu que 500 notes alors qu'il nous en faut mille, on réitère la recherche des notes comprises entre le seuil N°1 et le seuil N°2 pour obtenir les 500 meilleures notes manquantes.

On peut aussi, pour éviter de faire plusieurs parcours, classer les 200 000 notes dans 100 paquets (seuils N°1 à seuil N°100 de l'échantillon).
Ainsi, il n'y aura en tout état de cause qu'un seul paquet à trier (en dehors de l'échantillon).