Discussion :

[shurikeNzL]

Bonjour à tous,

Je manipule en ce moment d'énorme liste d'objets (List(Of T)), en faisant plusieurs types d'opérations dessus, des insert, des remove et compagnie.

Malheureusement, je m'aperçois que plus ma liste grossis, plus c'est une horreur.

Je me demande juste si en travaillant avec des tableaux tout bêtement, ce n'est pas mieux question rapidité ?

Merci à vous.

[meziantou]

Le problème vient peut-être du conteneur. Pour en être sûr peux-tu détailler toutes les opérations que tu effectues sur la liste.
Par exemple : des insert toujours au début, toujours à la fin, n'importe où dans la liste.

Enorme ? ça fait quelle ordre de grandeur ?
horreur ? ca veut dire quoi exactement ?

remarque:
Une List<T> contient un tableau. Tu peux préciser la taille initiale de celui-ci dans le contructeur si tu connais la taille à l'avance.

[Pol63]

un redim preserve n'est pas imaginable pour les performances
les lists sont théoriquement plus lent que les tableaux dans certains cas, mais en pratique c'est infime

il faudrait plutot savoir ce que tu fais avec tes lists, car nous on a des dictionary avec des centaines de milliers d'objets et c'est plus que performant

[Slumpy]

Salut,

As tu regardé du coté des "SortedDictionary" ? Quand on comme a les utiliser, on ne peut plus s en passer lol

++

Slumpy

[meziantou]

As tu regardé du coté des "SortedDictionary" ? Quand on comme a les utiliser, on ne peut plus s en passer lol

Ca ne sert à rien de proposer des structures de données si on ne connait pas le besoin. Dans certains cas un Dictionnaire est très bien alors que dans d'autres une liste chainée sera mieux.
Attendons qu'il nous détaille son besoin et on pourra ensuite proposer la meilleure structure de données pour y répondre.

[Slumpy]

Ca ne sert à rien de proposer des structures de données si on ne connait pas le besoin. Dans certains cas un Dictionnaire est très bien alors que dans d'autres une liste chainée sera mieux.
Attendons qu'il nous détaille son besoin et on pourra ensuite proposer la meilleure structure de données pour y répondre.

C'est ton point de vu... Je trouve que ca lui permet d'aller se renseigner sur cette structure si il ne connait pas et de voir si cela peut l'aider. Si ce n'est pas le cas, ce lui sera peut etre utile une prochaine foi ...

[Pol63]

C'est ton point de vu... Je trouve que ca lui permet d'aller se renseigner sur cette structure si il ne connait pas et de voir si cela peut l'aider. Si ce n'est pas le cas, ce lui sera peut etre utile une prochaine foi ...

dans ce cas autant lui citer toutes les classes du framework, comme ca il sera sûr de trouver la classe qui lui convient

[meziantou]

dans ce cas autant lui citer toutes les classes du framework, comme ca il sera sûr de trouver la classe qui lui convient

Et encore... Toutes les structures de données ne sont pas implémentées : Les arbres bicolores, les B tree, les listes circulaires, etc

[Slumpy]

dans ce cas autant lui citer toutes les classes du framework, comme ca il sera sûr de trouver la classe qui lui convient

J'ai cité celle qui me parrait de par mon experience (ptet limitée je l accorde) repondre à ce genre de pb :

Je manipule en ce moment d'énorme liste d'objets (List(Of T)), en faisant plusieurs types d'opérations dessus, des insert, des remove et compagnie.

Malheureusement, je m'aperçois que plus ma liste grossis, plus c'est une horreur.

Si cela ne l aide pas pour ce cas, ca lui sera utile a un moment ou a un autre c sur.

TOut citer ne seriverais a rien puisque je suppose qu il n a pas 10 ans a perdre et surtout il n'irait surement rien voir ...

[meziantou]

Le SortedDictionnary est un arbre binaire trié équilibré => Pour proposer cette structure tu supposes que les éléments soient comparables entre eux, chose qui n'est pas précisée. De plus le parcourt (foreach) a-t-il besoin d'être ordonné ? Si oui, cette structure pourrait correspondre, tout comme une SortedList. Si non pourquoi ne pas utiliser plutôt un Dictionnary (table de hashage) qui est plus rapide et moins lourd en mémoire.
Peut être y a-t-il des problèmes de concurrences ?

Bref, il n'y a pas de solution générique : Tout dépend du besoin.

Tout citer ne servirait a rien puisque je suppose qu'il n'a pas 10 ans à perdre et surtout il n'irait surement rien voir...

Malheureusement le problème est bien là. Certains ne connaissent pas les différences entre les différentes structures de données car ils ne se sont jamais documentés ou personne ne leur à appri. Ils utilisent donc toujours la même structure même lorsqu'elle est totalement inadaptée, ce qui peut être catastrophique pour les performances.

[DonQuiche]

@shurikenZl
En somme, dis-nous ce que tu fais de ta liste (natures et fréquences des diverses modifications notamment) et nous te proposerons des solutions.

[shurikeNzL]

Bonjour, désolé pour le retard niveau réponse, j'ai été un peu pris ces derniers temps. Tout d'abord merci pour vos réponses, je vais tenter de vous éclairer sur ce que je fais.

Concrètement, je lis ligne par ligne des fichiers log, j'insert chacune de ces lignes (il peut donc il y'en avoir beaucoup) dans une liste.

Ensuite, pour chaque élément de la liste, je cherche une regex (pour reconnaître la forme du log), s'il la trouve, alors la ligne est un nouveau log, sinon c'est la suite du dernier log. Donc en fonction du résultat, je supprime des éléments pour les rajouter à la fin d'autres éléments. Bref le boxon.

Ensuite, sur chacun des éléments de la listes, je vais parser encore grâce à la regex afin d'obtenir enfin ma List(Of Log) et pouvoir faire des traitement dessus du genre recherche de texte etc...

Ca fait beaucoup de choses je sais, c'est certainement pas la meilleure façon de faire les choses... Mais je voulais savoir si rien qu'au niveau du choix de structure je ne m'étais pas déjà trompé ?

En général ces fichiers logs contiennent 2500 logs, ce qui reste peu finalement. J'ai bien peur que ce soit les Regex qui prennent le plus de temps.

Merci

[DonQuiche]

Bonjour.

Avant toute chose, utiliser un profiler comme EQATEC Profiler (dispose d'une version gratuite) serait judicieux pour savoir d'où vient le problème.

Cela étant dit, comment procèdes-tu exactement ?
* Tu fais une passe où tu crées un log par ligne (toutes les lignes d'un coup) puis une seconde passe où tu regroupes les logs ? Si oui alors il faut les stocker dans une nouvelle liste, pas les retirer de la première. Ça pourrait en effet être assez lent, le pire cas ayant une complexité en 2500 + 2499 + ... = 3.1M (n * (n-1) / 2).
* Tu n'as qu'une seule passe où tu te contentes, pour chaque nouvelle ligne trouvée, soit de l'ajouter à la fin soit de remplacer la dernière entrée par une fusion avec la nouvelle ? Alors il n'y a rien à changer, surtout avec seulement 2k5 entrées.

[shurikeNzL]

Cela étant dit, comment procèdes-tu exactement ?

1. Pour résumer, j'ai un fichier .log contenant des logs. Je lis ligne par ligne le fichier jusqu'au EOF. Chaque ligne (string) est ajouter à une liste de ligne (List(Of String)).

Je retourne cette liste à la couche du dessus.

2. Etant donné qu'un même log peut tenir sur plusieurs lignes de mon fichier.log, je suis obligé de vérifier que chaque ligne est bien un nouveau log en cherchant le motif d'un log grâce aux Regex. S'il est trouvé, alors il s'agit d'un nouveau log, et je l'ajoute à la liste. S'il n'est pas trouvé, alors j'ajoute la ligne incriminée à la suite de la dernière ligne ajoutée.

Tout cela me retourne une liste de de log (string) de type List(Of String).

3. Ensuite, il s'agit pour moi de convertir chaque ligne de log en log. Pour cela je cherche à nouveau le motif du log avec un regex avec matches, et à partir de ça je créér ma liste de log (List(Of Log)).

Je retourne ça pour affichage.

Ce qui me dérange, c'est que pour des fichiers de 2k5 lignes pour 2k5 logs, on va plus vite qu'un fichier de 100 lignes pour 39 log (différence de minimum 3 secondes en +). J'en ai déduis que ce qui posait problème était surement ma fonction pour reconstituer mes logs (2.)

La fonction en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
    '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
    '   Entrée : Chemin du fichier à parser (String), Regex (Regex).
    '   Sortie : Liste Recomposée (List (Of String))
    '   Description : Regroupe les morceaux d'un même log (un log peut tenir sur +sieurs lignes) afin 
    '   d'obtenir une ListeRecomposée de string représentant des logs. 
    '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
    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 dernierIndex As Integer = 0
        listeRecomposee.Add("")
 
        For Each ligne In listeDeString
             If Regex.Match(Ligne).Success  = True Then
                  listeRecomposee.Add(ligne)
                  dernierIndex = listeRecomposee.IndexOf(ligne)
             Else
                  Dim derniereLigne As String = listeRecomposee(dernierIndex)
                  listeRecomposee(dernierIndex) = derniereLigne + ligne
             End If
        Next
 
        listeRecomposee.RemoveAt(0)
 
        Return listeRecomposee
    End Function
#End Region

[DonQuiche]

Ok, donc c'est la première solution que j'avais proposée. L'usage de la liste ne pose aucun problème ici. On pourrait faire un poil mieux mais rien de significatif. Ton problème vient soit des regex, soit des concaténations.

Maintenant quelques autres questions pour mieux cerner le problème :
* Quel est l'objectif de durée pour le traitement du fichier ? 2k5 lignes ne devraient pas poser de problèmes.
* Combien de lignes par entrée en moyenne ? Je veux évaluer le nombre de concaténations.
* Le regex a t-il été prélablement compilé ?
* A t-on vraiment besoin d'un regex ; de simples StartsWith ou Contains ne pourraient-ils pas suffir ? A défaut pourrait-on inventer un test préalable qui permettrait la plupart du temps d'économiser le regex ?

[shurikeNzL]

Ok, donc c'est la première solution que j'avais proposée. L'usage de la liste ne pose aucun problème ici. On pourrait faire un poil mieux mais rien de significatif. Ton problème vient soit des regex, soit des concaténations.

Maintenant quelques autres questions pour mieux cerner le problème :
1. Quel est l'objectif de durée pour le traitement du fichier ? 2k5 lignes ne devraient pas poser de problèmes.
2. Combien de lignes par entrée en moyenne ? Je veux évaluer le nombre de concaténations.
3. Le regex a t-il été prélablement compilé ?
4. A t-on vraiment besoin d'un regex ; de simples StartsWith ou Contains ne pourraient-ils pas suffir ? A défaut pourrait-on inventer un test préalable qui permettrait la plupart du temps d'économiser le regex ?

1. J'essaie de faire un petit logiciel qui simplifie la vie pour lire des fichiers.log, donc je n'ai pas de grosses attentes concernant la vitesse. Mais au moins que ça justifie la création d'un logiciel de parse de fichier .log...

2. En moyenne, on peut en compter du 5000 lignes.

3. Je ne suis pas certain de comprendre ce que tu me demandes. En tout cas, cette Regex n'est pas écrite en dure dans le code, et est générée à partir d'un "masque" entré par l'utilisateur. De cette façon le logiciel peut parser à peu près tout.

4. Ben maintenant que tu le dis, peut-être qu'avec un simple Contains, ça irait aussi bien... Je vais tenter le coup. Tu penses que ça peut réduire un peu la durée ?

EDIT : Je pense que cela doit venir de la concaténation, car cette augmentation significative de temps ne se produit que lorsque le programme traite un fichier où des concaténations sont à faire.

Je fais un test sur :
- un fichier de 80.000 logs en 80.000 lignes. Résultat : 4 secondes.
- un fichier de 3028logs en environ 14803 lignes. Résultat : > 1minutes ! Autant dire que ça ne sert à rien...

[Er3van]

Un lien pour l'optimisation des performances des RegEx en .Net.

Voici un exemple d'expression régulière précompilée :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Program
{
    static Regex _wordRegex = new Regex(@"\W+", RegexOptions.Compiled);
 
    static void Main()
    {
	string s = "This is a simple /string/ for Regex.";
	string[] c = _wordRegex.Split(s);
	foreach (string m in c)
	{
	    Console.WriteLine(m);
	}
    }
}

Ici une RegEx compilée :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
class Program
{
    static void Main()
    {
	string s = "This is a simple /string/ for Regex.";
	Regex r = new Regex(@"\W+");
	string[] c = r.Split(s);
	foreach (string m in c)
	{
	    Console.WriteLine(m);
	}
    }
}

Et ici ce qu'il ne faut pas faire :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class Program
{
    static void Main()
    {
	string s = "This is a simple /string/ for Regex.";
	string[] c = Regex.Split(s, @"\W+");
	foreach (string m in c)
	{
	    Console.WriteLine(m);
	}
 
    }
}

[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.

Sinon, en vrac : oui, Contains a toutes les chances d'être plus rapide que regex. Si dois absolument utiliser un regex, crée-le en passant RegexOptions.Compiled au constructeur. Une assembly sera générée à la volée, ce qui prend environ une demi-seconde mais accélère pas mal les appels ultérieurs.

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é) :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

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
var builder = new StringBuilder(1000);
String logMonoLigne = null;
using(var e = listeDeString.GetEnumerator())
{
   while(true)
   {
       bool fin = !e.MoveNext();
       bool logComplet = fin || Regex.Match(e.Current);
 
       // On a complété un log, ajoutons-le
       if (logComplet)
       {
         // Plus d'une ligne ?
         if (builder.Length > 0) 
         {
             listRecomposee.Add(builder.ToString());
             builder.Length = 0;
         }
         // Une seule ligne
         else if (logMonoLigne != null)
         {
             listeRecomposee.Add(logMonoLigne);
         }
      }
 
      if (fin) break;
 
      // On démarre un nouveau log ?
      if (logComplet)
      {
          logMonoLigne  = e.Current;
      }
      // On continue un log ayant déjà une ou plusieurs lignes
      else 
      {  
          // Une seule ligne ?
          if (logMonoLigne != null)
          {
              builder.Append(logMonoLigne);
              logMonoLigne = null;
          }
          builder.Append(e.Current);
     }
}

@Er3van
Non, ce n'est pas une regex compilée. C'est une regex instanciée. Tu as montré statique versus instancié mais pour passer au compilé il faut utiliser le flag que j'ai précisé.

[meziantou]

Un petit article sur les différentes structures de données en Dotnet
http://www.meziantou.net/dotnet-choi...re-de-donnees/

Contains est plus rapide qu'une Regex même compilée.
Dès qu'une regex doit être utilisée plusieurs fois, il vaut mieux la compiler.
La concaténation de chaine de caractères n'est pas forcément des plus conseillée lorsqu'on ne connait pas le nombre de concaténations (dans une boucle par exemple). Le StringBuilder est plus adapté à cet usage.

[Er3van]

@Er3van
Non, ce n'est pas une regex compilée. C'est une regex instanciée. Tu as montré statique versus instancié mais pour passer au compilé il faut utiliser le flag que j'ai précisé.

Ca m'apprendra à faire un copier/coller rapide dans relire avant d'aller manger ! :p

Effectivement, seule la première version est compilée.

+1 pour le StringBuilder (et l'allergie au VB !)