Discussion :

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

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

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 !