Quelqu'un pour infirmer/confirmer/completer/me faire interner?
Je suis contre la tres grosse constante.
Si on prend deux hypothese assez courantes :
1) je connais l'intervalle de mes valeurs qui sont des entiers (par exemple 0 <valeur <k) et leur nombre et fixee (j'ai n valeurs a trier)
2) Je m'en fout de la quantite de memoire que je grille je veux de la vitesse.
voici le tri le plus rapide du monde :
initialiser a 0 tableau[k] //je cree un tableau pour le tri
valeur[n] // la structure qui contient mes valeurs
pour i entre 0 et n exclu faire
incrementer tableau[valeur[i]]
fin pour
Amusant non ? et hop une structure qui contient dans chaque case le nombre d'elements egaux a la place de la case. cout : O(n).
Ensuite pour sortir les zeros du tableau (si le besoin s'en fait sentir )c'est O(k), mais c'est rarement obligatoire. En fait ca n'est utile que si k est tres superieur a n(ce qui est souvent tres rare).
Maintenant si ce n'est pas des entiers (c'est la que ca bouffe de la memoire) ben on va les transformer en entiers en les multipliant par ce qui va bien (preicision a six chiffres = *1000 0000). Vous avez bien entendu le droit de hurler a l'anonce de cette ennormite, neamoins il y a pas mal de cas ou ca marche. Bien sur il risque d'y avoir plus de chances que k soit superieur a n, donc le traitement pour purger les 0 du tableau peut sembler long.
[^] # Re: Soft de peer to perr
Posté par Jerome Herman . En réponse au journal Soft de peer to perr. Évalué à 1.
Je suis contre la tres grosse constante.
Si on prend deux hypothese assez courantes :
1) je connais l'intervalle de mes valeurs qui sont des entiers (par exemple 0 <valeur <k) et leur nombre et fixee (j'ai n valeurs a trier)
2) Je m'en fout de la quantite de memoire que je grille je veux de la vitesse.
voici le tri le plus rapide du monde :
initialiser a 0 tableau[k] //je cree un tableau pour le tri
valeur[n] // la structure qui contient mes valeurs
pour i entre 0 et n exclu faire
incrementer tableau[valeur[i]]
fin pour
Amusant non ? et hop une structure qui contient dans chaque case le nombre d'elements egaux a la place de la case. cout : O(n).
Ensuite pour sortir les zeros du tableau (si le besoin s'en fait sentir )c'est O(k), mais c'est rarement obligatoire. En fait ca n'est utile que si k est tres superieur a n(ce qui est souvent tres rare).
Maintenant si ce n'est pas des entiers (c'est la que ca bouffe de la memoire) ben on va les transformer en entiers en les multipliant par ce qui va bien (preicision a six chiffres = *1000 0000). Vous avez bien entendu le droit de hurler a l'anonce de cette ennormite, neamoins il y a pas mal de cas ou ca marche. Bien sur il risque d'y avoir plus de chances que k soit superieur a n, donc le traitement pour purger les 0 du tableau peut sembler long.
Kha