Copier rapidement une plage de données [Résolu]

[Tito_28]

Bonjour à tous et à toutes !
Voilà mon problème :

Je travaille sur un Sub générique qui est chargé de copier une série d'éléments contigus d'un tableau dans un autre. Le but est de m'en servir pour implémenter des algorithmes de tri efficaces.

La signature de ce sub est :

Code :

1
2
3
4
Sub Copier(Of T)( _
Source as T(), IndexSource as Integer, _
Cible as T(), IndexCible as Integer, _
Longueur as Integer)

Source : tableau d'où proviennent les éléments ;
IndexSource : index du premier élément à copier ;
Cible : tableau où recopier les éléments ;
IndexCible : indice où recopier le premier élément ;
Longueur : nombre d'éléments à copier.

J'ai pensé à plusieurs méthodes :

• Effectuer une copie élément par élément, avec une boucle For ;
• Utiliser la méthode Array.Sort(), qui répond à mes attentes ;
• Effectuer une copie grâce à la classe System.Runtime.InteropServices.Marshal.

J'ai testé les deux premières méthodes, avec une rapidité d'exécution supérieure pour la deuxième.

Ma priorité est la rapidité (et pas la simplicité du code). De plus, ce Sub étant destiné à être appelé de très nombreuses fois, un gain de temps minime serait déjà le bienvenu ! Je pense donc que la troisième méthode serait encore meilleure.

Mais la méthode Copy() de la classe Marshal permet de copier un tableau à l'adresse spécifiée par un pointeur, ou les informations trouvées à l'adresse d'un pointeur dans un tableau, mais pas un tableau dans un autre tableau.

Quelqu'un a-t-il une idée me permettant d'utiliser, dans ma situation, les performances de la fonction Copy() ?

Merci à vous !

[Pol63]

à la description de ce que tu dis au début, je ne vois le rapport avec le sort vu que tu parles d'une copie en bloc
et il y a une méthode sur le framework 3 ou 3.5 qui fait ca (array.copy(source, cible, débutsource, débutcible, longueur))

sinon tu dois pouvoir tenter de réinventer ca en multithreading ...

[Tito_28]

Pol63, merci pour ta réponse !

Comme je l'indique dans mon message, j'utilise la copie en bloc à l'intérieur d'une routine de tri, et Array.Copy(), que j'ai essayée, ne paraît pas encore assez efficace dans mon cas. D'où la recherche d'une méthode plus rapide...

En revanche, l'idée du multi-thread me semble excellente, car parfaitement adaptée à mon algorithme de tri. J'essaie ça tout de suite et je reviens !

[Pol63]

l'algo de tri, qui doit etre celui implémenté dans .sort est connu
en réinventer un en multithreading et plus performant n'est pas forcément aisé je pense
je partirais sur un découpage du tableau en x parties, x étant le nombre de core
un sort par petit morceau
et au final on recréer un tableau en lisant les 1ères valeurs de chaque tableau pour trouver la plus petite et on dépile ce tableau (ou on retient l'index)

[Tito_28]

Pol63, je tiens compte de tes diverses propositions ! Je reviendrai pour rendre compte des solutions retenues au final.

Merci !

[Tito_28]

Je reviens pour confirmer qu'utiliser le multi-threading pour effectuer un tri est une excellente idée ! Pour ma part j'obtiens une routine générique qui fait le même travail que Array.Sort(), asymptotiquement en quatre fois moins de temps !!! Donc tout cela en valait largement la peine.

Précision : pour moi, inutile de découper mon tableau en paquets avant d'appliquer mon algo à chaque paquet, puisque mon algorithme de tri consiste justement en un diviser pour régner. Donc dans ma fonction de tri récursive, je passe en argument la profondeur de récursion actuelle (1 pour l'appel sur le tableau entier, 2 pour les deux moitiés, 3 pour les quatre quarts, etc.) Ensuite, si la profondeur est petite ( <= 3 pour une machine ayant 2^3 processeurs) je lance le diviser pour régner sur deux Threads, sinon sur le même. On a alors une utilisation optimale des processeurs (si leur nombre est une puissance de 2, ce qui est toujours le cas j'imagine ??)

Grand merci à Pol63 !

[Kropernic]

Et on peut avoir le code de cette sub si géniale ? ^^

[Tito_28]

Avec plaisir griftou !

Précisions pour le code qui va suivre :

• Pour obtenir une classe générique, il faut spécifier une fonction capable de dire, entre deux éléments du tableau, lequel est le plus grand. Si on veut obtenir des performances encore meilleures avec un type en particulier, il suffit donc d'oublier la généricité et de remplacer l'appel à la fonction de comparaison par un bête signe "inférieur ou égal".
• Le miraculeux gain de performance (de 1 à 4 dans mon cas) est dépendant du nombre de processeurs de l'ordi. Pour un processeur unique, les performances sont très légèrement inférieures à Array.Sort() (je n'arrive pas à optimiser plus).
• Pas besoin de modifier le code selon le nombre de processeurs, car mon code fait un appel à Environment.ProcessorCount(). Donc en bref, le code est entièrement utilisable tel quel, et s'utilise exactement comme Array.Sort().

Voici le code (à insérer en entier dans un fichier) :

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
Option Strict On
 
Public Class Tri(Of T)
    Private Shared Tbl As T()
    Private Shared Cop As T()
    Private Shared Comp As Comparison(Of T)
    Private Shared ProfMax% = NbDeZéros(Environment.ProcessorCount)
 
    'Le Sub qui est appelé pour trier un tableau
    Public Shared Sub TrierSurPlace(ByVal Tbl As T(), ByVal Fin%, ByVal Comp As Comparison(Of T))
 
        Tri(Of T).Tbl = Tbl
        ReDim Cop(Fin)
        Tri(Of T).Comp = Comp
 
        Trier(0, Fin, 1)
 
    End Sub
 
    Private Shared Sub Trier(ByVal Ind1%, ByVal Ind2%, ByVal Profondeur%)
 
        'Trouver l'index intermédiaire
        Dim IndEntre1% = (Ind1 + Ind2) >> 1
        Dim IndEntre2% = 1 + IndEntre1
 
        'Trier les deux plages
        If Profondeur <= ProfMax Then
            Dim Tr As New Thread(Ind1, IndEntre1, Profondeur)
            If IndEntre2 < Ind2 Then Trier(IndEntre2, Ind2, Profondeur + 1)
            Do While Tr.IsAlive
            Loop
        Else
            If Ind1 < IndEntre1 Then Trier(Ind1, IndEntre1, Profondeur + 1)
            If IndEntre2 < Ind2 Then Trier(IndEntre2, Ind2, Profondeur + 1)
        End If
 
        'Réunir les deux plages triées dans Cop
        Dim I1% = Ind1
        Dim I2% = IndEntre2
        Dim Cpt% = Ind1
        Dim Tbl_I1 As T
        Dim Tbl_I2 As T
        Do Until I1 > IndEntre1 OrElse I2 > Ind2
            Tbl_I1 = Tbl(I1)
            Tbl_I2 = Tbl(I2)
            If Comp(Tbl_I1, Tbl_I2) < 0 Then
                'Insérer Tbl(I1) en Cop(Cpt)
                Cop(Cpt) = Tbl_I1
                Cpt += 1 : I1 += 1
            Else
                'Insérer Tbl(I2) en Cop(Cpt)
                Cop(Cpt) = Tbl_I2
                Cpt += 1 : I2 += 1
            End If
        Loop
        If I2 > Ind2 Then
            Do Until I1 > IndEntre1
                'Insérer Tbl(I1) en Cop(Cpt)
                Cop(Cpt) = Tbl(I1)
                Cpt += 1 : I1 += 1
            Loop
            'Recopie... Cop -> Tbl ; à partir de Ind1 ; taille Ind2 - Ind1 + 1
            Array.Copy(Cop, Ind1, Tbl, Ind1, Ind2 - Ind1 + 1)
        Else
            'Recopie... Cop -> Tbl ; à partir de Ind1 ; taille Cpt - Ind1
            Array.Copy(Cop, Ind1, Tbl, Ind1, Cpt - Ind1)
        End If
 
    End Sub
 
    Private Shared Function NbDeZéros%(ByVal I%)
 
        If I = 0 Then Return 0
 
        Dim Rép%
 
        Do Until I = 1
            I >>= 1
            Rép += 1
        Loop
 
        Return Rép
 
    End Function
 
    Private Structure Thread
        Private Ind1%
        Private IndEntre1%
        Private Profondeur%
        Private Tr As Threading.Thread
 
        Public Sub New(ByVal Ind1%, ByVal IndEntre1%, ByVal Profondeur%)
 
            Me.Ind1 = Ind1
            Me.IndEntre1 = IndEntre1
            Me.Profondeur = Profondeur
 
            Me.Tr = New Threading.Thread(AddressOf Faire)
            Tr.Start()
 
        End Sub
 
        Private Sub Faire()
 
            If Ind1 < IndEntre1 Then Trier(Ind1, IndEntre1, Profondeur + 1)
 
        End Sub
 
        Public ReadOnly Property IsAlive As Boolean
            Get
 
                Return Tr.IsAlive
 
            End Get
        End Property
 
    End Structure
 
End Class

Maintenant voici un exemple d'utilisation :

Code :

1
2
Dim Tableau() as Double = New Double () {15.0, 8.0, 42.0, 16.0, 4.0, 23.0}
Tri(Of Double).TrierSurPlace(Tableau, Tableau.Length - 1, AddressOf comp_Double)

Après exécution le tableau Tableau() vaudra alors {4.0, 8.0, 15.0, 16.0, 23.0, 42.0} (il s'agit d'un tri "sur place").

Il faut avoir déclaré préalablement :

Code :

1
2
3
4
5
6
7
8
Public Function comp_Double(ByVal D1 As Double, ByVal D2 As Double) As Integer
 
        If D1 < D2 Then : Return -1
        ElseIf D1 > D2 Then : Return 1
        Else : Return 0
        End If
 
End Function

Voilà pour les curieux ! Si ça ne marche pas dites-le...
A+

[Kropernic]

Merci.

Je garde cela sous le coude pour le cas où

[Tito_28]

Petite précision... Chez moi mon algorithme est meilleur que Array.Sort() à partir de 80 000 éléments. Pour les tableaux plus petits, il est mauvais. A réserver donc aux grands tableaux...

On peut modifier le Sub TrierSurPlace pour tester si la taille est inférieure ou supérieure à 80 000, et selon utiliser Array.Sort() ou le tri perso. Comme il n'est appelé qu'une fois par tri, pas de perte de performance donc tout bénef pour un tableau quelconque !