Sélection et tri partiel

a marqué ce sujet comme résolu.

Bonjour tout le monde,

J’ai commencé à écrire un petit article sur un sujet que j’avais en tête depuis quelques temps. Il s’agit du quickselect et de son analyse de complexité.

Vous pouvez trouver le contenu juste ici

Je dois encore repasser plusieurs fois sur le texte et j’hésite à aborder des notions sur l’emploi de structures de données à cet effet ou l’existence de streaming algorithms. Mais les éléments principaux devraient déjà être présents.

Merci d’avance pour vos retours !

+2 -0

Bonjour,

Je n’ai lu que le paragraphe La statistique d’ordre, mes remarques sont données dans le sens de la lectures, et comme je ne maitrise pas du tout ce sujet ces remarquent ce concentrent sur la forme.

Orthographe:

Cependant, vous employer chaque jour → employez

les données que vous avez collectées. → collecté.

Je ne comprends pas de quel temps on parle dans la phrase suivante (c’est quoi le temps d’un quantile ?):

les temps relevés suivent le plus souvent des distributions de type poisson ou bimodale et on peut s’intéresser aux temps des quantiles 99%, 99.9%

Suggestion :

Étant donné un ensemble AA de nn nombres (distincts) et un entier i compris entre 1 et nn, on cherche à déterminer l’élément xx de AA tel qu’il est plus grand que i−1 éléments de AA.

Tounure de phrase: (je ne suis pas sur du sens désiré)

Avec les cas particuliers que le minimum est tel que i = 1, le maximum correspond à i = n et la médiane à i = n/2.

⇒ Avec les cas particuliers tels que: le minimum soit à i = 1, le maximum correspond à i = n et la médiane à i = n/2

Dans le 1er code, on ne voit pas que la fonction find_min_or_max est à appeler 2 fois , j’aurais ajouté dans le même code un fonction min_max de type:

def find_min_or_max(A, inequality):
    target_value = A[0]
    for e in A[1:]: # Pour chaque élément de l'ensemble
       if inequality(e, target_value): # S'il est plus grand ou plus petit
          target_value = e # On modifie l'élément actuel
       return target_value
       
def min_max(A):
    min_a = find_min_or_max(A, min)
    max_a = find_min_or_max(A, max)
    return min_a,_max_a

Dans le 2eme code pourquoi ne pas affecter A[0] à min et max au début de la fonction ?

Phrase complexe:

En effet, la propriété employée ne tient pas, en particulier, si la liste est triée par ordre décroissant et on serait amener à effectuer 4n comparaisons au final

⇒ Par exemple, si la liste est déja triée par ordre décroissant et on serait amener à effectuer 4n comparaisons au final.

Ps:le correcteur orthographique sur mon PC n’a pas l’air de reconnaitre le francais, donc tout est souligné rouge .. j’ai surement du laisser des fautes.

+0 -0

Bonjour Kayou,

Tout d’abord merci d’avoir fait l’effort de ta relecture ! J’ai particulièrement aimé ta remarque sur le fait d’appeler "find_min_or_max" 2 fois, c’est nettement plus clair avec ce que tu proposes. J’ai également apporté les corrections que tu avais mentionnées et suggérées. Il ne me restera plus qu’à imprimer pour relire au calme afin de trouver d’autres problèmes =)

Par contre, je dois admettre ne pas avoir compris ce point:

Dans le 2eme code pourquoi ne pas affecter A[0] à min et max au début de la fonction ?

Est-ce que tu pourrais davantage l’expliciter ?

J’ai rajouté les deux parties, qui manquaient dans ma tête, relatives à l’usage d’une structure de données pour résoudre ce problème ou la vision online. Mais je ne suis pas entièrement convaincu … Les structures de données pourraient nécessiter de nombreux articles tant les choses sont nombreuses à exprimer mais la vision que j’espère proposer me semble suffisamment concise. L’algorithme online cache beaucoup trop de complexité d’apprentissage (sans doute moins que l’étude des moments du quickselect …) mais je ne perds pas d’espoir de pouvoir aborder un jour ce sujet.

+0 -0

Les données que vous avez collectées .

https://www.francaisfacile.com/exercices/exercice-francais-2/exercice-francais-2956.php

Avec l’auxiliaire 'avoir’, le participe passé s’accorde normalement avec le complément d’objet direct seulement si celui-ci est placé devant le verbe. Pour retrouver le complément d’objet direct (brièvement appelé COD), il suffit de se poser la question 'qui' ou 'quoi' après l’action.
Premier exemple : 'Le chat a mangé la souris.' > 'le chat a mangé quoi ?' réponse : 'la souris’ -> mangé ne s’accorde pas tout simplement parce que le COD est placé après le participe passé.
Deuxième exemple : 'la souris que le chat a mangée était blanche' > 'le chat a mangé quoi ?' réponse : 'la souris’ > mangée s’accorde avec le COD souris (au féminin et au singulier) placé devant le verbe dans la phrase, donc le participe passé s’accorde avec ce COD (au féminin singulier).

Application : ici, on utilise l’auxiliaire avoir. Vous avez collecté quoi ? les données.
"les données" est le COD, il est placé devant le verbe. Donc il faut accorder.

+0 -0

Bonjour Gawabounga,

j’aurais ecris le début de la fonction min_max un peu differement, ca ne change pas le resultat de la fonction, ca enleve juste un des cas non gérés.

def min_max(A):
  min = max = A[0]
  
  for i in range(2, len(A), 2):
    .....

PS: En général je n’aime pas trop l’usage de min et max en tant que variables en python, je trouve que ca crée un confusion avec les fonctions du même nom, ici par exemple on a des fonctions dans le 1er code et des variables dans le 2eme.

+0 -0
Ce sujet est verrouillé.