Tri tableau d'integer par dichotomie, maj

Soyez le premier à donner votre avis sur cette source.

Vue 11 285 fois - Téléchargée 431 fois

Description

Cette source corrige un problème lié au zéro, et prend acte des critiques reçues par la première version.

Source / Exemple :


/*

  • PROJET : TriDicho AUTEUR : Alexandre Alcuyet DATE : 27/09/2008
  • Trier un tableau par dichotomie.
  • Le tri par dichotomie est un tri très efficace qui consiste
  • à éliminer successivement la motié des possibilités restantes,
  • jusqu'à parvenir au résultat.
  • Ce code n'a qu'un intérêt pédagogique, au titre d'algorithme car
  • l'API contient déjà de nombreuses solutions pour trier. Il
  • n'est pas question ici de trier des Collections mais des entiers,
  • mais libre à vous d'adapter le code.
  • /
import java.io.IOException; import java.lang.Integer; public class Main { public static void main(String args[]) throws IOException { Integer[] tnb = { Integer.valueOf(0), Integer.valueOf(54), Integer.valueOf(2), Integer.valueOf(321326), Integer.valueOf(1255), Integer.valueOf(10128), Integer.valueOf(65), Integer.valueOf(4), Integer.valueOf(101254), Integer.valueOf(4), Integer.valueOf(10), Integer.valueOf(5), Integer.valueOf(3), Integer.valueOf(1), Integer.valueOf(8) }; affichetableau(tnb); tnb = TriDicho.trier(tnb); affichetableau(tnb); System.exit(0); } public static void affichetableau(Object tab[]) throws IOException { for ( int i=0; i<tab.length-1; i++) System.out.format("%s - ", tab[i].toString()); System.out.format("%s%n",tab[tab.length-1].toString()); } } class TriDicho { public static Integer[] trier(Integer tab1[]) throws IOException { int debut = 0; int fin = 0; int pos = 0; Integer[] tab2 = new Integer[tab1.length]; for ( int i=0; i<tab2.length; i++) { pos = rechercheposition(tab1[i].intValue(), tab2, debut, fin); fin = i; insertion(tab1[i].intValue(), tab2, pos); }; return tab2; } private static void insertion( int val, Integer tab[], int pos) throws IOException { int zr; for ( int i=tab.length-2; i>pos-1 ; i-- ) { zr = (tab[i] == null) ? 0 : tab[i].intValue() ; if ( pos != i ) tab[i] = tab[i-1] ; else tab[i] = val ; tab[i+1] = zr; }; } private static int round(double nb) throws IOException { int monint = (int)nb; double mondouble = (double)monint; if ( mondouble != nb) return (int)nb+1 ; return (int)nb; } private static int rechercheposition(int val, Integer tab[], int debut, int fin) throws IOException { int milieu; do { milieu = round((double)((double)debut+(double)fin)/2); /*
  • si la valeur du tableau est null et que la fin (nombre
  • le plus grand connu) est 0 retourne 0.
  • Dans le cas du premier nombre inscrit au tableau
  • /
//System.out.println("valeur: "+tab[0].intValue()); if ( (tab[milieu] == null) && (fin==0) ) return 0 ; /*
  • si la valeur est superieure et qu'il n'y a plus
  • d'écart entre fin et debut retourne fin+1
  • /
if ( (tab[milieu].intValue() <= val) && (debut == fin) ) return fin+1 ; /*
  • si la valeur est inferieure et qu'il n'y a plus d'ecart
  • entre fin et debut retourne fin+1
  • /
if ( (tab[milieu].intValue() > val) && (debut == fin) ) return fin ; /*
  • quand la valeur du tableau coordonee milieu est
  • superieure a la valeur a entrer
  • /
if ( tab[milieu].intValue() > val ) { /*
  • si il ne reste que deux cases,
  • alors la deuxieme est inutile
  • /
if (fin-debut == 1) fin = fin-1 ; // sinon fin est initialise avec milieu else fin = milieu; } /*
  • si la valeur du tableau a la coordonee de milieu
  • est inferieure ou egale a la valeur a entrer,
  • alors on oublie tout ce qui se trouve avant
  • /
if ( tab[milieu].intValue() <= val ) debut = milieu ; } while ( milieu != -1 ); return 0; } }

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

Puisqu'on parle de qualité de code et réutilisation, il serait important de notyer certains défauts dans le code ci-dessus:

(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).
Messages postés
15
Date d'inscription
mardi 3 mars 2009
Statut
Membre
Dernière intervention
26 juin 2009

Merci beaucoup pour ces informations!
Messages postés
13
Date d'inscription
dimanche 29 février 2004
Statut
Membre
Dernière intervention
20 novembre 2015

ton commentaire est vraiment très intéressant verdy. on vois que tu t'es penché sur le sujet. ces mécanismes sont d'un niveau relativement bas, le développeur n'en a pas trop à s'en soucier en général. à part servir de cas d'école (cours d'algorithme, etc) ce genre de programme n'est pas très utilisé dans la vie professionnelle, on se concentre plus sur la partie métier. java à le grand avantage d'être réutilisable alors réutilisez ce qui existe déjà, d'autant plus qu'il est difficile de faire mieux en termes de performances (java ayant été longtemps critiqué sur ce point des efforts on été fait). par contre il est nécessaire de bien comprendre les fonctionnements de ces fonctions pour choisir celle qui est le mieux adaptée à chaque cas de figure.
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

Effectivement la fonction du JRE Arrays.sort(tnb); est lpus efficace et est déjà très optimisée, elle n'a que très peu de cas défavorables. Pour l'insertion dans une collection triée, les méthodes natives du JRE sont également très efficaces et optimisées et savent aussi utiliser la dichotomie là où elle est pertinente (si la collection est représentée par un vecteur) ou une recherche récursive de type divide-and-conquer (pour la représentation de la collection triée en arbre, qu'il soit binaire ou plus, et semi-équilibré en AVL, ou totalement équilibré en B-arbre).
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 !
Messages postés
15
Date d'inscription
mardi 3 mars 2009
Statut
Membre
Dernière intervention
26 juin 2009

Merci beaucoup!
Afficher les 9 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.