Discussion :

[sbadecoder]

Je recherche un algorithme très rapide pour mélanger un tableau pouvant être :

tab1 : array of Char;
ou
tab2 : array of AnsiChar;

[Charly910]

Bonjour,

je ne sais pas ce que tu entends par rapide, mais tu peux toujours essayer la méthode de Fisher-Yates :

Code :

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

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
procedure TF_Princ.Btn_MelangerClick(Sender: TObject);
// Mélange de Fisher-Yates
Const
  NbChar = 10 ;
Var
  i, j : Integer ;
  a    : Array [0..NbChar-1] of Char ;
  a1   : Array [0..NbChar-1] of Char ;
  s    : String ;
  s1   : String ;
  b    : Char ;
begin
  Randomize ;
  s1 := '' ;
  For i := 0 To NbChar-1 Do
    Begin
      a[i] := Chr(i+97) ;
      a1[i] := Chr(i+97) ;
      s1 := s1 + a1[i] ;
    End ;
  For i := NbChar-1 DownTo 1 Do
    Begin
      j := Random(i) ;
      b := a[i] ;
      a[i] := a [j] ;
      a[j] := b ;
    End ;
  s := '' ;
  For i := 0 To NbChar-1 Do
    Begin
      s := s + a[i] ;
    End ;
  ShowMessage(s1+ Chr(13)+s) ;
end;

Mais je pense que tu la connais ?

A+
Charly

[Charly910]

Bonjour,
j'ai fait un test avec mon PC qui n'est pas une bête de course, c'est très rapide :
0,05 s pour mélanger 1000 fois un tableau de 10000 Char

Je ne sais pas si il y a plus rapide ?

A+
Charly

[sbadecoder]

Oui, en effet c'est ce que j'utilise actuellement et c'est bien rapide, mais s'il y a mieux, je suis preneur.
Le plus souvent, je devrai mélanger un tableau de 300000 caractères environ 5000 fois.
(au maximum, 1 million de caractères environ 10000 fois).

Code :

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

1
2
 
For i := NbChar DownTo 1 Do

[Charly910]

Bonjour,

non, je pense que c'est bien :

Code :

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

For i := NbChar-1 DownTo 1 Do

avec

Code :

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

a  = Array [0..NbChar-1] of Char ;

A+
Charly

[sbadecoder]

justement, tu peux donc même écrire :

For i := NbChar DownTo 2 Do

Code :

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

1
2
3
4
5
6
7
8
 
For i := NbChar-1 DownTo 1 Do
...
j := Random(i);  # on évite i = j et donc mélange à chaque itération
 
For i := NbChar-1 DownTo 1 Do
...
j := random(i+1);  # on mélange sauf si i = j

[ShaiLeTroll]

Code :

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

1
2
For i := 0 To NbChar-1 Do
      s := s + a[i] ;

Sur une longue chaine cela peut être lent, en D7 cela l'aurait été affreusement, en DXE+ et D10+, avec FastMM inclut, c'est au moins 100 fois plus rapide mais si l'on connaît la longueur autant exploité cela !
Pourquoi ?
Avant cela aurait réalloué la mémoire auprès de l'OS à chaque concaténation
Maintenant cela réalloue la mémoire auprès de l'OS uniquement lorsque le bloc réservé est trop petit, sur les premiers blocs c'est genre de 8 en 8 ou 16 en 16 et + jusqu'à ~2Ko, voir les tables de FastMM pour plus de précision sur les SmallBlock puis cela passe en MediumBlock où le pas est d'allocation est presque de 3Ko.

Code :

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

1
2
3
 
SetLength(s, NbChar);
CopyMemory(@s[1], @a[0], NbChar);

StrPLCopy, StrPas, il y a un tas de façon d'écrire cela puisque le langage peut facilement traduire un Array of Char en String.
Et si l'on anticipe le Zéro Terminal dans le Buffer de travail, on peut encore utiliser d'autre astuce.

CopyMemory étant fourni par l'OS, cela peut copier des segments et des pages entière de mémoire, un algorithme optimisé selon la mémoire, le processeur ...

[ShaiLeTroll]

justement, tu peux donc même écrire :

Code :

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

1
2
 
For i := NbChar DownTo 2 Do

Il y a du vrai et du faux !
Dans l'idée je suppose que parfois il n'y ait pas de mélange en tombant avec un Random qui retourne l'indice en cours.
Il y a de l'idée mais un décalage de les bornes de -1
Ce la DOIT être For i := NbChar-1 DownTo 1 Do ... avec j := Random(i + 1); pour corriger le range 0 <= X < Range"
çà c'est une correction possible


NbChar - 1 comme départ, sinon cela irait chercher en dehors du tableau qui ne pas excéder [NbChar-1], mais comme Random(NbChar - 1) renvoie jamais NbChar - 1, il faut donc compenser par Random(i + 1)
1 comme fin car un Random(0 + 1) n'a aucun intéret puisque renvoie toujours 0, donc autant éviter la dernière itération inutile à Zéro mais comme l'on compense avec Random(i + 1), cela fait au pire un Random(1 + 1) avec un fin à 1

Après est-ce qu'il y a un intérêt à corriger cela ?
si parfois on peut renvoyer Range donc I, il y a une chance que I = J et donc qu'il n'y ait pas de mélange et comme d'habitude, ce sont des questions sur des problématiques sans aucun contexte, ... pourquoi souhaitez faire cela ?
Peut-être que nous pourrions vous proposer une solution plus large à un problème plus clairement exprimé.

Le code de Charly910 tel qu'il est mélangera toujours I <> J, ce qui semble parfait.

[sbadecoder]

Oui, en effet cela dépend si on souhaite toujours mélanger effectivement ou passer le mélange dans de rares cas (i=j).

C'est dans le cadre d'un jeu de type mots mêlés, je dois mélanger une grille existante pour en générer entre 1000 à 10000 autres.

[ShaiLeTroll]

Ah mais pour des mots mêlés, tu travailles à partir d'un dictionnaire de mot existant, j'aurais plutôt vue une technique de Path Finding ou de Graph que l'on appelle le backtracking, tu commences par choisir aléatoirement n mots sur la première colonne (avec ou sans cases noirs), chaque lettre du mot te permet de trouver aléatoirement dans le dictionnaire un mot commençant par la lettre pour remplir les lignes, tout en cherchant des mots qui coïncident sur les colonnes.

As tu étudié les notions de grilles parfaites et hyperparfaites ?
Une grille de mots croisés parfaite est une grille de mots croisés sans case noire ce qui donc pourrait convenir à une grille de mots mêlés

Perso, j'avais regardé ça pour le Défi Sudoku du Forum, cela dépassait clairement ma patience pour m'occuper de ce sujet mais le backtracking, c'est à mon avis ce que tu dois regarder, là tu sembles vouloir nous faire un BruteForce de grille qui sera très lent.