Rapidité : Tableau vs. List(Of T)

Version imprimable

Voir 40 message(s) de cette discussion en une page

Citation:

Envoyé par DonQuiche

Tiens, j'avais loupé un truc très laid et cause de dégradation de performances dans ton code... Vire donc la variable dernierIndex et utilise plutôt listeRecompose.Count - 1 à la place. Avec ce bête IndexOf tu ajoutes quelques dizaines de millions de comparaisons pour ton fichier de 14k lignes. :aie:

Ok j'ai corrigé ça !

Citation:

Envoyé par DonQuiche

Enfin, concernant les concaténations. Essaye de modifier ton code pour utiliser un StringBuilder que l'on recyclera. En gros, code en C# (allergique au VB, désolé)

J'ai du mal à assimiler pour le string builder. Il s'agit d'une espece de boite où je vais ajouter au fur et à mesure des strings grâce à Append, et à la fin j'ajoute la boite à ma liste ? C'est ça ?

J'ai fais ça, mais j'imagine que j'ai rien compris, vu que ça empire de 4 secondes :oops:.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Shared Function IdentifierLog(ByVal CheminFichier As String, ByVal Regex As Regex) As List(Of String) Dim listeRecomposee As New List(Of String) Dim listeDeString As List(Of String) = LogManager.LireFichier(CheminFichier) Dim builder As New StringBuilder("") For Each ligne In listeDeString ' Si la ligne est un nouveau log, alors on ajoute ce que contenait jusque là le buider. If Regex.Match(ligne).Success Then listeRecomposee.Add(builder.ToString()) builder.Length = 0 builder.Append(ligne) ' Sinon la ligne n'est pas un nouveau log, on l'ajoute au builder Else builder.Append(ligne) End If Next listeRecomposee.RemoveAt(0) Return listeRecomposee End Function

09/05/2012, 14h33
DonQuiche

Citation:

Envoyé par shurikeNzL

J'ai du mal à assimiler pour le string builder. Il s'agit d'une espece de boite où je vais ajouter au fur et à mesure des strings grâce à Append, et à la fin j'ajoute la boite à ma liste ? C'est ça ?

Tel que tu l'utilises toi, tu recrées toujours une chaîne même si ton log ne contenait qu'une ligne. Le code que j'avais proposé évitait cela en n'ayant recours au StringBuilder qu'à compter du moment où une concaténation était vraiment nécessaire.

Sinon le StringBuilder est effectivement une list de caractères et il est donc relativement peu coûteux d'y ajouter de nouvelles chaînes. Moins coûteux en tout cas que l'instanciation de nouvelles chaînes en série avec à chaque fois allocation de nouveaux tableaux. Tu devrais mesurer un gain sensible à compter de trois lignes par log.

Citation:

Envoyé par DonQuiche

Tel que tu l'utilises toi, tu recrées toujours une chaîne même si ton log ne contenait qu'une ligne. Le code que j'avais proposé évitait cela en n'ayant recours au StringBuilder qu'à compter du moment où une concaténation était vraiment nécessaire.

Oui, mais en faite, moi je fais une allergie au C# :P.
J'ai essayé de traduire ton code en VB.NET, mais j'ai du me tromper à un endroit...

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
    Shared Function IdentifierLog(ByVal CheminFichier As String, ByVal Regex As Regex) As List(Of String)
        Dim listeRecomposee As New List(Of String)
        Dim builder = New StringBuilder(1000)
        Dim listeDeString As List(Of String) = LogManager.LireFichier(CheminFichier)
        Dim logMonoLigne As String = Nothing
        Dim e = listeDeString.GetEnumerator()
 
        While (True)
            Dim pasFin As Boolean = e.MoveNext()
            Dim logComplet As Boolean = (pasFin = False Or Regex.Match(e.Current).Success)
 
            ' On a complété un log, ajoutons-le
            If (logComplet) Then
                ' Plus d'une ligne ?
                If (builder.Length > 0) Then
                    listeRecomposee.Add(builder.ToString())
                    builder.Length = 0
                End If
                ' Une seule ligne
            ElseIf (logMonoLigne <> Nothing) Then
                listeRecomposee.Add(logMonoLigne)
            End If
 
 
            If (pasFin = False) Then
                Exit While
            End If
 
            ' On démarre un nouveau log ?
            If (logComplet) Then
                logMonoLigne = e.Current
                ' On continue un log ayant déjà une ou plusieurs lignes
            Else
                ' Une seule ligne ?
                If (logMonoLigne <> Nothing) Then
                    builder.Append(logMonoLigne)
                    logMonoLigne = Nothing
                End If
                builder.Append(e.Current)
            End If
        End While
 
        Return listeRecomposee
    End Function

09/05/2012, 14h52
DonQuiche

Tout ce que je vois comme problème c'est :
* Ligne 10 : OrElse et non pas Or, sinon exception à la fin. Qui plus est, dans le doute, j'isolerais "pasFin = False" dans des parenthèses au cas où...
* Pas de bloc finally (comme dans try-catch-finally) pour appeler e.Dispose()

Si c'est autre chose, merci de préciser. ;)
09/05/2012, 15h18
shurikeNzL

Citation:

Envoyé par DonQuiche

Tout ce que je vois comme problème c'est :
* Ligne 10 : OrElse et non pas Or, sinon exception à la fin. Qui plus est, dans le doute, j'isolerais "pasFin = False" dans des parenthèses au cas où...
* Pas de bloc finally (comme dans try-catch-finally) pour appeler e.Dispose()

Si c'est autre chose, merci de préciser. ;)

Ok voilà, c'est fait. Mais c'est toujours pas acceptable niveau durée. Je n'ai gagné que 5 secondes, c'est beaucoup. Mais peu comparé au total d'1 minute 45 secondes... :roll:

Merci quand même en tout cas. :aie:
09/05/2012, 15h26
Er3van

Je te conseille d'utiliser des logs et la classe StopWatch pour voir à quel endroit tu perds du temps, car compte tenu de ce que fais ton code, tu ne devrais pas mettre aussi longtemps.

Commence par mettre des chronomètres aux niveaux des blocs, puis descend ligne à ligne une fois que tu as identifié ce qui mettait du temps.
09/05/2012, 15h32
DonQuiche

Je rejoins Er3van sur le fait que ça ne devrait pas prendre tant de temps et j'en appelle pour la troisième fois à l'utilisation d'un profiler (plutôt que des stopwatch). ;)

Par ailleurs, quid du devenir de ces chaînes ? Vont-elles être affichées ? Écrites dans un fichier ?
09/05/2012, 15h48
Er3van

... ou un profiler ! ;)

Quand ça reste à ce niveau de complexité je préfère me contenter de StopWatch, un profiler c'est un peu comme utiliser un tank pour tuer une mouche dans notre cas.

Je sens qu'on va finir par trouver que les 115 secondes de perdues le sont en temps d'écriture disque ou autre perte réseau...
09/05/2012, 16h06
shurikeNzL

Citation:

Envoyé par DonQuiche

Je rejoins Er3van sur le fait que ça ne devrait pas prendre tant de temps et j'en appelle pour la troisième fois à l'utilisation d'un profiler (plutôt que des stopwatch). ;)

Par ailleurs, quid du devenir de ces chaînes ? Vont-elles être affichées ? Écrites dans un fichier ?

Elles seront parsées, pour devenir des type Log, rangés dans une List(Of Log), qui sera retournée pour affichage dans un datagrid. Pas d'écriture.

J'ai éssayé stopwatch, donc le problème est bien au niveau de la concaténation. 1 minutes 38 à tous les essais pour la fonction décrite précédemment, pour mon fichier test.

EDIT : Ma remarque précédente est vraie que ce soit pour la concaténation, ou le stringbuilder. Conclusion -> J'ai mal traduit ton code de tout à l'heure.

EDIT2 : Chaque traitement de ligne est énorme quand même, avec une moyenne de 0,0005 secondes et des piques a 0,20 secondes ! Outch !
Le match de la regex prend 0,00002 secondes en moyenne.
09/05/2012, 17h08
DonQuiche

Citation:

Envoyé par shurikeNzL

[B]EDIT : Ma remarque précédente est vraie que ce soit pour la concaténation, ou le stringbuilder. Conclusion -> J'ai mal traduit ton code de tout à l'heure.

Ouhlà ! Oui, dis-voir, je viens de rejeter un coup d'oeil et tu t'es emmêlé les pinceaux au niveau des Endif. Dans le post #23, vire celui à la ligne 18 et remets-le à la ligne 23.

Citation:

Envoyé par shurikeNzL

EDIT2 : Chaque traitement de ligne est énorme quand même, avec une moyenne de 0,0005 secondes et des piques a 0,20 secondes ! Outch !

Attention, le GC a pu se mettre en route à ce moment-là ou je ne sais quoi. Cela dit, quelle est la taille de tes lignes ? Quant au regex, tu as bien utilisé le constructeur que j'avais pointé, afin de compiler ?
10/05/2012, 08h04
shurikeNzL

Citation:

Envoyé par DonQuiche

Ouhlà ! Oui, dis-voir, je viens de rejeter un coup d'oeil et tu t'es emmêlé les pinceaux au niveau des Endif. Dans le post #23, vire celui à la ligne 18 et remets-le à la ligne 23.

Oui j'avais déjà corrigé dans mon code en faite.

Citation:

Envoyé par DonQuiche

Attention, le GC a pu se mettre en route à ce moment-là ou je ne sais quoi. Cela dit, quelle est la taille de tes lignes ? Quant au regex, tu as bien utilisé le constructeur que j'avais pointé, afin de compiler ?

Pour la regex, je croyais l'avoir fait mais non j'avais oublié. J'étais fatigué hier :mouarf:.
Déjà là, bonne nouvelle, gain de temps considérable me faisant passer de 98 secondes à 44 secondes !

Mais que ce soit avec la concaténation normale, ou ton code avec le builder, le résultat est toujours le même. 44 secondes.

Le fichier que je parse à chaque fois en guise de test fait 1,68Mo quand même... Et c'est vrai que les piques ont l'air proportionnels à la longueur des lignes.
10/05/2012, 08h45
DonQuiche

Citation:

Envoyé par shurikeNzL

Le fichier que je parse à chaque fois en guise de test fait 1,68Mo quand même... Et c'est vrai que les piques ont l'air proportionnels à la longueur des lignes.

1.68Mo, c'est à dire rien du tout. En ce moment j'ai des processus complexes de désérialisation, avec plusieurs chaînes de caractères, qui sont traités en 50ms pour des fichiers de 20Mo. Je réalise des analyses complexes de vidéos HD frame par frame, en appliquant à chaque fois filtres, transformations d'espaces de couleurs et calculs de statistiques, le tout à dix fois la vitesse normale de lecture des vidéos et sans utiliser le GPU. J'ai déjà écrit des codes de logiques floues et de rendu complexe devant s'exécuter à 60ips. Et tout ça en C# et sans optimiser beaucoup.

J'en appelle, pour la quatrième fois, à un profilage. Utilise EQATEC comme je l'avais proposé, isole Regex.Match et StringBuilder.Append dans des fonctions DoMatch(Regex, String) et DoAppend(StringBuilder, String) pour contourner les limites de la version gratuite et dis-nous ce que ça donne. A savoir les temps cumulés respectifs pour IdentifierLog, LireFichier, DoMatch et DoAppend.

Enfin, pendant ce temps-là, je te propose deux petits tests :
* Remplace tes strings par des tableaux de char et StringBuilder par une liste de chars. Je m'attends à un gain trop faible pour être intéressant mais je voudrais en être sûr.
* Trace la longueur de StringBuilder juste avant que celle-ci ne soit remise à zéro. Quel est le max obtenu ?
10/05/2012, 12h46
shurikeNzL

Ok, donc j'ai fais un coup du profiler que tu m 'a conseillé.
A priori ce serait le DoMatch qui pompe un temps énorme.
~3 milièmes de seconde pour matcher la Regex. On multiplie ça par le nombre de lignes, 14803 et on obtient un temps total ~44 secondes...

Bon ben je vais me débrouiller autrement pour l'identification des logs.

Merci pour ton aide et pour ce programme, très simple et efficace. :ccool:

Je pense pouvoir dire que le sujet est résolu, merci à tous.
10/05/2012, 13h08
meziantou

Un article sur les optimisations pour les chaines de caractères
http://www.codeproject.com/Articles/...perations-in-C
10/05/2012, 13h17
DonQuiche

Citation:

Envoyé par shurikeNzL

Ok, donc j'ai fais un coup du profiler que tu m 'a conseillé.
A priori ce serait le DoMatch qui pompe un temps énorme.
~3 milièmes de seconde pour matcher la Regex. On multiplie ça par le nombre de lignes, 14803 et on obtient un temps total ~44 secondes...

Nous aurions dû commencer par ça. ;)
Pour le regex, un petit conseil déjà : utilise plutôt IsMatch puisque tu n'as pas besoin des détails de la correspondance Ensuite, il se peut qu'en utilisant RegexOptions.CultureInvariant tu puisses aussi observer une différence. Tu peux aussi reconsidérer tes expressions régulières : certaines sont plus rapides que d'autres à exécuter. Enfin, wrapper la biblio PCRE peut être une bonne idée vu la lenteur du regex dotnet.
10/05/2012, 13h22
meziantou

La première chose avant d'optimiser la Regex : As-tu réellement d'utiliser une regex ?
A quoi ressemble ce que tu dois parser ? Peux-tu nous donner un exemple ?

Citation:

Pour le regex, un petit conseil déjà : utilise plutôt IsMatch

En effet ca évite de remplir la structure Match.
10/05/2012, 13h28
shurikeNzL

Citation:

Envoyé par DonQuiche

Nous aurions dû commencer par ça. ;)
Pour le regex, un petit conseil déjà : utilise plutôt IsMatch puisque tu n'as pas besoin des détails de la correspondance Ensuite, il se peut qu'en utilisant RegexOptions.CultureInvariant tu puisses aussi observer une différence. Tu peux aussi reconsidérer tes expressions régulières : certaines sont plus rapides que d'autres à exécuter. Enfin, wrapper la biblio PCRE peut être une bonne idée vu la lenteur du regex dotnet.

En effet, c'est par là qu'il fallait commencer. J'ai fais une petite fonction intermédiaire comme tu me l'as conseillé afin d'éviter de matcher la Regex le plus possible.

Bref, le résultat est sans appel : - d'une seconde.

C'est quand même étrange. On dirait que quand la regex ne trouve pas, elle met + de temps à s'en remettre que lorsqu'elle trouve... :P.

Je vais suivre tes conseils.
10/05/2012, 13h32
shurikeNzL

Citation:

Envoyé par meziantou

La première chose avant d'optimiser la Regex : As-tu réellement d'utiliser une regex ?
A quoi ressemble ce que tu dois parser ? Peux-tu nous donner un exemple ?

En faite, je dois pouvoir parser n'importe quel fichier texte, sachant qu'ils peuvent être tous formattés différements. Par conséquent, je ne peux pas écrire de Regex en dur.

Mon programme doit s'adapter à ce qu'il doit parser et générer lui même une Regex. Pour cela, l'utilisateur rentre un masque simplifié par exemple sous la forme [Date] [Heure] [[Thread]] - [Message].
Avec ce masque, je génère une RegEx qui va permettre la parse.

La RegEx s'est imposé à moi parce que d'une je ne connais pas beaucoup de chose programmatiquement parlant :roll:, et de deux parce que j'avais pas mal de problème si je ne les utilisais pas. C'était le plus simple.

Par exemple, ici, pour éviter d'utiliser trop le match du regex, auparavant, je teste si dans la ligne, tous les séparateurs d'attributs sont présents. S'ils le sont tous, alors je match avec la regex, car après tout, ils peuvent être dans le désordre, dans quel cas ce n'est pas un log !
Si un ou plusieurs séparateurs manquent à l'appel, alors je ne prend pas le temps de matcher, ça ne sert à rien, ça signifie soit que c'est la fin du log précédent, soit que c'est n'importe quoi :mouarf:.
10/05/2012, 13h46
DonQuiche

Le fait que ton regex mette plus de temps à s'exécuter dans les lignes sans correspondance témoigne d'un problème avec ta regex.
En effet, d'après ce que tu nous dit ta regex vérifie toujours le début de la chaîne. Dès lors, as-tu bien spécifié cela dans ton motif (un caractère permet de spécifier que le groupe doit être au début de la chaîne) ? Et les groupes sont-ils correctement définis comme successifs et non-optionnels ?

Au passage, quels sont ces séparateurs d'attributs ? Et utilises-tu StartsWith quand possible (on peut d'ailleurs spécifie un indice de départ), plutôt que Contains ?

Enfin, à mon avis, avec un regex correctement définie tu n'auras pas besoin de tests préliminaire.

PS : Pour ISMatch, c'est surtout qu'en théorie ça évite d'avoir :
* A rechercher toutes les captures, une seule suffisant.
* A extraire les sous-chaînes des résultats.
* A instancier les résultats.
En pratique, malheureusement, l'implémentation dotnet n'est pas si astucieuse.
10/05/2012, 14h10
shurikeNzL

Citation:

Envoyé par DonQuiche

Le fait que ton regex mette plus de temps à s'exécuter dans les lignes sans correspondance témoigne d'un problème avec ta regex.

C'est fortement possible étant donné le temps que ça m'a mis pour en trouver une qui fonctionne correctement en faisant ce que je souhaitais faire.

Citation:

Envoyé par DonQuiche

En effet, d'après ce que tu nous dit ta regex vérifie toujours le début de la chaîne. Dès lors, as-tu bien spécifié cela dans ton motif (un caractère permet de spécifier que le groupe doit être au début de la chaîne) ? Et les groupes sont-ils correctement définis comme successifs et non-optionnels ?

Je te donne un exemple, tu vas vite voir je pense que ma RegEx est pas belle.

Mettons que je veuille parser cette ligne :
[2012/03/09 00:00:24] Nooommm Information: 0 : messsssaaaaaaaaaaggeee
avec le masque :
[[Date] [Heure]] [Nom] [Level]: [Thread] : [Message]
Mon programme va générer la RegEx pourrie suivante :
[\[](.+?) (.+?)[\]] (.+?) (.+?)[\:] (.+?) [\:] (.+)?

Etrangement, quand je lui signale le caractère $ au début de la Regex, ca va pas. Même chose pour le ^ à la fin.

Citation:

Envoyé par DonQuiche

Au passage, quels sont ces séparateurs d'attributs ? Et utilises-tu StartsWith quand possible (on peut d'ailleurs spécifie un indice de départ), plutôt que Contains ?

Les séparateurs d'attributs, c'est ce qui délimite les attributs du masque. Par exemple [Nom] [[Prénom]] - [Age], ici les séparateurs sont " [" et "] - ".

Voir 40 message(s) de cette discussion en une page

Fuseau horaire GMT +2. Il est actuellement 17h58.