IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Trier de trés grosses tables


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre expérimenté Avatar de funckfot
    Profil pro
    Étudiant
    Inscrit en
    Mars 2006
    Messages
    221
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2006
    Messages : 221
    Par défaut Trier de trés grosses tables
    Bonjours,
    c 'est le genre de chose que vous avez tres souvent mais je veut connaitre l'algorithme le plus rapide pour un tri

    j'ai des tables qui peuvent aller de 100 enregistrements jusqu'a 500 000 facile

    et pas moyen de les metre en ordre (avec order by) car la configuration AS400 me donne en premier les minuscules, les majuscules et enfin les chiffres ( je crois que c'est le code EBCDIC (ou par la)) or mon traitement ce fait sur une plateforme JAVA 1.3

    je récupere un object et je doi les comparer avec des String ou chaine de carractère


    le trie par bulle est trés lent pour ce genre de tables, mais est que le tri rapide est-il vraiment rapide?

    je ne peut pas télécharger le logiciel qui fait la comparaison mais apparament le tris rapide est meilleur.

    et le tri fusion qu'es que c'est?

  2. #2
    Membre éclairé Avatar de Ekinoks
    Profil pro
    Étudiant
    Inscrit en
    Novembre 2003
    Messages
    687
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2003
    Messages : 687
    Par défaut
    Effectivement le tri par bulle est très long ^^ il a une complexité d'ordre N^2 (N étant le nombre d'argument)

    Le tri rapide et le tri fusion on une complexité d'ordre N*log2(N).

    Le tri fusion consiste à fusionner récursivement des tableaux trier.
    On fusion 1 nombre avec un autre nombre, puis 2 avec 2 puis 4 avec 4 etc...

    Mais bien que la complexité de ces deux tri soit identique, le tri rapide est plus efficace et demande moins de mémoire RAM que le tri fusion.


    Ceci dit il y a peu étre un moyen pour que ton (order by) ne prenne pas en compte les majuscules...

  3. #3
    Membre confirmé Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Par défaut
    Le tri rapide comme son nom l'indique est rapide
    Au pire c'est n² et en moyenne n*log(n)
    mais ces liens parleront mieux que moi

    http://fr.wikipedia.org/wiki/Tri_rapide

    http://fr.wikipedia.org/wiki/Tri_fusion

    voilà

    Le réflexe google et wiki n'est pas trop mal en général !

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par funckfot
    et pas moyen de les metre en ordre (avec order by) car la configuration AS400 me donne en premier les minuscules, les majuscules et enfin les chiffres
    ORDER BY UPPER( some_name ) ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Expert confirmé
    Avatar de shawn12
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Avril 2006
    Messages
    3 368
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2006
    Messages : 3 368
    Par défaut
    Citation Envoyé par pseudocode
    ORDER BY UPPER( some_name ) ?
    Oui mais les chiffres restent positionnés à la fin non ?

  6. #6
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    qsort ??

    ou sort (shell) sous *n*x

  7. #7
    Membre expérimenté Avatar de funckfot
    Profil pro
    Étudiant
    Inscrit en
    Mars 2006
    Messages
    221
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2006
    Messages : 221
    Par défaut
    Citation Envoyé par souviron34
    qsort ??

    ou sort (shell) sous *n*x
    Rien compris !!!

  8. #8
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    je disais qsort c'est le nom de la fonction C qui fait du quick sort (http://en.wikipedia.org/wiki/Quicksort) basé sur la méthode "divide and conquer".

    Et si tu es sous un système unixoide, la commande shell sort parmet de faire ça sans le programmer...

    [EDIT]

    Je viens de regarder.. Je suis pas habitué aux traductions des noms informatiques (d'algo en particulier) .. C'est ce qu'on t'a signalé sous le nom "tri rapide"..

    [/EDIT]

  9. #9
    Membre expérimenté Avatar de funckfot
    Profil pro
    Étudiant
    Inscrit en
    Mars 2006
    Messages
    221
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2006
    Messages : 221
    Par défaut
    Citation Envoyé par shawn12
    Oui mais les chiffres restent positionnés à la fin non ?
    en effet cella me le positionne les majuscule au bon endroit

    mais les chiffres c'est tj parreille

  10. #10
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 967
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 967
    Par défaut
    Zao,
    Citation Envoyé par funckfot
    mais les chiffres c'est tj parreille
    Ben oui, au moins pour ça, tu dépends du système d'encodage, à moins d'écrire ta propre fonction de comparaison.

    Pour le tri, il vaut probablement mieux utiliser le tri par tas (heapsort), qui en moyenne est meilleur que le tri rapide (quick sort) : en n*log(n) dans le pire des cas, alors que le tri rapide va de n*log(n) à n*n dans le pire des cas

  11. #11
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation Envoyé par droggo
    Pour le tri, il vaut probablement mieux utiliser le tri par tas (heapsort), qui en moyenne est meilleur que le tri rapide (quick sort) : en n*log(n) dans le pire des cas, alors que le tri rapide va de n*log(n) à n*n dans le pire des cas
    Le tri rapide est en moyenne plus rapide que le heap sort. La constante est plus petite et les entrees sur lesquelles il degenere sont rares quand il est bien code (quand il est mal code, il peut degenerer sur des donnees presque triees ce qui dans certaines applications arrive souvent). heap sort n'est en fait utile que si la garantie de n log n est utile -- et dans ce cas, il vaut peut-etre mieux un adaptatif qui passe de quick sort a heap sort quand il detecte un probleme.

  12. #12
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par funckfot
    en effet cella me le positionne les majuscule au bon endroit

    mais les chiffres c'est tj parreille
    ET tu les veux où les chiffres ? avant ?

    ORDER BY LOCATE( LEFT(some_name,1) , "9876543210") DESC, UPPER(some_name) ASC
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Membre expérimenté Avatar de funckfot
    Profil pro
    Étudiant
    Inscrit en
    Mars 2006
    Messages
    221
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2006
    Messages : 221
    Par défaut
    Citation Envoyé par pseudocode
    ET tu les veux où les chiffres ? avant ?

    ORDER BY LOCATE( LEFT(some_name,1) , "9876543210") DESC, UPPER(some_name) ASC
    SUPER sa marche mais que directement sur la machine AS400 en JAVA il accepte rien meme pas le UPPER je suis en JAVA 1.3 pour ceux qui connaisse et donc j'utilise un JDBC mais je sais pas lequelle

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. purge très grosse table (+1téra)
    Par serge0934 dans le forum MS SQL Server
    Réponses: 12
    Dernier message: 23/09/2011, 10h33
  2. Gestion (très) grosse table !
    Par shadowbob dans le forum Optimisations
    Réponses: 18
    Dernier message: 11/12/2009, 11h43
  3. Performances sur très grosse table
    Par CinePhil dans le forum Optimisations
    Réponses: 2
    Dernier message: 17/09/2008, 17h52
  4. [SSIS][2k5] jointure entre très grosse table
    Par RicardMan dans le forum SSIS
    Réponses: 1
    Dernier message: 18/04/2008, 16h54
  5. Gestion de très grosse table
    Par Arni23 dans le forum Requêtes
    Réponses: 11
    Dernier message: 04/06/2007, 20h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo