Filtrer les K plus grandes valeurs d'un vecteur

Filtrer les K plus grandes valeurs d'un vecteur - Algo - Programmation

Marsh Posté le 18-06-2009 à 11:03:30    

Bonjour à tous,
 
Je me permets d'ouvrir un nouveau sujet car j'ai un tout petit souci dans un programme que je dois écrire et je pense que je pourrais trouver une réponse efficace ici.
 
J'ai en entrée un vecteur de N nombre réels positifs et je voudrais écrire une routine qui met toutes ses composantes à 0 sauf les K plus grandes.  
 
J'ai pensé à faire un bubble-sort pour mettre le vecteur dans l'ordre croissant, garder les positions en mémoire, mettre à 0 les N-K premières puis faire la permutation inverse mais ça me paraît bien compliqué pour pas grand chose. N et K sont assez petits (N de l'ordre de 100 et quelques et K de l'ordre de 10) mais l'opération sera répétée plusieurs milliers de fois donc j'aimerais trouver un moyen économique de le faire.
 
Je précise que je travaille (malheureusement) en VBA pour Excel (si c'était en Matlab je crois que je saurais le faire en utilisant les fonctions natives du langage).
 
Je vous remercie d'avance pour votre aide.

Reply

Marsh Posté le 18-06-2009 à 11:03:30   

Reply

Marsh Posté le 18-06-2009 à 11:58:44    

Tu fais une première passe en gardant les K plus grandes valeurs et une deuxième en mettant à 0 celles que tu n'as pas gardé.  N'oublie pas de bien définir ce qu'il faut faire quand plusieurs valeurs sont égales (en particulier quand il y a un ex-equo pour la Kième valeur).


---------------
The truth is rarely pure and never simple (Oscar Wilde)
Reply

Marsh Posté le 18-06-2009 à 14:21:31    

Merci beaucoup pour ta réponse rapide. J'avais vaguement pensé à quelque chose comme ça, mais sans trop concrétiser. Qu'est-ce que tu penses de quelquechose comme ça (V est mon vecteur initial) :
 
- on définit un vecteur M de taille K, intialisé avec des 0
 
- pour i = 1 to N on fait :
-- si V(i) > M(1), K(1) = V(i)
-- puis un passage de tri sur K pour remettre les valeurs dans l'ordre croissant (si M(j) > M(j+1), on les échange)
- fin boucle
 
Sauf erreur mon vecteur K contient bien ce qu'il faut à la fin (avec une complexité en N*K ?) et il reste à mettre à 0 toutes les valeurs de N qui sont < M(1), ça te paraît OK ?

Reply

Marsh Posté le 18-06-2009 à 15:14:03    

Oui -- pour autant que ce soit bien ce qu'il faut faire quand il y a plusieurs V(j) qui sont égaux.


---------------
The truth is rarely pure and never simple (Oscar Wilde)
Reply

Marsh Posté le 18-06-2009 à 15:27:12    

A priori dans ma situation ça n'arrivera pas :)  
 
Mais en effet il faut tout de même se poser la question ! J'avoue que je ne vois pas très bien comment gérer ce genre de situations sans alourdir le code de façon démesurée...  
 
J'imagine qu'on peut toujours ajouter une boucle à la fin pour vérifier qu'il y a bien (au plus) K valeurs non nulles dans V, et envoyer un message d'erreur si ce n'est pas le cas ? Ce serait alors à l'utilisateur de décider ce qu'il convient de faire.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed