Imports System Imports System.Collections.Generic Imports System.Linq Imports System.Text.RegularExpressions Class MaCase #Region "Propriétés de classe" ''' <summary> ''' Valeur en X mini de la grille ''' </summary> Public Shared Property Xmin As Integer = 1 ''' <summary> ''' Valeur en X maxi de la grille ''' </summary> Public Shared Property Xmax As Integer = 10 ''' <summary> ''' Valeur en Y mini de la grille ''' </summary> Public Shared Property Ymin As Integer = 1 ''' <summary> ''' Valeur en Y maxi de la grille ''' </summary> Public Shared Property Ymax As Integer = 7 #End Region #Region "Méthode de classe" ''' <summary> ''' Crée une instance de Case à partir d'un texte, si le texte n'est pas compatible, retourne null ''' </summary> ''' <param name="Coordonnees"></param> ''' <returns></returns> Public Shared Function NouvelleCase(Coordonnees As String) As MaCase Dim m As Match = Regex.Match(Coordonnees, "^(?<x>\d+);(?<y>\d+)$") If m.Success Then 'si le texte correspond au modèle 'on extrait x et y Dim x As Integer = Convert.ToInt32(m.Groups("x").Value) Dim y As Integer = Convert.ToInt32(m.Groups("y").Value) 'On vérifie qu'il sont compatibles de la grille If x >= Xmin AndAlso x <= Xmax AndAlso y >= Ymin AndAlso y <= Ymax Then Return New MaCase(x, y) 'on retourne une instance de Case, grâce au constructeur privé avec paramètres End If End If 'sinon, on retourne null Return Nothing End Function #End Region #Region "Constructeurs" ''' <summary> ''' Constructeur nécessaire pour la création d'une instance voisine ''' </summary> Private Sub New() End Sub ''' <summary> ''' Constructeur nécessaire pour la création d'une instance depuis un string au format "x;y" ''' </summary> ''' <param name="LeX"></param> ''' <param name="LeY"></param> Private Sub New(LeX As Integer, LeY As Integer) X = LeX Y = LeY 'crée la liste des voisins non null de la case en cours, 'cette fois on se sert du constructeur sans paramètres pour ne pas calculer indéfiniment des voisins VoisinsPotentiels = ({New MaCase With {.X = LeX, .Y = LeY + 1}, New MaCase With {.X = LeX, .Y = LeY - 1}, New MaCase With {.X = LeX + 1, .Y = LeY}, New MaCase With {.X = LeX - 1, .Y = LeY}}).Where(Function(c) c IsNot Nothing).ToList() End Sub #End Region #Region "Propriétés d'instance" ''' <summary> ''' Abscisse de la case ''' </summary> Public Property X As Integer ''' <summary> ''' Ordonnées de la case ''' </summary> Public Property Y As Integer ''' <summary> ''' Liste des voisins possibles de la case ''' </summary> Public Property VoisinsPotentiels As List(Of MaCase) #End Region Public Overrides Function ToString() As String Return String.Format("{0};{1}", X, Y) End Function #Region "Opérateurs" ''' <summary> ''' Opérateur d'égalité ''' </summary> ''' <param name="Un"></param> ''' <param name="Autre"></param> ''' <returns></returns> Public Shared Operator =(ByVal Un As MaCase, ByVal Autre As MaCase) As Boolean 'si Un ou Autre vaut null If Object.ReferenceEquals(Un, Nothing) Then Return Object.ReferenceEquals(Autre, Nothing) ElseIf Object.ReferenceEquals(Autre, Nothing) Then Return False End If 'Sinon on compare les coordonnées Return Un.X = Autre.X AndAlso Un.Y = Autre.Y End Operator ''' <summary> ''' Opérateur d'inégalité ''' </summary> ''' <param name="Un"></param> ''' <param name="Autre"></param> ''' <returns></returns> Public Shared Operator <>(ByVal Un As MaCase, ByVal Autre As MaCase) As Boolean Return Not (Un = Autre) End Operator #End Region End Class
Private Sub TestMatousso() 'initialisation d'un arrayList pour l'exemple Dim caseNoires As New ArrayList() caseNoires.Add("6;2") caseNoires.Add("4;3") caseNoires.Add("5;3") caseNoires.Add("6;3") caseNoires.Add("5;4") caseNoires.Add("4;5") caseNoires.Add("5;5") caseNoires.Add("8;7") caseNoires.Add("9;7") 'si finalement on décidait que la grille a une colonne de plus MaCase.Xmax = 11 Dim lesCasesNoires As New List(Of MaCase)() 'Création de la liste de travail For Each s As String In caseNoires 'on ne peut pas faire de Linq sur un ArrayList, alors on fait un foreach Dim c As MaCase = MaCase.NouvelleCase(s) If c IsNot Nothing Then lesCasesNoires.Add(c) End If Next s Dim lesGroupes As New List(Of List(Of MaCase))() Do While lesCasesNoires.Count > 0 'la recherche ci dessous va enlever les cases au fur et à mesure et s'arreter quand il n'y en aura plus 'Création d'un nouveau groupe qui commence avec la première case, que l'on enlève de la liste d'origine Dim laCase As MaCase = lesCasesNoires(0) lesCasesNoires.Remove(lesCasesNoires(0)) Dim g As New List(Of MaCase)() From {laCase} lesGroupes.Add(g) Do Dim voisinsPotentiels As List(Of MaCase) = g.SelectMany(Function(c) c.VoisinsPotentiels).ToList() 'collection de tous les voisins possibles des cases déjà dans le groupe Dim voisins As List(Of MaCase) = ( From p In voisinsPotentiels, c In lesCasesNoires Where p = c Select c).ToList() 'collection des cases se trouvant dans les voisins potentiels et les cases noires If voisins.Count = 0 Then Exit Do 'il n'y a plus de voisins on sort de la création de ce groupe End If 'On ajoute les voisins au groupe g.AddRange(voisins) 'on les enlève de la liste de cases noires For Each c As MaCase In voisins lesCasesNoires.Remove(c) Next c If lesCasesNoires.Count = 0 Then Exit Do 's'il n'y a plus de case à classer, pas la peine de faire une boucle de plus End If 'on recommence la même recherche à partir du groupe nouvellement constitué Loop Loop End Sub
Je voudrais, dans toutes ces coordonnées, isoler et partager en plusieurs groupes toutes celles correspondant à des cases qui se touchent.
une case ne contient rien, elle est juste caractérisée par sa coordonnée.
Je me retrouve donc avec un arraylist contenant une série de coordonnées correspondant aux cases noires,
Et j'utilise un arraylist tout simplement parce que je ne connais pas à l'avance le nombre de cases noires au départOk, mais une list(of ), est plus simple et souple à utiliser, et c’est aussi une liste chaînée
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
12 juil. 2019 à 20:42
https://docs.microsoft.com/fr-fr/dotnet/api/system.collections.arraylist?view=netframework-4.8
Principalement l'encart bleu, qui explique que c'est une classe dépréciée.
Modifié le 13 juil. 2019 à 14:34
Juste un petit couac, il me faudra essayer d'optimiser plus car lorsque je fais grandir la grille et qu'un grand nombre de cases sont à tester, le programme ne suit plus et travaille indéfiniment (dans mon utilisation, ça peut aller jusqu'à plusieurs milliers de cases).
Merci encore, matousso
13 juil. 2019 à 15:26
Pour plusieurs milliers de cases (la grille, les cases noires, les 2?) , il faut revoir le code.
Mais pas que, en effet, j'ai codé en C# (le langage natif de .Net, mais aussi plus optimisé), ce code s'exécute environ 2 fois plus vite dans ce langage qu'en VB.Net.
Le rapport décroit probablement avec la quantité de données, mais fait est qu'un programme C# tourne plus vite qu'un VB.net. Le mode de compilation est important aussi Release est plus performant que Debug.
Pour le code, il faut se limiter à chercher les voisins en périphérie extérieure, actuellement, quand 6;3 est déjà triée car voisine de 6;2, elle va entrainer la recherche de 6;2, pour quelques dizaines, voire quelques centaines de cases, c'est pas bien grave, au-delà....
Du coup, le concept même d'agréger tous les voisins potentiels n'est plus très adapté, il faut revoir l'algorithme et pet-être l'existence même de la liste VoisinsPotentiels, voire le principe de "déplacer" les instances de la liste de départ vers
Aussi, je pars d'un ArrayList, pour en faire une List, tu pourrais gagner une boucle (de plusieurs milliers d'itérations) en construisant directement une liste.
J'ai vérifié la validité du format et des coordonnées, ça évite les bug, mais c'est chronophage.
J'ai forcé l'exécution immédiate de chaque requête Linq, ça évite de se préoccuper des effets (désirables ou non c'est selon le cas) de l'exécution différée, ça gagne aussi un peu de temps au débugage, mais au lieu d'une seule itération (une requête cache des boucles), il y a à 2.
Bref, je peux y retravailler, mais il me faudra connaitre une taille de grille habituelle et le nombre de cases noires associées.
Modifié le 13 juil. 2019 à 15:56
Pour la grille, dans mon utilisation, la largeur X = 453 et la hauteur Y = 453 également, ce qui fait environ 200k cases.
Pour le nombre de cases noires, c'est aléatoire, mais le nombre peut vite grimper, jusqu'à plusieurs milliers ( dans certains cas même aller jusqu'à 10k voire 20k, peut être même plus), augmentant aussi par ailleurs le nombres de groupes de cases noires possibles.
J'espère qu'il est possible de trouver un algorithme capable de tourner à cette échelle.
Merci :)
Modifié le 13 juil. 2019 à 23:11
Pour faire mes tests, j'ai généré un fichier txt de 453 lignes de 453 caractères, des ' ' et des 'X' , les 'X' représentant les cases noires, je ne prends pas en compte le temps de chargement dans les 4s mais juste le tri. Ainsi au fur et à mesure de mes optimisations, je testais toujours la même configuration. Pour info avec le code d'origine, j'ai stoppé à 1minute 30 et même pas 10% étaient faits.
Par contre, je ne passe pas par la forme "x;y", je suis parti du principe que pour générer cette forme tu avais d'abord généré x et y donc que tu peux avoir accès à ces valeurs et donc j'utilise un constructeur avec x et y en paramètre.
Peux tu me confirmer cette hypothèse?