Discussion :

[cerede2000]

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]

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]

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?

[pseudocode]

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.

Tu peux adapter les algorithmes de tris pour effectuer ce genre de recherche:

http://en.wikipedia.org/wiki/Selecti...rgest_elements

[Jedai]

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]

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]

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]

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

[Graffito]

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).

[Jedai]

Graffito, il y a des algorithmes déterministes en O(n), mais ta technique est intéressante, tu peux estimer l'espérance de réussite selon la marge que tu t'accorde ?
cederede2000, as-tu lu la page Wikipédia ? Un échantillon des techniques pertinentes y est exposé.
En gros l'idée est de commencer le tri, mais de s'arrêter dès qu'on a trié suffisamment d'éléments, avec un algorithme de tri adapté (mergesort ou quicksort/tri fusion ou tri rapide), on obtient du O(n log k) (avec les k premiers éléments triés) ou du O(n) (avec les k premiers éléments non-triés).

(ma remarque sur Haskell soulignait que dans un langage dit "à évaluation paresseuse", il n'était même pas nécessaire de recoder l'algorithme de tri pour le rendre "partiel", demander les k premiers éléments de la liste triée revenait au même, ce qui est très sympa !)
--
Jedaï

[Graffito]

des algorithmes déterministes en O(n),

Si on recherche les n/2 meilleurs sur n, j'ai du mal à imaginer un algo en O(n)

Tu peux estimer l'espérance de réussite selon la marge que tu t'accorde ?

Oulà, il me faudrait remonter le temps quand j'avais encore quelques connaissances en statistiques. Mais, il me semble qu'en se basant sur une loi classique de répartition (style poisson), on devrait pouvior évaluer les probabilités de réussite.

[Jedai]

Si on recherche les n/2 meilleurs sur n, j'ai du mal à imaginer un algo en O(n)

Pourquoi ? Il y a un algo en O(n) pour trouver la médiane, donc il y a bien un algo en O(n) pour récupérer les n/2 premiers nombres (pas triés bien sûr).

--
Jedaï

[Graffito]

Il y a un algo en O(n) pour trouver la médiane

Je ne connaissais pas ....

[cerede2000]

cederede2000, as-tu lu la page Wikipédia ? Un échantillon des techniques pertinentes y est exposé.

Eu j'ai lut mon possible mais je doit dire que mon anglais est pas assez performant pour comprendre tout ça

[cerede2000]

Pouvez vous m'aider encore un peu? SVP

[coyotte507]

Voilà par exemple un algo qui te permet de trouver le k-ième plus grand -ou plus petit - élément d'un tableau.

On considère un tableau de taille n (le premier élément est à 1, le dernier à n).
Tu prends le premier éléments, et si tu trouves k éléments plus grands, alors tu continues la recherche sur le tableau A[2]..A[n].

Par contre, si tu trouves moins de (k-1) élements plus grands, alors pareil, tu le laisses à sa place, et tu continues la recherche sur le tableau A[2]..A[n]. Sauf que là, vu qu'il est plus grand que l'élément que tu recherches, tu remplaces k par k-1.

Enfin, si il y a exactement k-1 éléments plus grands, alors tu stoppes la recherche .

Je vais poster un code en C pour te montrer le principe, si tu veux.


Une fois que tu as le k-ième élément le plus grand, c'est simple pour faire un algorithme en O(n) pour trouver les k éléments les plus grands.

___________________________________________________________

Autre solution:
Tu fais une liste chainée, avec comme élément de départ le premier élément du tableau. Ensuite, pour chaque élément jusqu'au k-ième élément du tableau, si l'élément est plus gros que le dernier élément, tu l'ajoutes à la fin, et si il est moins gros que le premier élément du tableau, tu le mets au début.

Donc maintenant, que tu as k-éléments dans ta liste chainée, c'est simple: pour chaque élément restant du tableau, si il est plus gros que le premier élément de la liste chainée, tu vires le premier élément de la liste et parcoures la liste chainée pour savoir ou le mettre, sinon tu fais rien.

A la fin, tu as les k plus gros éléments dans ta liste chainée.

Et ca a une complexité de O(kn)

[Jedai]

Le mieux c'est que ca donne aussi un algo en O(n) pour trier tout un tableau .

Tu es au courant du fait que pour tout algorithme de tri procédant par comparaison on ne peut pas faire mieux que O(n log n) dans le pire des cas ? Autrement dit ton algo a un problème...

Ensuite, pour chaque élément jusqu'au k-ième élément du tableau, si l'élément est plus gros que le dernier élément, tu l'ajoutes à la fin, et si il est moins gros que le premier élément du tableau, tu le mets au début.

Donc maintenant, que tu as k-éléments dans ta liste chainée, c'est simple: pour chaque élément restant du tableau, si il est plus gros que le dernier élément de la liste chainée, tu vires le premier élément de la liste et tu l'ajoutes à la fin, sinon tu fais rien.

En l'état ton algorithme ne marche pas, parce que tu ne tiens pas compte de la possibilité que l'élément du tableau soit entre les extrémités de ta liste chaînée.
Ton idée n'est pas mauvaise, corrigée, elle reviendrait à faire un tri par sélection partiel et aurait une complexité de O(kn), mais on peut faire mieux en O(n log k). Ton algorithme (même avec la correction) garde l'avantage de la simplicité par rapport à un quicksort partiel.

--
Jedaï

[cerede2000]

Le code en C m'intéresse en tout cas

[coyotte507]

Tu n'as plus qu'à modifier les trois paramètres k, tab, et longueur_tab:

Code C :

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
 
typedef int element;
 
typedef struct _liste {
	struct _liste *avant;
	struct _liste *apres;
	element contenu;
} liste;
 
//pour créer un maillon de la liste chainée.
liste *creer_liste(element el, liste *avant, liste *apres)
{
	liste *ret = malloc(sizeof(liste));
	ret->avant = avant;
	ret->apres = apres;
	ret->contenu = el;
 
	if (apres != NULL) ret->apres->avant = ret;
	if (avant != NULL) ret->avant->apres = ret;
 
	return ret;
}
 
//pour insérer au bon endroit de la liste un élément
liste *inserer(liste *li, element el)
{
	liste *depart = li;
 
	//si c'est le + petit élément
	if (depart->contenu > el)
	{
		return creer_liste(el, NULL, depart);
	}
	//on l'insère où il faut
	while(li->apres != NULL && li->apres->contenu < el)
	{
		li = li->apres;
	}
	creer_liste(el, li, li->apres);
	return depart;
}
 
//pour effacer le premier élément seulement
//et seulement si il y a d'autres éléments après
liste *effacer(liste *li)
{
	liste *ret = li->apres;
 
	ret->avant = NULL;
	free(ret->avant);
 
	return ret;
}
 
//le main
int main()
{
	int i;
	int k = 3;
	int tab[] = {5,4,2,9,18,6,7,3,1,0};
	int *ptr = tab;
	int longueur_tab = 10;
	liste *dep = creer_liste(tab[0], NULL, NULL);
 
	//on crée la liste chainée de k éléments
	for (i=1; i < k; i++)
	{
		dep = inserer(dep, *ptr);
		++ptr;
	}
 
	//et on là on insère les éléments dans la liste chainée ou pas,
	//la liste gardant toujours la même taille
	for (i=k; i <= longueur_tab; i++)
	{
		if (*ptr > dep->contenu)
		{
			dep = effacer(dep);
			dep = inserer(dep, *ptr);
		}
		++ptr;
	}
 
	//et on affiche le résultat
 
	for (dep = dep; dep != NULL; dep = dep->apres)
	{
		printf("%d ", dep->contenu);
	}
	printf("\n");
 
	return 0;
}

[coyotte507]

Sinon, si j'ai bien compris, si on veut avoir du O(n lg k), alors il faut pouvoir trouver l'endoit où l'on doit insérer l'élément en lg k, et donc utiliser une autre structure que la liste chainée comme un arbre rouge-noir...