FASTCOLLECTION ==> UNE COLLECTION 10000 FOIS PLUS RAPIDE EN LECTURE PAR INDEX QUE CELLE DE VB collection, fast, optimisation, liste, chaine, Source N°42861

Information sur la source

Catégorie :Optimisation du code Classé sous : collection, fast, optimisation, liste, chaine Niveau : Expert Date de création : 27/05/2007 Date de mise à jour : 28/05/2007 21:31:55 Vu / téléchargé: 6 310 / 670

Auteur : violent_ken

Site perso

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :

10,00 / 10

1
2
3
4
5
6
7
8
9
10

Commentaire sur cette source (22)

Ajouter un commentaire et/ou une note

Description

Ben voilà, comme la Collection de VB est basée sur un liste chainée, il faut parcourir toute la Collection pour arriver au dernier Item (quand on lit par l'Index, car c'est différent avec la Key à cause de la présence d'une HashTable, et là bien sur c'est beaucoup plus rapide qu'avec l'Index).

Alors quand il s'agit de lire plusieurs Items à la fin de la collection (comme c'est le cas pour l'espèce de ListView que je code).... c'est INCROYABLEMENT LENT !!
(cf http://www.vbfrance.com/infomsg_ACCES-LENT-COLLECTION-POUR-ITEMS-FIN_949183.aspx#11 )

J'avais essayé les listes toutes simples, le problème de lecture des Items de fin était réglé, mais quand je voulais insérer un Item au milieu de la liste il fallait tout décaler avec des For et c'était encore plus lent....

Et là : j'ai pensé à CopyMemory ;)

NOTE : Dans le zip est présent clsReyCollection.cls. Il s'agit de la même classe que la mienne (clsFastCollection), mais revue et optimisée par Renfield. C'est donc cette dernière qu'il faut utiliser pour les meilleures performances ! D'ailleurs c'est également elle la mieux commentée.
Je laisse néanmoins clsFastCollection, un peu mieux que lors de la dernière MAJ, même si elle est moins rapide que celle de Renfield.

Le réusultat est plutôt impressionant en lecture par index :

Bench (P4 3Ghz Compilé Natif avec optimisations) :

- Ajout de 10000 items à la suite :         Collection (VB) : 47 ms    clsFastCollection : 47 ms
- Ajout de 1000 items au début :         Collection (VB) : 0 ms    clsFastCollection : 46 ms
- Suppression des 1000 derniers Items :         Collection (VB) : 31 ms    clsFastCollection : 44 ms
- Clear :         Collection (VB) : 94 ms  (Set=Nothing + Set=New)   clsFastCollection : 78 ms (Clear)

Jusque là rien d'extraordinaire, la collection de VB est d'ailleurs largement plus rapide pour l'insertion d'éléments, mais voilà l'intérêt de ma source :

- Lecture des 1000 derniers Items sur 30000 Items :      Collection (VB) : 3204 ms    clsFastCollection : 0 ms

AHAHA, je suis infiniment plus rapide que la collection de VB ;) Donc je n'avais pas menti dans le titre ^^

Evidemment, si vous n'utilisez que 200 items, gardez la Collection de VB. Mais si vous manipulez 50000 objets (par leur index !), adieu la Collection de VB ;)

Source

'ULTRA COMMENTE (chaque ligne de la classe est commentée)
'clsItem ==> exemple d'objet
'clsFastCollection ==> la classe rapide que j'ai codée
'clsReyCollection ==> la même, corrigée, optimisée et commentée par Renfield ==> c'est elle la meilleure des deux.

'ULTRA COMMENTE (chaque ligne de la classe est commentée)

'clsItem ==> exemple d'objet
'clsFastCollection ==> la classe rapide que j'ai codée
'clsReyCollection ==> la même, corrigée, optimisée et commentée par Renfield ==> c'est elle la meilleure des deux.

Conclusion

C'est du level 3 parce que je manipule des pointeurs.

Si vous avez des conseils, des critiques, des remarques...etc, ne vous gênez pas ;)
Notez et commentez SVP !

Evidemment MERCI encore à Renfield ^^

Note : le Bench varie beaucoup d'une fois à l'autre, donc à essayer plusieurs fois !
Note2 : la collection VB n'est pas capable de gérer 100000 objets, d'où le On Error Resume Next

@+

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

clsFastCollection.cls 7 885 octets
clsItem.cls 479 octets
clsReyCollection.cls 5 952 octets
Form1.frm 12 911 octets
MSSCCPRJ.SCC192 octets
Projet1.vbp 812 octets
Projet1.vbw 160 octets

Télécharger le zip

Historique

27 mai 2007 15:27:35 :: Avait oublié une ligne de code
28 mai 2007 21:31:56 :: Optimisé ma classe + ajouté celle de Renfield, encore meilleure.

Sources du même auteur

Toutes les sources de violent_ken

Sources de la même categorie

Toutes les sources de la catégorie Optimisation du code

Sources en rapport avec celle ci

Commentaires

Commentaire de violent_ken le 27/05/2007 15:16:15

Note : j'ai défini une constante arbitraire (Private Const USTEP As Long = 1000).

Si vous augmentez sa valeur, ce sera encore plus rapide mais vous perdrez peut être quelques octets en mémoire.

A l'inverse, si vous diminuez, ce sera plus lent mais gaspillera moins de mémoire.

@+
Commentaire de EBArtSoft le 27/05/2007 18:53:08 administrateur CS

Ouai en fait c'est un tableau d'objet ! lol
Par ce que justemlent ce qui est interresant dans une collection c'est de pouvoir utiliser des clefs de type string car sinon autant utiliser un tableau. Mais c'est bien de l'avoir montré et codé.

:p
Commentaire de violent_ken le 27/05/2007 18:57:11

Roohh, tu n'as pas compris l'utilité du code ;)

L'intérêt par rapport à un tableau, c'est de pouvoir insérer des Items au milieu sans avoir à redimensionner... autrement dit c'est pratiquement instantané (comme pour la Collection de VB), contrairement au tableau.
De même pour la suppression d'un Item au milieu ;)

Et cet intrêt est très important (c'est pour çà que j'ai codé çà)

@+
Commentaire de EBArtSoft le 27/05/2007 20:42:08 administrateur CS

Ouai ça depend comment tu gere ton tableau, si tu fais ça comme un cake c'est clair autant telecharger ta source. En meme temps ya pas que des cakes dans la communauté vb

:p
Commentaire de BruNews le 27/05/2007 20:49:30 administrateur CS

EB, ce sera avec un bon café serré pour moi.
Commentaire de EBArtSoft le 27/05/2007 21:59:23 administrateur CS

BruNews> Hahah, on ce crois a l'abri derriere une source en vb sans defence et paf ! V'la le Bruno tapi dans l'ombre mais guetant le programmeur en etat de faiblesse pour lui sortir la petite phrase assassine "qui va bon" !

Bon je te ramene bidon d'arabica de huit litre ça te fera l'apres-midi :p
Commentaire de violent_ken le 27/05/2007 22:17:23

lol ;)
@+
Commentaire de Renfield le 28/05/2007 05:56:16 administrateur CS

lu le code, y'a des incohérences...

quand tu remove un item, tu resize ton tableau qq soit ton UpStep.

amélioration possible : tu pourrais accelerer la chose en stockant la taille du tableau ...  ainsi, moins de UBound

implementes _NewEnum

Byval varptr(Obj) => Obj     (me semble)

Pas compris ce que tu fais avec ton refCount dans le Add... (le role de tmp, quoi... Explique ta demarche en commentaire dans le code
Commentaire de Renfield le 28/05/2007 06:37:31 administrateur CS

j'aime pas trop le fait que les index commencent à 1

J'ai ajouté deux trois trucs, qui optimisent un peu la chose :
- lSize ce qui m'evite des Ubound
- lSteps qui me permet de faire le redim en cas de suppression, sans faire de Mod ni de division

VB  / TOI  / MOI
Ajouter 10000 a la fin :
78ms  / 78 ms / 47 ms

Ajouter 1000 au début :
15ms / 109ms / 78ms

Supprimer 1000 premiers:
47ms / 78ms / 46ms

Clear:
328ms / 546ms / 62ms

Mon code n'est pas parfait, loin de là, mais montre la mise en oeuvre d'optimisations simples... et efficaces.

chose amusante, j'ajoute un element, et je ne peux pas le supprimer...
    If Index > 0 And Index < lCount Then
    (lCount vaut 1, ici)... a moins de mettre un Index décimal...

après relecture, j'ai saisi le role de tmp dans le Add... il sert à piquer une reference vers ton objet
j'ai testé (en mettant un BP dans le Class_Terminate de tes items), le RefCount est correct, et bien géré
Commentaire de Renfield le 28/05/2007 07:18:44 administrateur CS

pour le Tmp, pour que ce soit plus clair (je voyais pas pourquoi tu modifies Obj...)

fais plutot :

Set Tmp = Obj
lPtr(Index...) = ObjPtr(Tmp)
CopyMemory Tmp, 0,4

plus clair, non ?

ton add 1000 au début en boucle ne fais RIEN du tout, si lancé au démarrage de l'appli (si la collection est vide...)
si on ajoute le test adequat, l'insertion est nettement plus rapide.

de même, gaffe au fait que ta suppression se fait dans l'ordre croissant... supprimant les 1000 premiers items, tu supprime en fait les elements :
1, 3, 5, 7, 9, ..... vu que tu décale ton tableau...
Commentaire de violent_ken le 28/05/2007 12:57:27

Salut, merci pour les commentaires. Alors :

- "tu pourrais accelerer la chose en stockant la taille du tableau ... ainsi, moins de UBound" ==> oui, pourquoi pas
- "Byval varptr(Obj) => Obj" ==> bah, c'est équivalent, non ?
- pour l'implémentation du For Each, je le mettrais également
- pour l'histoire du tmp, c'est pas très clair en effet, je mettrais à jour
- "ton add 1000 au début" ==> oui je sais
- "supprimant les 1000 premiers items, tu supprime en fait les elements :" ==> ah ok, problème important, j'avais pas vu.

Merci, @+
Commentaire de apxa le 28/05/2007 20:18:12

iop all,
Voila une source et des remarques très interressantes.
Je pense en effet qu'en travaillant un peu sur les API de windows on pourrait vraiement faire quelque chose qui serait beaucoup plus performant que le composant collection.

Hava Fun ;)
Commentaire de violent_ken le 28/05/2007 20:32:09

Yep, d'autant que Renfield m'a proposé une version optimisée et très commentée que je releaserais avec la mienne (que je vais également optimiser suivant ses conseils).

Par contre il va manquer un truc : l'implémentation du For Each. Après m'être pas mal renseigné dessus, je dois dire que c'est pas encore de mon niveau -__-
Implémenter IEnumVARIANT etc..., n'est pas chose aisée.
ShareVB l'explique ici : http://www.vbfrance.com/tutorial.aspx?ID=188 mais je dois dire que quand il s'agit d'une collection perso (pas à base de Collection de VB), c'est bien tendu...
"pour l'implémentation du For Each, je le mettrais également" ==> ERF, je pensais pas que c'était si chaud.

Je pourrais bien sur faire un bête copier/coller d'une solution fonctionnelle, mais c'est pas le but non plus !

Donc MAJ pour les optimisations, mais le For Each pas pour tout de suite, je le ferais quand je maitriserai suffisement.

@+
Commentaire de EBArtSoft le 28/05/2007 20:33:36 administrateur CS

>> "Byval varptr(Obj) => Obj" ==> bah, c'est équivalent, non ?

Non ! ce n'est pas equivalent car VarPtr est une fonction de msvbvmxx.dll par consequent tu fais un appel de plus.
Commentaire de violent_ken le 28/05/2007 21:40:12

Yep, je l'ai corrigé ;)

MAJ : j'ai modifié ma source en prenant en compte les conseils de Renfield, et j'ai également ajouté littéralement la classe qu'il a codée ==> elle est plus rapide et mieux commentée.

J'ai pas trop trop le temps ce soir (révisions interro p:), mais 1 amélioration à faire :
- l'implémentation de For Each (chaud pour mon niveau, mais bon)

Note : j'ai ajouté Erase comme le disait PCPT et j'ai par contre laissé Redim lPtr(n) et pas (1 to n), même si l'item 0 est pas utilisé : le (n) est très légèrement plus rapide que le 1 to n, et je rajouterais par la suite la possibilité d'utiliser l'item 0.

@+
Commentaire de Renfield le 29/05/2007 09:06:46 administrateur CS

Pas sur que la FastCollection MAJ soit bien plus lente que ce que je t'ai fourni...
j'y ai vu les améliorations que je t'avais soufflées...

bonne assimilation, j'espère que tu y repensera pour tes prochains codes ...
limiter les accès aux tableaux, les redim, les calculs inutiles...

++
Commentaire de violent_ken le 29/05/2007 13:24:23

Yep, je retiens l'histoire des appels aux tableau à éviter (Ubound, redim...), idem que les procédures inutiles quand appelées une seule fois ^^
Par contre ta collection est encore bien plus rapide que la mienne pour le Clear (même si j'ai repris ta méthode avec le Step 4 ? bizarre.)

Au passage j'ai remarqué que la Collection de VB était limitée en nombre d'objets (ne gère pas le 'ajouter 100000 au début').

Merci encore, @+
Commentaire de Renfield le 29/05/2007 13:31:15 administrateur CS

Pour le "ajouter 10000 au début", ca coince avec la VbCollection parce que tu dit d'ajouter l'element après l'element 1... et que la liste est vide => CRASH
Commentaire de violent_ken le 29/05/2007 19:13:38

Yep c'est vrai, j'ai mis un On Error... pour éviter le bug : la Collection VB gère pas les Index incohérents ;)

En fait je ne l'ai pas précisé, mais le mieux pour tester les diverses classes et leur vitesse est d'appuyer sur les boutons dans l'ordre de haut vers le bas.

@+
Commentaire de waluigii le 01/06/2007 02:27:02

Slt,

Formidable ce code...tu mérites une note de 10/10!
Continue le beau travail.=)

@+ Bon succès à toutes et à tous.
Commentaire de violent_ken le 01/06/2007 12:20:28

Merci ;)
@+
Commentaire de BLUEBIBUBBLE le 02/06/2007 19:27:48

Slt,
Bon travail tous, on pourrais obtenir un p'tit peu plus de précision sur le timing lors des tests en attendent la fin de la ms en cours avant chaque test, un truc du genre:

    t2 = WaitTickCount
    For x = 1 To 10000
        ...
    Next x
    t2 = GetTickCount - t2

    t3 = WaitTickCount
    For x = 1 To 100000
        ...
    Next x
    t3 = GetTickCount - t3

Function WaitTickCount() As Long
    Dim T As Long
    T = GetTickCount
    Do: Loop While T = GetTickCount
    WaitTickCount = GetTickCount
End Function

Ajouter un commentaire

Discussions en rapport avec ce code source

Besoin d'aide sous VBA pour zone de liste !!! par jcconi

Nombres premiers (optimisation) par Julien39

affecter une chaine à une liste par mqsi

Optimisation par guigui28

Création d'un controle type liste par Kevin.Ory

Liste déroulante par sgd1

chaine de caractere et label dynamique!!!!!!!!!! par mouradj2006

extrare chaine par kelm_by

MSXML et String par run_nahu

Sérialiser un collection par fiko81