ArrayList et doublons, cas vraiment particulier

Version imprimable

25/01/2012, 20h28
Levaillant

ArrayList et doublons, cas vraiment particulier

Bonsoir,

Je suis en train de parser des fichiers contenant des informations
qui iront en base un peu plus tard, et j'ai tellement peur de mes
collègues que je suis en train de verrouiller le plus possible ce module
d'importation...
Bref, j'ai une contrainte forte sur la table en question, et j'essaye de
faire en sorte que les données que je vais lui envoyer soient les plus
propres possibles!

J'aurais besoin de conseils quant à la recherche et destruction de
tous les doublons, afin de ne garder que ce qui n'a aucun
doublon. En gros, j'ai un fichier

date1,valeurX
date2,valeurX
...
dateN,valeurX

mon conteneur est

mon conteneur{
Timestamp date;
Float valeur
}

Si il y a un doute car la date est en doublon sur une ou plusieurs
lignes, j'ai le devoir d'enlever le/les doublon(s) ET la première
donnée qui serait "doublonnée", je ne suis pas sur d'être plus clair :mrgreen:

Donc il y aurait bien l'utilisation d'un Set particulier (HashSet il
me semble) mais ce dernier ne résoudra pas vraiment mon problème.
La contrainte est sur la date bien entendu.

J'ai peur de ré-inventer la roue, et c'est pourtant ce que je suis
en train de faire... des idées?

Typiquement la solution apportée ici par vincent63:
http://www.developpez.net/forums/d64...ever-doublons/
Code:

1 2 3 4 5 6 7 8 9 10 11 12 System.err.println("Début"); ArrayList arrayList = new ArrayList(); arrayList.add("a"); arrayList.add("b"); arrayList.add("c"); arrayList.add("d"); arrayList.add("a"); System.err.println(arrayList); System.err.println("On utilise des ensembles"); Set set = new TreeSet(); set.addAll(arrayList); System.err.println(set);
Code:

1 2 3 4 Début [a, b, c, d, a] On utilise des ensembles [a, b, c, d]
ne suffit pas, je voudrais obtenir un ensemble [b,c,d]

Je ferais plutot comme ceci:

une Map<Timestamp,Donnee> contenu
un Set<Timestamp> (doublons)
et l'algo suivant:
Code:

1 2 3 4 5 6 7 8 pour chaque entree lue if map.contains(timestamp) doublons.add(timestamp) sinon contenu.add(timestamp,donnee) fin pour four chaque doublon contenu.remove(doublon)

Bon, j'ai continué sur une idée que j'ai eu, et j'obtiens un résultat
à peu près (en fait tout à fait) cohérent:
En gros, j'ai modifié un peu mon bean de donnée comme suit:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package Main;
 
import java.sql.Timestamp;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.logging.Level;
import java.util.logging.Logger;
 
public class bean {
 
    private SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    private Timestamp date;
    private Float mesure;
    private boolean aDoublon = false;
 
    bean(String date, float valeur) {
        try {
            this.date = new Timestamp(sdf.parse(date).getTime());
            this.mesure = valeur;
        } catch (ParseException ex) {
            Logger.getLogger(bean.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
 
    public Timestamp getDate() {
        return date;
    }
 
    public Float getMesure() {
        return mesure;
    }
 
    public boolean aDoublon() {
        return aDoublon;
    }
 
    @Override
    public boolean equals(Object o) {
        if (o == this) {
            aDoublon = true;
            return true;
        }
        if (!(o instanceof bean)) {
            return false;
        }
        final bean unAutreBean = (bean) o;
        if (unAutreBean.getDate().equals(this.getDate())) {
            this.aDoublon = true;
            unAutreBean.aDoublon = true;
            return true;
        } else {
            return false;
        }
    }
 
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 47 * hash + (this.sdf != null ? this.sdf.hashCode() : 0);
        hash = 47 * hash + (this.date != null ? this.date.hashCode() : 0);
        hash = 47 * hash + (this.mesure != null ? this.mesure.hashCode() : 0);
        hash = 47 * hash + (this.aDoublon ? 1 : 0);
        return hash;
    }
 
    public void afficher() {
        StringBuilder tmp = new StringBuilder();
        tmp.append(sdf.format(this.date));
        tmp.append("\t");
        tmp.append(this.mesure);
        tmp.append("\t");
        tmp.append(this.aDoublon);
        System.out.println(tmp.toString());
    }
}

Donc avec en gros un tag aDoublon et une redéfinition de la méthode
equals (normal) avec dans cette dernière une facon de qualifier la donnée
testée avec une autre...

Le "main":

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package Main;
 
import java.text.ParseException;
import java.util.ArrayList;
import java.util.Iterator;
 
public class testArrayList {
 
    private ArrayList<bean> listBeanClassique = new ArrayList<bean>();
    private ArrayList<bean> listBeanEvolue = new ArrayList<bean>();
 
    public void testArrayList() throws ParseException {
        //////////////////////////////////////////////////
        // les data
        // bean1 = bean2
        // bean5 = bean6
        bean unBean1 = new bean("2012-01-01 00:00:00", 0F);
        bean unBean2 = new bean("2012-01-01 00:00:00", 1F);
        bean unBean3 = new bean("2012-01-01 00:00:02", 2F);
        bean unBean4 = new bean("2012-01-01 00:00:03", 3F);
        bean unBean5 = new bean("2012-01-01 00:00:04", 4F);
        bean unBean6 = new bean("2012-01-01 00:00:04", 5F);
 
        //////////////////////////////////////////////////
        // Classique
        listBeanClassique.add(unBean1);
        listBeanClassique.add(unBean2);
        listBeanClassique.add(unBean3);
        listBeanClassique.add(unBean4);
        listBeanClassique.add(unBean5);
        listBeanClassique.add(unBean6);
 
 
        //////////////////////////////////////////////////
        // Evolué entre de grosses guillemets!!!
        // aucune prétention de ma part ;-)
        if (!listBeanEvolue.contains(unBean1)) {
            listBeanEvolue.add(unBean1);
        }
        if (!listBeanEvolue.contains(unBean2)) {
            listBeanEvolue.add(unBean2);
        }
        if (!listBeanEvolue.contains(unBean3)) {
            listBeanEvolue.add(unBean3);
        }
        if (!listBeanEvolue.contains(unBean4)) {
            listBeanEvolue.add(unBean4);
        }
        if (!listBeanEvolue.contains(unBean5)) {
            listBeanEvolue.add(unBean5);
        }
        if (!listBeanEvolue.contains(unBean6)) {
            listBeanEvolue.add(unBean6);
        }
        // plus un petit traitement
        Iterator iterator = listBeanEvolue.iterator();
        while (iterator.hasNext()) {
            bean a = (bean) iterator.next();
            if (a.aDoublon()) {
                iterator.remove();
            }
        }
 
 
        //////////////////////////////////////////////////
        // Affichage
        System.out.println("Classique");
        for (bean a : listBeanClassique) {
            a.afficher();
        }
 
        System.out.println("Sans doublons");
        for (bean a : listBeanEvolue) {
            a.afficher();
        }
 
    }
}

Le résultat:

Code:

1
2
3
4
5
6
7
8
9
10
Classique
2012-01-01 00:00:00	0.0	true
2012-01-01 00:00:00	1.0	true
2012-01-01 00:00:02	2.0	false
2012-01-01 00:00:03	3.0	false
2012-01-01 00:00:04	4.0	true
2012-01-01 00:00:04	5.0	true
Sans doublons
2012-01-01 00:00:02	2.0	false
2012-01-01 00:00:03	3.0	false

Je vais tester çà sur un set de données conséquent, environ 10Mo de texte,
mais j'ai bien peur que les performances ne soient pas au rendez vous, donc
le sujet est toujours ouvert, et si quelqu'un a une meilleure solution, je suis
vraiment preneur! :)

Bon, j'ai modifié mon code, j'ai lancé ma lecture du fichier, je suis allé
fumer une clope, je suis revenu, j'ai checké mes mails, j'ai vu ton message
tchize_ :ccool:, et c'est encore en train de faire son job :)
Bref, c'est vraiment pas acceptable en terme de performance lol

@tchize_:
Je pense avoir adopté dans mon dernier test ton algo, mais il faut se
rendre à l'évidence, ca marche pour quelques (petits) milliers de lignes
parsées, mais dans mon cas, je crois que c'est mort...
j'utilise un ArrayList parce que:

1- je peux le dimensionner presque exactement
2- parce que les ArrayList sont plus performants dans les ajouts en fin de liste, ce qui correspond bien à mon cas, car les lignes de mon fichier ne sont pas forcement dans un ordre chronologique
3- parce que un Collection.sort() est vraiment très rapide
du coup la solution que tu évoques et que je viens de tester n'est pas satisfaisante. Je pensais à la base faire un truc du genre:
Code:

1 2 3 4 5 6 7 lecture ligne à ligne: je parse et ajoute ma ligne classement de la liste en ordre chronologie (vu que ma contrainte est sur la date) lecture de ma liste par ligne si ma ligne != ligne suivante ajout dans une nouvelle liste ...
bref, ce n'est pas réellement satisfaisant, quelque soit la méthode...
un peu déprimé ce soir :cry:

26/01/2012, 10h01
thelvin

Tu veux dire

- que tu as essayé d'adapter le code de tchize en remplaçant les Map et Set par des List, et que tu trouves ça (sans surprise) très inefficace, ou

- que tu as pris son algo tel que, et que ce n'est pas assez rapide, alors tu as essayé avec des List à la place (ce qui ne risque pas de faire mieux)

?

Edit : je viens de tenter l'algo de tchize_ sur des données aléatoires dans un fichier de 10Mo+. Le dédoublonnage avec classement des résultats prend environ 4 secondes sur ma machine, l'écriture des résultats 1 seconde. Soit un traitement total d'à peu près 5 secondes.
26/01/2012, 17h55
Levaillant

t'as raison, je vais revoir ma copie, je ne sais plus trop ce que
j'essaye de faire...
Je vais reprendre en l'état l'algo de tchize, remplacer mes lists
par des maps et sets, et je vous tiens au courant
:ccool:

Soit dit en passant, la dernière solution envisagée :
Code:

1 2 3 4 5 6 lecture ligne à ligne: je parse et ajoute ma ligne classement de la liste en ordre chronologie (vu que ma contrainte est sur la date) lecture de ma liste par ligne si ma ligne != ligne suivante ajout dans une nouvelle liste
fonctionne aussi sur le principe et est presque aussi rapide. Mais elle demande jusqu'au double de mémoire.

26/01/2012, 22h12
Levaillant

Bon, je n'arrive à rien ce soir :calim2:
trop de fatigue, je n'arrive pas à modifier mon code pour arriver
à intégrer l'algo de tchize avec ces maps et sets!
Le truc est que mon bean n'est pas aussi simple qu'indiqué avant,
je devrais faire un map<TimestampIssuDeMonBean, bean> avec
mon bean contenant un Timestamp, valeur1, valeur2, .., valeurX
pour continuer mes tests de performance
Bref, je patauge ce soir, mais cela doit venir plus de ma méconnaissance
des Collections maps et set qu'autre chose...
@ thelvin:
Je suis preneur de ton générateur de fichier aléatoire, et du code
qui tu as testé ;)
26/01/2012, 23h10
tchize_

LEvaillant, le timestamp était un exemple, n'importe quelle classe supportant equals / hashcode correctement (dans ton sens de l'égalité) ferait l'affaire.
26/01/2012, 23h23
Levaillant

Je pense que mon problème vient de l'interface cerveau - clavier (et non je ne parle pas de mes mains :mouarf:)
Je vais tenter de remettre mon problème à plat, et refaire mes objets de telle sorte qu'ils seront compatibles avec un treeset et le set doublon que tu évoquais... Je ne suis pas un bon "algorithmiste", et/mais malheureusement je suis trop perfectionniste pour laisser la solution lente actuelle perdurer!
En tout cas, restez connectés sur ce fil, j'aurais sans doute besoin d'un coup de main pour conceptualiser mon modèle de donnée :zoubi:
Bref, c'est à moi de bosser pour le moment :ccool:

J'ai donc un fichier avec un entete

NOM
DEFINITION MESURE 1
DEFINITION MESURE 2
DEFINITION MESURE 3
...
DEFINITION MESURE N
DATE 1, MESURE 1, MESURE 2, MESURE 3, ..., MESURE N
DATE 2, MESURE 1, MESURE 2, MESURE 3, ..., MESURE N
DATE 3, MESURE 1, MESURE 2, MESURE 3, ..., MESURE N
...
DATE N, MESURE 1, MESURE 2, MESURE 3, ..., MESURE N

du coup, je m'étais fait un bean mesure:
Code:

1 2 3 4 5 6 7 public class mesure { private Timestamp date; private Float mesure; private boolean nouvelle = true; private boolean valide = true; // les getters et setters... }
un autre bean, qui représentait un ensemble de MESURE X, ce que je nomme une voie
Code:

1 2 3 4 5 6 7 8 9 10 public class voie { private Integer numeroVoie; private Integer indexVoie; private String typeVoie; private String commentaireVoie; private String uniteVoieFichier; private ArrayList<mesure> listeMesures = new ArrayList<mesure>(); private boolean valide = true; // les getters et setters... et le addMesure }
et finalement un autre bean qui était sensé bien représenter mon fichier, enfin surtout son contenu:
Code:

1 2 3 4 5 public class beanDataFichier { private String nom; private ArrayList<voie> listeVoies = new ArrayList<voie>(); // les getters et setters... et le addVoie }
Ce qui conceptuellement me donnait:

NOM VOIE 1 DATE 1 MESURE 1
NOM VOIE 1 DATE 2 MESURE 2
NOM VOIE 1 DATE 3 MESURE 3
...
NOM VOIE 1 DATE N MESURE N

NOM VOIE 2 DATE 1 MESURE 1
NOM VOIE 2 DATE 2 MESURE 2
NOM VOIE 2 DATE 3 MESURE 3
...
NOM VOIE 2 DATE N MESURE N

NOM VOIE 3 DATE 1 MESURE 1
NOM VOIE 3 DATE 2 MESURE 2
NOM VOIE 3 DATE 3 MESURE 3
...
NOM VOIE 3 DATE N MESURE N

NOM VOIE N DATE 1 MESURE 1
NOM VOIE N DATE 2 MESURE 2
NOM VOIE N DATE 3 MESURE 3
...
NOM VOIE N DATE N MESURE N

Tout ca pour arriver le plus proche possible de mon but, à savoir l'insertion en base de

NOM VOIE N DATE N MESURE N
avec ma fameuse contrainte sur la clé primaire constituée de NOM VOIE N DATE N
Est ce que cela vous semble correct?

Bon, ce fil n'a pas été très suivi, j'aurais bien eu besoin de vos
aides concernant ma modélisation, mais somme toute, les bonnes
réponses étaient déjà dans vos propositions :ccool:

J'ai repris à "zero", et donc à la lecture du fichier, je me suis forcé
à mapper les lignes lues dans :
Code:

1 2 private Map<Timestamp, ArrayList<Float>> contenu = new TreeMap<Timestamp, ArrayList<Float>>(); private Set<Timestamp> doublons = new HashSet<Timestamp>();
l'algorithme restant exactement celui de tchize_, à savoir:
Code:

1 2 3 4 5 6 7 8 pour chaque entree lue if map.contains(timestamp) doublons.add(timestamp) sinon contenu.add(timestamp,donnee) fin pour four chaque doublon contenu.remove(doublon)
J'ai ensuite rempli mon beanData originel composé de x voies
avec y mesures, et l'ai rangé chronologiquement comme suit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 for (Entry<Timestamp, ArrayList<Float>> entry : contenu.entrySet()) { resultPkDate = entry.getKey(); listeMesureFloat = entry.getValue(); int i = 0; for (voie uneVoie : beanData.getListeVoies()) { uneMesure = new mesure(); uneMesure.setResultPkDate(resultPkDate); uneMesure.setResultMesure(listeMesureFloat.get(i)); uneVoie.addUneMesure(uneMesure); i++; } } contenu.clear(); // Tout le beanData a été rempli, classons le par ordre chronologique for (voie uneVoie : beanData.getListeVoies()) { Collections.sort(uneVoie.getListeMesures()); }
Question performance:
Alors oui, le parsing du fichier, enfin le remplissage de mon map est
plus long de quelques secondes, par contre, la recherche et la
destruction des doublons est (quasi) instantanée!
Pour moi l'objectif est absolument atteint!

Quant à l'insertion ou l'update en base, je me suis servi d'un post sur ce
même forum... il ne faut pas utiliser un PreparedStatement pour les
insert, cela marche, mais aussi bizarre que cela puisse paraître, un
StringBuilder genre
Code:

1 2 3 4 5 "INSERT INTO maTable(date,valeur) VALUES (date1,valeur1), (date2,valeur2), ... (dateN,valeurN);"
lancé une seule fois au serveur (Postgres dans mon cas) a divisé par
deux les temps d'insertion (par rapport à des PreparedStatements donc)
en gros, un fichier de plus ou moins 10Mo avec près de 300 000 données
peut être inséré en base avec des controles préalable en moins de 20
secondes!

En gros, merci encore pour vos aides, cela faisait longtemps que je ne
m'étais pas pris la tête sur ce genre de détail et la satisfaction d'avoir
atteint cet objectif me fait bien plaisir... Je vous dois un demi à chacun!
:chin: