besoin d'un conseil....

keke · Le 09/05/2006, à 18:06

Voila, j'obtiens à partir d'un logiciel un fichier texte contenant plus de 5000 points (un point equivaut à une corrdonnée suivant x, y ,z). Il me faut les classer suivant z et la position angulaire suivant x et y. Est il possible de le faire directement de ce fichier à un autre.Si oui comment, sinon comment feriez vous ( liste chainé, tableau) sachant que le temps de traitement rentre en ligne de compte.

merci pour vos nombreuses reponses...

kéké

gene69 · Le 10/05/2006, à 01:01

hum...
pour trier un fichier, avec lecture d'une file, ya rien de mieux que le tri fusion.
en compléxité on est en n*log(n) parce qu'on trie...
Le qsort n'est pas adapté parce que tu n'as pas un tableau en mémoire. 5quick Sort) cependant il à une moyenne meilleure parce qu'il peut y avoir des simplifications en cour de route.

Niveau complexité construire un abre est équivalent à condition que ce soit un AVL.

faire une liste chainée... même circulaire ce n'est pas une super option.

D'apres mon prof d'algo complexe c'est les arbres quaternaires les plus performants.(noir/rouges) mais bon, si tu penses qu'une structure linéaire peu être comparée à une structure bilineaire...

Sur un jeu de donnée de 5000000 d'individus si mes souvenirs sont bons le tri bulle prenait 15 mintes, et le quick sort 1 secondes. L'autre côté pense que tu va acceder au disque dur, et que 5000 points c'est rien par rapport aux latences de ton disque. Si tu veux travailler la complexiter alors il faut que tu charges ton fichier en memoire (tableau dynamique ! insertion en o(1)): le temps de lecture doit être isolé dans ton cas, PUIS tu tries.

mesmento · Le 10/05/2006, à 09:13

hé hé...

un script utilisant awk et sort ?

La commande sort devrait beaucoup t'aider.

aleph · Le 10/05/2006, à 16:44

Python permet de résoudre ce problème élégamment et assez simplement.
1) Lecture de toutes les données du fichier texte en une passe, elles
seront sauvegardées dans un string.
2) Transformation de ce string en une liste de tuple's.
3) Tri de la liste, <list>.sort()
4) Enregistrement de la liste triée dans un fichier texte.

Ici, l'élégance de Python réside dans le fait que Python sait
comparer des tuples, une des conséquences induite de cette propriété
est que trier un liste de tuples est, pour Python, aussi simple que
trier une liste de nombres (entiers ou floats).

Exemple de comparaison de tuples:

(1, 2, 3) < (2, 2, 3) < (2, 2, 4) -> True

J'ai effectué quelques tests, PIII, 500MHz, win2k. Trier une liste
de 5000 3-tuple's de floats prend moins d'une seconde. Environ 1 seconde
pour 10000 tuple's. Je dis environ, c'est le temps que prend mon éditeur
pour exécuter le script et afficher mon message 'fini'.
Tout ça en 20 lignes de programme.

J'adore Python. Ce langage de programmation a vraiment ce petit quelque
chose de plus que les autres n'ont pas.

gene69 · Le 10/05/2006, à 22:57

mouais.
python sais faire de la surcharge d'opérateur et alors? C++ aussi.

Et même en C on peut faire un truc équivalent (qui s'appelle un pointeur sur fonction mais bon... à déconseiller à un namateur)

C ya vraiment rien en trop.

keke · Le 11/05/2006, à 00:57

ca roule! Pour ma part, mes prof m'ont conseillé de lire tout le fichier en une fois, de stocker les variables dans un tableau et de trier le tableau par la méthode du tri a bulle.Vous en pensez quoi comme temps de traitement?
A part, vous savez quoi de la compatibilité entre les programmes fait sous visual C et compilé sous visual C et ceux réalisé sous linux.Ca serait pour faire passer un programme fait en objet sous visual directement sur linux en étant capable de le compiler.

aleph · Le 11/05/2006, à 09:41

> gene69
...python sais faire de la surcharge d'opérateur et alors? C++ aussi....

Oui, c'est exactement cela. Python permet "nativement" la création de types de variable et la définition des opérateurs associés à ces types de variable. C'est pour ainsi dire l'essence de ce langage. Python propose par défaut certains types de variables et ses opérateurs, list, tuple, dictionary en plus des entiers, floats et compagnie. Rien n'empêche l'utilisateur de créer ses propres types et les règles opératoires associées. Commes les types sont des classes, il est très aisé d'ajouter des méthodes.
C'est assez rigolo de jouer avec Python. On peut facilement créer un type "nombre pair" et (re)définir toutes les opérations associées à ce type, addition, division, etc.
Un exemple pratique qui revient fréquemment est le type matrice (au sens mathématique).
Si tu aimes la programmation et ne connaît pas Python, je ne peux que te conseiller d'y jeter un oeil. Pour le fun...
Je crois que le language Ruby permet aussi de le faire simplement. Mais j'ai très peu d'expérience avec Ruby.

Cela dit, mon intervention n'était pas de démontrer la supériorité de tel ou tel langage de programmation. Notre ami keke a un problème et cherche conseil. Je lui ai proposé une solution qui permet de résoudre son problème. Il m'a fallu cinq minutes pour écrire une application qui teste les tris. Si j'ajoute le code de lecture et d'écriture de fichier, l'écriture d'une application complète serait réglée en 30-60 minutes.

Maintenant si keke veut faire le travail en Visual C. Libre à lui. Un bon informaticien n'est pas simplement quelqu'un qui sait programmer, c'est aussi une personne qui sait choisir les outils qu'il veut utiliser.

Keke, je serais curieux de connaître la réaction de tes profs si tu leur disait que quelqu'un t'a proposé une solution simple à ton problème. (Je ne sous-estime pas tes profs).

keke · Le 11/05/2006, à 23:15

merci pour tous ces precieux renseignements mais de base je ne suis pas un informaticien en herbe...Certes,la programmation me plait beaucoup et j'aimerais avoir le temps pour m'y penchait dessus mais en ce moment le projet que je fais est suffisamment tendu pour trouver du temps à passer sur python.Lorsque j'ai attaqué ce projet,je ne connaissais pas linux, ni ubuntu,ni glade,ni l'architecture d'un programme.J'étais vide de connaissance.Bon aujourd'hui,j'arrive à me débrouiller avec les compilateurs,les .h,.c,.cpp et c'est déjà une réussite.Pour ce qui est de mes professeurs,tant que j'arrive à programmer le robot suivant une méthode abordable par tous,rien n'importe plus.aleph,si tu as des sites sympa à poster pour expliquer Python et Ruby,n'hésite pas.J'en ferais pour ma part,bonne usage dans les mois à venir.Merci pour tes conseils

Dernière modification par keke (Le 12/05/2006, à 00:47)

mesmento · Le 12/05/2006, à 00:19

Un bon informaticien n'est pas simplement quelqu'un qui sait programmer, c'est aussi une personne qui sait choisir les outils qu'il veut utiliser.

Exactement.

bobuse · Le 12/05/2006, à 10:55

Tiens, quelques URL pour python :
http://del.icio.us/bobuse/python

J'aime bien ce langage pour développer rapidement des petites choses, c'est assez pratique. Il y a apparemment pas de possibilités avancé, mais que je n'ai pas encore le loisir d'étudier ...

gene69 · Le 12/05/2006, à 14:29

Un bon informaticien n'est pas simplement quelqu'un qui sait programmer, c'est aussi une personne qui sait choisir les outils qu'il veut utiliser.

je suis d'accord avec toi. Malheureusement on n'a pas toujours le choix.

Je sais aussi que la surchage d'opérateur peut être problématique au niveau performance parce qu'on fait moins attention à la complexité d'un opérateur simple qu'à une fonction qu'on a mis des heures à débugger.

Un tri bulle n'est pas un bon choix pour la complexité o(n2) si c'est la complexité du tris qui compte et que tu as un niveau supérieur à Bac+2. Bon apres c'est quand même sacrément plus facile...

Mathieu147 · Le 12/05/2006, à 14:40

Ça intéresse quelqu'un un résumé sur les algos de tri?

aleph · Le 12/05/2006, à 15:03

> gene69

>je suis d'accord avec toi. Malheureusement on n'a pas toujours le choix.
Entièrement d'accord.

>Je sais aussi que la surchage d'opérateur peut être problématique au niveau performance...
Oui.

> parce qu'on fait moins attention à la complexité d'un opérateur simple qu'à une fonction qu'on a mis des heures à débugger.

Pas tout à fait d'accord, du moins pour Python. La raison : chaque classe que l'on crée à des méthodes "builtins" déja prédéfinies au niveau du langage qui prévoient l'utilisation des opérateurs. Ces méthodes sont par ex. __add__, __div__, __len__, __iter__ ou __getitem__, __setitem__ pour des variables indexées. C'est bigrement malin et efficace pour veut les utiliser.

keke · Le 12/05/2006, à 17:43

> gene69

Je ne connaissais pas le tri à bulle mais je dois avouer que c'est super simple et que ça marche plutot bien.Dans une réponse, je disais que je cherchais à optimiser le temps de traitement mais dans les tri que je fais, cela se fait en 2s...allons bon, à quoi aller chercher un temps de traitement inférieur.Dans mon cas, je trie 2000 points sachant qu'un point correspond a un mouvement de machine,ça nous fait une bonne heure d'usinage....

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 09/05/2006, à 18:06

besoin d'un conseil....

#2 Le 10/05/2006, à 01:01

Re : besoin d'un conseil....

#3 Le 10/05/2006, à 09:13

Re : besoin d'un conseil....

#4 Le 10/05/2006, à 16:44

Re : besoin d'un conseil....

#5 Le 10/05/2006, à 22:57

Re : besoin d'un conseil....

#6 Le 11/05/2006, à 00:57

Re : besoin d'un conseil....

#7 Le 11/05/2006, à 09:41

Re : besoin d'un conseil....

#8 Le 11/05/2006, à 23:15

Re : besoin d'un conseil....

#9 Le 12/05/2006, à 00:19

Re : besoin d'un conseil....

#10 Le 12/05/2006, à 10:55

Re : besoin d'un conseil....

#11 Le 12/05/2006, à 14:29

Re : besoin d'un conseil....

#12 Le 12/05/2006, à 14:40

Re : besoin d'un conseil....

#13 Le 12/05/2006, à 15:03

Re : besoin d'un conseil....

#14 Le 12/05/2006, à 17:43

Re : besoin d'un conseil....

Pied de page des forums