trier un fichier

Version imprimable

03/03/2007, 19h22
jeje_38

trier un fichier

bonjour
je possède un fichier texte que je souhaite trier par ordre croissant
je me tourne vers vous afin de savoir quelle solution est la plus simple et rapide à mettre en oeuvre pour réaliser ce tri.
MERCI
03/03/2007, 19h25
®om

Comment se présente ton fichier, et tu veux le trier selon quoi?
03/03/2007, 19h59
jeje_38

Merci de votre aide
mon fichier représente des numéros de série (numérique et alphanumérique)

fichier entre 3500 numéros et 10 000.

je pensais lire le fichier, placer les données dans une LISTE de String
trier cette liste avec .sort()

ensuite écrire la liste dans un fichier temporaire

supprimer le fichier source et le remplacer par le temporaire.

mais ne vaudrais t' il pas mieux (question de rapidité) de mettre un place un tri
(tri bulle, tri dicotomique .....)

MERCI
03/03/2007, 20h17
®om

J'aurais fait ça aussi, une liste de String.

En fait, je dirais qu'il y a 2 méthodes : soit on utilise un TreeSet<String> qui trie lors de l'insertion, soit on utilise une List<String> qu'on remplit, et qu'on trie à la fin avec Collections.sort().

Pour les complexités, pour une arrivée des String aléatoire (sans ordre spécial) :

Pour le treeset, ça fait:
1 + log_2(1) + log_2(2) + ... + log_2(n-1)
= 1 + somme_{0 < i < n} (log_2(i))
= 1 + log_2((n-1)!)

Pour la liste, ça fait:
n + n*log_2(n) = n(1 + log_2(n))

Selon ton nombre d'élements tu choisis la solution :) (si je me suis pas trompé dans les calculs)
La liste semble plus rapide quand même au vu de la tête des formules, le (n-1)! est violent.

EDIT: après avoir fait le graphique, en fait la factorielle est bien absorbée par le log, et donc avec plein d'éléments le treeset est plus rapide, même si le rapport entre les 2 décroit en fonction du nombre d'éléments.

EDIT2: Vu que les 2 fonctions semblent tendre à être quasiment proportionnelles, quand le nombre d'éléments est grand, ça veut dire que leur complexité est à un facteur k près, et donc que l'étude de leur complexité ne suffit pas à dire laquelle sera la plus rapide (ça dépend ce que chacune fait pendant 1 unité de complexité).

Si tu pouvais tester les 2, ça m'intéresserait de savoir :)

Suite à un exemple simple, la liste est plus rapide:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class TestTri {
 
    public static void main(String... args) {
        final int NB_ITER = 500000;
        long tmp;
 
        Random random = new Random();
 
        tmp = System.nanoTime();
 
        List<Double> list = new ArrayList<Double>();
        for (int i = 0; i < NB_ITER; i++)
            list.add(random.nextDouble());
 
        System.out.println("durée remplissage list: " + (System.nanoTime() - tmp));
 
        Collections.sort(list);
 
        System.out.println("durée list: " + (System.nanoTime() - tmp));
 
        tmp = System.nanoTime();
        Set<Double> set = new TreeSet<Double>();
        for (int i = 0; i < NB_ITER; i++)
            set.add(random.nextDouble());
 
        System.out.println("durée set: " + (System.nanoTime() - tmp));
 
    }
 
}

Affichage:

Code:

1
2
3
durée remplissage list: 462309316
durée list: 1590834869
durée set: 2937609389

Cependant, il y a un autre élément à prendre en compte, c'est que le TreeSet forcément n'accepte pas les doublons...

EDIT: je viens de modifier, il y avait une petite erreur dans le code, ce qui inversait les résultats :)

05/03/2007, 08h51
jeje_38

Merci
pour toutes ces infos
je code donc sur le principe de la liste de STRING
qui semble donc ête la plus rapide
à vérifier !!
MERCI.