C#: Comment faire un tableau de structs ?

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : C#: Comment faire un tableau de structs ?

ParadoX

Bonjour,

Question con a laquelle je ne trouve pas de reponse [:wam]
J'ai un struct tout con qui contient 2 integer, par ex.

J'aimerais creer un tableau contenant des ces structs, mais je ne parviens pas a trouver la syntaxe correcte.

Code :

public struct tableEntry
{
public int value;
public int[] candidates;
}

Code :

tableEntry[] myTable = new tableEntry[];

J'oublie quel détail ?

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

Publicité

flo850

moi je

tu es sur que tu ne devrai pas plutôt faire un tableau d'objet ? , avec une classe tableEntry ?

---------------

ParadoX

Classe, struct, pareil
par contre sur le net jai trouvé que les tableaux doivent etre typés et que du coup, c'est pas top.

Quelle est la meilleure facon (ou la plus simple, disons) d'implementer une matrice a 2 dimensions en C# ? Je vais passer de mon int[,] a un truc qui peut contenir des structs. Un Dictionary, peut etre ? :sweat:

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

flo850

moi je

http://www.danielsoper.com/program [...] aspx?ID=44

---------------

ParadoX

Donc ca marche avec une classe mais pas un struct [:transparency]

Merci :jap:

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

moi23372

class ou struc ce n'est pas pareil.
Leur allocation mémoire est totalement différente (pour l'un dans la HEAP, pour l'autre dans la STACK).
Les struct ne doivent idéalement pas dépasser 16 bytes.

Message cité 1 fois

---------------
quand un homme raisonne mal c'est qu'il n'a pas les données pour raisonner mieux (diderot)

flo850

moi je

c'est pas parceque c'est possible que c'est une bonne pratique

---------------

ParadoX

:jap:

A la base c'etait pour un programme de resolution de Sudoku en brute force. Ca fonctionne bien, maintenant j'aimerais l'optimiser: pour le sudoku qui est donné en "near worst case" sur wiki, mon prog met 4:52 minutes avec une config moyenne de nos jours (:o).

J'utilise un tableau a 2 dimensions contenant des cell, ma classe:

Code :

// Class cell
private class cell
{
public cell(int aRow, int aCol, int aValue)
{
row = aRow;
col = aCol;
value = aValue;
for (int i = 1; i <= 9; i++)
{
candidates.Add(i);
}
}
public int value;
public int row;
public int col;
public List<int> candidates = new List<int>();
}

Voici la methode de brute force:

Code :

// BruteForce
private bool bruteForce(cell acell)
{
// Call counter
counter++;
// Not finished
if (acell.row <= 8 && acell.col <= 8)
{
// For all candidates
for(int i = 0; i <= acell.candidates.Count - 1; i++)
{
// Candidate shortcurt
int aValue = acell.candidates[i];
// Check constraints
if (( checkRow(acell.row, aValue) == 0)
&& (checkColumn(acell.col, aValue) == 0)
&& (checkSquare(acell.row, acell.col, aValue) == 0))
{
myTable[acell.row, acell.col].value = aValue;
if (bruteForce(nextFreeCell()))
return true;
}
}
// Clear the field, wrong value
myTable[acell.row, acell.col].value = 0;
}
else
{
// End reached
return true;
}
return false;
}

Sachant que je ne peux pas ameliorer grand chose niveau logique pour la resolution du puzzle, peut-etre que je peux ameliorer qqch niveau programmation, n'etant pas un guru Y-a-t-il des astuces / idees pour reduire le temps de calcul en utilisant certaines methodes d'implementation ?

:jap:

Message édité par ParadoX le 15-12-2008 à 11:22:58

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

gilou

Modérateur
Modzilla

Tu es sur que c'est du "near worst case"?
Parce que j'ai écrit pour voir entre hier et ce matin un petit programme en C# (surtout pour voir si je perd pas la main dans ce langage que je pratique peu), qui ne fait pas de la brute force, mais applique juste les regles logiques de base (et qui ne saura pas resoudre une grille ou il faut faire des essais, comme une grille qui a plus d'une solution).
Or il résoud ta grille quasiment instantanément en 17 passes dans mon algo.

step 17:

| 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 |
| 02 | 04 | 06 | 01 | 07 | 03 | 09 | 08 | 05 |
| 03 | 05 | 01 | 09 | 02 | 08 | 07 | 04 | 06 |
| 01 | 02 | 08 | 05 | 03 | 07 | 06 | 09 | 04 |
| 06 | 03 | 04 | 08 | 09 | 02 | 01 | 05 | 07 |
| 07 | 09 | 05 | 04 | 06 | 01 | 08 | 03 | 02 |
| 05 | 01 | 09 | 02 | 08 | 06 | 04 | 07 | 03 |
| 04 | 07 | 02 | 03 | 01 | 09 | 05 | 06 | 08 |
| 08 | 06 | 03 | 07 | 04 | 05 | 02 | 01 | 09 |

A+,

Message cité 1 fois
Message édité par gilou le 17-12-2008 à 12:00:58

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

ixemul

Nan mais sans blague ! ⚡

On peut aussi passer par une liste:

Code :

List<tableEntry> myListe = new List<tableEntry>();
myListe.Add(new tableEntry());
myListe.Add(new tableEntry());
myListe.Add(new tableEntry());
tableEntry[] myTable = myListe.ToArray();

Après, l'idéal étant de n'utiliser que la liste si besoin, sans passer par le Array

---------------
VA APPRENDRE ET REVIENS QUAND TU SAIS, SINON ABSTIENT TOI C'EST UN GRAND CONSEIL QUE JE TE DONNE... TU ES INCOMPÉTENT ET C'EST UNE RÉALITÉ, TU N'AS RIEN A FAIRE ICI FAUT S'Y CONNAITRE ... -Jojo1998 - RIP - http://tinyurl.com/qc47ftk

Publicité

ParadoX

gilou a écrit :

Je peux voir ton algo ?
Sinon c'est un worst case justement pour un algo de bruteforce, sinon le terme de worstcase n'a pas de sens :jap:

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

gilou

Modérateur
Modzilla

Typiquement, mon algo ne marche que s'il existe une resolution directe.
Cette grille de départ (Télé Loisir Force 3 de cette semains ) le bloque au bout de 3 itérations (et résolution pour 11 cases)

| 01 | | | | | | | 05 | |
| | | | 01 | 05 | | 04 | | |
| | | | | | 04 | 06 | | |
| 06 | | | | | 09 | | 07 | |
| 04 | 02 | 09 | | | | | | |
| | 03 | | | 04 | | | 09 | |
| 02 | 05 | | 09 | 06 | | | 04 | 08 |
| | | | 03 | | | | | 05 |
| 07 | | 08 | | | 05 | | 03 | 09 |

A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

gilou

Modérateur
Modzilla

L'algo marche ainsi:
Une classe pour definir ce qu'est une case:

Code :

public class Square {
static int[] digits = {1, 2, 3, 4, 5, 6, 7, 8, 9};
public int? digit { get; set; }
List<int> possible_digits;
public Square() {
digit = null;
possible_digits = new List<int>(digits);
}
.................................

Une classe pour définir une grille

Code :

public class BoardSquare : Square {
public Square square;
public int row { get; set; }
public int col { get; set; }
public BoardSquare (int i, int j) {
row = i;
col = j;
}
..................................

Une classe pour définir une partie:

Code :

public class Game {
BoardSquare[,] board = new BoardSquare[9,9];
public List<BoardSquare> todo = new List<BoardSquare> ();
public Game() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i,j] = new BoardSquare(i,j);
}
}
}
..........................................

todo est la liste des cases dont les valeurs viennent d'être connues et qu'on va traiter.

On initialise la grille avec les valeurs d'une grille initiale, et on met chaque case de la grille initiale dans la liste todo.

Code :

public Game(int[,] iniset) : this() {
BoardSquare carre;
for (int i = 0; i < iniset.GetLength(0); i++) {
carre = board[iniset[i,0],iniset[i,1]];
carre.InitSquare(iniset[i,2]);
if (!todo.Contains(carre))
todo.Add(carre);
}
}

InitSquare(n) va mettre a n son champ digit et réduire a {n} sa liste possible_digits.
ou ta grille exemple est:

Code :

int[,] initial_set = {
{1,5,3}, {1,7,8}, {1,8,5},
{2,2,1}, {2,4,2},
{3,3,5}, {3,5,7},
{4,2,4}, {4,6,1},
{5,1,9},
{6,0,5}, {6,7,7}, {6,8,3},
{7,2,2}, {7,4,1},
{8,4,4}, {8,8,9}
};

Ensuite pour chaque element de la liste todo on va virer sa valeur des possible_digits des cases dans la même ligne, colonne et carré interne:

Code :

public void Reduce(BoardSquare carre) {
int val = (int) carre.digit;
int row = carre.row;
int col = carre.col;
for(int i = 0; i < 9; i++) {
board[row,i].RemoveDigit(val);
board[i,col].RemoveDigit(val);
}
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
board[((row/3)*3)+i,((col/3)*3)+j].RemoveDigit(val);
}
}
}

RemoveDigit fait gaffe a pas le virer sur la case de todo en cours elle même.

C'est appellé dans cet fonction, qui fait la resolution de la grille:

Code :

public void BasicReduce() {
foreach (BoardSquare carre in todo) {
Reduce(carre);
}
todo.Clear();
for(int n = 1; n <= 9; n++) {
FindUniqueInRow(n);
FindUniqueInCol(n);
FindUniqueInSqr(n);
}
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if (board[i,j].Solved()) {
if (!todo.Contains(board[i,j])) {
todo.Add(board[i,j]);
}
}
}
}
}

Donc apres avoir traité la liste todo, on la vide, et on regarde si notre traitement n'a pas créé de nouvelles cases qu'on va pouvoir resoudre (et donc mettre dans la liste todo):
Pour chaque chiffre, on regarde si il n'est pas présent qu'une seule fois dans les possible_digits dans une ligne, une colonne ou un carré interne, si oui, pour la seule case portant cette valeur, si elle n'a pas déja sa valeur dans digit (ie deja traitée), on met la valeur, et on reduit possible_digits a cette valeur. Si la case n'est pas déja dans la todo list, on la met.

Code :

public void FindUniqueInCol(int num) {
int count;
for(int i = 0; i < 9; i++) {
count = 0;
for(int j = 0; j < 9; j++) {
if (board[j,i].HasDigit(num)) {
count++;
}
}
if (count == 1) {
for(int j = 0; j < 9; j++) {
if (board[j,i].HasUnsetDigit(num)) {
board[j,i].SetDigit(num);
if (!todo.Contains(board[j,i])) {
todo.Add(board[j,i]);
}
}
}
}
}
}

FindUniqueInSqr est du même tonneau, mais plus coton a établir comme formule, il faut utiliser des modulo et la division entiere.

Enfin l'algo verifie qu'il n'y a pas des cases qui ont possible_digit a une seule valeur et digit pas positionné, sinon, on positionne digit et on ajoute la case dans la todo list.

On a une nouvelle liste todo, on réitere l'algo:

Code :

int k = 1;
while (game.todo.Count != 0 && k < 99) {
game.BasicReduce();
System.Console.WriteLine( "step {0}: ", k);
game.Print();
k++;
}

j'ai mis une valeur maximale a 99 tours, mais en fait, ca ne devrait pas dépasser 9*9=81 (ou 81+1) tours.

L'algo consiste pour une case connue, a réduire les possibilités dans sa ligne, colonne, carré interne, puis a regarder:
- si pour une valeur donnée, il n'y a pas qu'une seule possibilité par ligne, colonne ou carré interne
- si il n'y a pas des cases qui n'ont qu'une seule possibilité

Il y a peut être des améliorations a apporter a cet algo, mais il faut que j'aille lire du coté des techniques de résolution des grilles de Sudoku pour voir s'il y a d'autres techniques directes (ie ne faisant pas a un moment donné une hypothése "si la valeur en cette case est... alors, et voir si on arrive a une contradiction" ).

Il y a en particulier la technique de la hidden pair qu'il faudrait que je rajoute.
A+,

Message édité par gilou le 17-12-2008 à 17:22:08

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

ParadoX

:jap:

J'ai un truc similaire, avant de commencer le brute force je diminue le nombre de candidats pour chaque cellule. Par contre ta methode ne marche que pour les sudokus solvables par un humain, avec de la logique.

Quelques idees de methodes a implementer: http://www.mots-croises.ch/Manuels [...] hnique.htm (bonne chance pour certaines [:ddr555] )

Le brute force, lui, garantit de trouver une solution ('sil en existe une). Ce que j'ai fait, c'est une sorte de preprocessing avant le brute force qui permet d'optimiser (donc reduire) l'arbre de possibilités histoire de minimiser le temps du backtracking.

J'arrive a 4 minutes 52 pour la grille "near worst case" de brute force (69 175 317 appels recursifs !), et 2183 milisecondes en appliquant une astuce qui simplifie le tout (518 275 appels).

Il serait d'ailleurs interessant de trouver LA grille worst case, si c'est possible.

Ca devient tres vite tres mathematique, ces trucs :jap:

Message édité par ParadoX le 17-12-2008 à 18:53:41

---------------
Pier noir la mèr - La chanson par HFR Band - Topic TrueCrypt

gilou

Modérateur
Modzilla

Citation :

J'ai un truc similaire, avant de commencer le brute force je diminue le nombre de candidats pour chaque cellule. Par contre ta methode ne marche que pour les sudokus solvables par un humain, avec de la logique.

Je fais rarement des sudokus pour le plaisir, alors je ne connais pas les techniques logiques utilisées pour résoudre les grilles, je ne m'attendais pas a un truc parfait, c'etait juste pour voir si la logique simple permettait d'aller plus vite que la force brute.
A+,

Message cité 1 fois

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

MEI

|DarthPingoo(tm)|

gilou a écrit :

Citation :

Oui.
De ce que je me souviens, les meilleurs solveur de sudoku utilisent avant tout toutes les regles logiques avant de sortir le brute force en dernier recours.

---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |

FORUM HardWare.fr

Programmation

C#/.NET managed

C#: Comment faire un tableau de structs ?

Sujets relatifs
Tableau en C [niveau faible ^^]	[C#] Insérer une ligne dans tabeau Excel
[ASP.NET & C#] Pagination : remplacer les numéros par "..."	Création de ligne/ Tableau Type sous excel
C appel Mathématica???	[PERL] Passer un tableau en paramètre d'une fonction
probleme grammaire linéaire en C	[C] nombres binaires
Plus de sujets relatifs à : C#: Comment faire un tableau de structs ?

Page générée en 0.143 secondes