TRI TABLEAU D'INTEGER PAR DICHOTOMIE, MAJ
cs_petifa
Messages postés
215
Date d'inscription
dimanche 20 février 2005
Statut
Membre
Dernière intervention
10 mars 2014
-
28 sept. 2008 à 17:59
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019 - 1 mars 2009 à 12:23
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019 - 1 mars 2009 à 12:23
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/48079-tri-tableau-d-integer-par-dichotomie-maj
https://codes-sources.commentcamarche.net/source/48079-tri-tableau-d-integer-par-dichotomie-maj
1 mars 2009 à 12:23
(1) pourquoi tous ces "throws IOException" pour des méthodes qui ne font pas d'IO? C'est totalement inutile (et couteux) dans la classe TriDicho ci-dessus.
(2) voila une fonction d'arrondi très bizarre ! Non seulement elle ne fait pas un arrondi à l'entier le plus proche (en fait elle prend l'entier supérieur), mais en plus elle le fait avec un test complètement inutile et couteux, et avec deux conversion de type au passage.
Rappel:
int round(double x) { return (int)(x + 0.5); }
suffit pour un arrondi à l'entier le plus proche, ou
double round(double x) { return Math.floor(x + 0.5); }
si on veut une étendue numérique plus large au delà de +/-2^31.
(3) l'arrondi est en fait totalement inutile dans la dichotomie: il suffit de prendre la division entière par deux des intervalles, même si un des deux sous-intervalles est de longueur impaire et l'autre paire, lequel sera le plus long reste un choix arbitraire. Bref pour prendre un nombre entier moyen entre dex entiers, il suffit totalement de prendre:
milieu = (debut + fin) / 2;
avec la division entière, au lieu du couteux et inutile:
milieu = round((double)((double)debut+(double)fin)/2);
En effet, début et fin sont des index de tableaux, et ils sont nécessairement positifs ou nuls donc sur 31 bits, leur somme tient sans dépassement dans 32 bits (même si un signe négatif peut apparaître). Si on veut éviter le cas de la somme négative (qui peut apparaître seulement si les deux entiers positifs nécessitent 31 bits, donc tous deux supérieurs ou égal à 2,1 milliards), et éviter tout cas de débordement de capacité, on peut aussi écrire:
milieu = (debut>>1)+(fin>>1)+(début&fin&1);
(pour comprendre cette formule, il faut voir que x>>1 divise un entier par 2, et qu'on s'occupe donc d'ajouter les moitiés entières des deux nombres, puis d'ajouter à la fin le bit faible manquant, quand il est pertinent c'est à dire présent dans les deux nombres). Maintenant, avoir un tableau de plus de 2 milliards d'entiers à trier en mémoire est un cas exceptionnel et on peut s'interroger sur le modèle de données utilisé dans l'appli qui aurait besoin de faire ça !
Dernière note (hors sujet mais fait suite à une remarque ci-dessus): Java n'est certainement pas "lent" comme le prétendent encore bon nombre de gens qui ne l'ont pas essayé. Les tests de performance montrent qu'il peut pratiquement égaler le C++ et souvent dépasser .Net, car le code est réellement compilé et optimisé directement sur la machine cible, et pas du tout interprété. Les machines virtuelles se sont énormément améliorées (c'est aussi le cas de .Net qui rattrape son retard, ou de Python et PHP avec le moteur Zend) et cette façon de produire l'environnement d'exécution permet de dépasser les performances qu'on obtiendrait avec une précompilation générique (de type C/C++ ou même assembleur) en faveur d'une seule machine théorique. Aujourd'hui la grande variété des architectures et le fait qu'on est amené à réinstaller le même code de l'une à l'autre, milite en faveur des machines virtuelles à compilation dynamique (comme Java, .Net, Python, PHP/Zend, ...) dont les performances et la portabilité est nettement supérieure (et demande également beaucoup moins d'effort de la part du programmeuir qui n'a besoin de concevoir son programme qu'une seule fois avec une base solide). Java est aujourd'hui aussi rapide que C++, et souvent plus rapide sur des applications gourmandes en communications ou en volume de données traitées, ou en requêtes, ou en threads, ceci grace à un modèle mémoire plus évolué et plus adapté à un contexte très dynamique. C'est la raison pour laquelle Java marche tellement bien pout les applications multitiers, où il apporte aussi une grande sécurité (qui reste toujours à démontrer pour les applis en C++, les compilateurs C++ ne pouvant pas tout détecter car le langag eest trop permissif).
28 févr. 2009 à 14:00
25 févr. 2009 à 18:15
25 févr. 2009 à 17:51
En revanche pour les collections triées dont les éléments ne sont pas tous en mémoire mais sont stockées de façon externe par un accès lent (fichier, service réseau distant...), le tri complet dans un vercteur est moins intéressant que les représentation sous forme d'arbre d'index (avec un cache local d'exlporation) complété d'une méthode d'équilibrage qui ne nécessite pas trop de réorganisations (pour les mises à jour) telle que les AVL, arbres bicolores, B-arbres, et arbres B+.
Dans ce cas ce qui est très intéressant à écrire c'est la fonction d'équilibrage (total ou partiel) de l'arbre, et la façon de modifier rapidement l'arbre (par insertion ou suppression d'éléments dans la collection) sans nécessairement maintenir un équilibrage total (et là des paramètres de tuning sont intéressants tels que le niveau minimum de remplissage des feuilles et noeuds dans un B-arbre), ainsi que les méthodes de parcours séquentiel de l'arbre (pour l'explorer dans l'ordre de tri).
De toute façon, dans chaque problème où intervient un tri, il faut se demander s'il est pertinent. Le tri est et a toujours été coûteux, on le relègue donc le plus souvent à la fin dans la présentation des résultats d'un problème: pratiquement toujours ce n'est pas le tri qui est nécessaire, mais simplement un test d'unicité (ou d'existence) dans une collection, et là le hachage fait des miracles, à condition que la fonction de hachage soit uniformément distribuée, ce que bien des programmes Java oublient de traduire dans la fonction de hachage de leurs objets, souvent simplement basée sur une simple évaluation de polynome ! Même pour hacher des entiers, un polynome est très insuffisant pour assurer cette uniformité de distribution (alors que l'inversion du poids des bits est une opération "simple" mais efficace pour avoir une assez bonne distribution du hachage dans nombre de problèmes relatifs à la recherche d'unicité).
Le hachage a cependant le défaut de ses avantages: il ne garantie aucun ordre pertient dans les éléments récupérés de la collection (mais le plus souvent on s'en fout royalement pour l'immense majorité des problèmes où on n'a à gérer que des ensembles d'éléments et non des collections triées).
Ainsi, trop de programmes font des requêtes SQL contenant un tri couteux (ORDER BY) alors qu'un groupement d'unicité suffit et est bien plus performant et suffisant pour le problème donné (GROUP BY). La même question se pose pour les index (dont il n'est souvent pas nécessaire qu'ils maintiennent triées les données d'une table à la quelle on accède uniquement par un identifiant ou une valeur unique, et non par une recherche par plage de valeurs), et sur la pertinence des recherches par plage (ce qui peut traduire un défaut de conception du modèle de données si ce type de recherche est trop systématique, car il est évident qu'il manque alors un attribut de type "classe énumérée")
Bref, faites du tri, mais avec modération !
20 janv. 2009 à 11:16
30 sept. 2008 à 09:27
Le cours abordant la dichotomie est arrivé après une semaine de cours consacrée aux algos de triage. C'est pour cette raison je pense qu'il nous a été demandé d'utiliser la dichotomie pour effectuer un tri.
Dès que j'ai le temps je posterai un algo de nombres-en-lettres pour me faire pardonner :)
29 sept. 2008 à 18:47
D'accord pour dire que la recherche dichotomique dans une table triée est efficace. Elle prend un temps Log(N) pour N éléments.
Par contre le tri par recherche dichotomique et insertion est très inefficace à cause de la phase d'insertion, qui prend un temps N^2.
A proscrire !!! Les tris efficaces sont en N.Log(N).
29 sept. 2008 à 12:01
Arrays.sort(tnb);
28 sept. 2008 à 17:59
Par contre trop de commentaires tue les commentaires...
bizarre la fonction rechercheposition est commentée mais pas le reste...