Discussion :

[retwas]

Bonjour,

Sur une application de test il est possible que je doive stocker de 2 à plusieurs milliards d'enregistrements.

Dans ma procédure j'ai la variable suivante :

Code :

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

ListChemins : TList<TPoint>;

Au fur et à mesure j'ajoute des points, au bout d'un moment j'obtiens un "Mémoire insuffisante" à environ 50 millions d'items.

J'ai une boucle ou pour passer à l'item suivant il faut respecter une conditions sinon je recommence jusqu’à l'atteindre. Avant la boucle j'ajoute un point de coordonnées X=0 et Y=0.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
procedure TForm2.btnCalculerClick(Sender: TObject);
var
   i          : integer;
   iTermine   : integer;
   ListChemins: TList<TPoint>;
   iWidth     : integer;
begin
   iWidth      := seEdit.Value;
   ListChemins := TList<TPoint>.Create;
   iTermine    := 0;
   i           := 0;
   try
      ListChemins.Add(TPoint.Create(0, 0));
 
      while i <= ListChemins.Count - 1 do
      begin
         if (ListChemins[i].X < iWidth) and (ListChemins[i].Y < iWidth) then
         begin
            ListChemins.Add(TPoint.Create(ListChemins[i].X, ListChemins[i].Y + 1));
            ListChemins[i] := TPoint.Create(ListChemins[i].X + 1, ListChemins[i].Y);
            Dec(i);
         end else
         if ListChemins[i].X < iWidth then
         begin
            ListChemins[i] := TPoint.Create(ListChemins[i].X + 1, ListChemins[i].Y);
            Dec(i);
         end else
         if ListChemins[i].Y < iWidth then
         begin
            ListChemins[i] := TPoint.Create(ListChemins[i].X, ListChemins[i].Y + 1);
            Dec(i);
         end else
         begin
            Inc(iTermine);
         end;
 
         Inc(i);
      end;
 
      lbTotal.Caption := iTermine.ToString;
   finally
      for i := ListChemins.Count - 1 downto 0 do
         ListChemins.Delete(i);
 
      FreeAndNil(ListChemins);
   end;
end;

Si j'utilise le SetLocation au lieu du TPoint.Create sur l'affectation j'ai directement un mémoire insuffisante et je ne vois pas pourquoi..

C'est sur que au bout d'un moment boucler sur des ensembles aussi grands .. mais j'ai vraiment besoin de garder en mémoire le contenu de la liste.

Auriez vous une idée pour éviter cette erreur ?

Merci

[Linkin]

Pour 2 milliards de TPoint, tu es environ à 16 Go de RAM occupée (au moins 8 octets pour le TPoint * 2 000 000 000).

Premièrement, ton application devrait être en 64 bits, deuxièmement, matériellement, il faudrait une machine qui ait suffisamment de RAM.

Par contre je n'ai pas de solution pour ton problème. Il faudrait voir s'il est possible de modifier ton algo pour limiter les références de TPoint.

[retwas]

Merci pour la réponse, finalement c'est ok avec une fonction récursive même si faut attendre 3 plombes

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
procedure TForm2.CheckPoint(aPoint: TPoint);
begin
   while (aPoint.X <> iWidth) and (aPoint.Y <> iWidth) do
   begin
      if (aPoint.X < iWidth) and (aPoint.Y < iWidth) then
      begin
         CheckPoint(TPoint.Create(aPoint.X, aPoint.Y + 1));
 
         aPoint.X := aPoint.X + 1;
      end else
      if aPoint.X < iWidth then
      begin
         aPoint.X := aPoint.X + 1;
      end else
      if aPoint.Y < iWidth then
      begin
         aPoint.Y := aPoint.Y + 1;
      end;
   end;
 
   aPoint := Default(TPoint);
   Inc(iFin);
end;

Avec un premier appel :

Code :

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

CheckPoint(TPoint.Create(0, 0));

[ShaiLeTroll]

A l'époque où l'on avait que 512Mo au mieux sur un Pentium4
J'ai du gérer beaucoup de données calculées, j'ai utilisé un fichier directement pour y gérer un tableau géant de 10Go
Cela allait 100 fois plus vite d'utiliser un fichier que de laisser faire le Swap (tant que l'on était sous les 2Go) après de toute façon cela plantait comme toi

Photoshop fonctionnait ainsi, il gérait son propre swap fichier au lieu de celui de l'OS

[GoustiFruit]

J'ai du mal à comprendre comment une fonction récursive pourrait utiliser moins de mémoire ? Je pense plutôt que les deux fonctions font des choses différentes !?

Par curiosité, tu pourrais nous expliquer à quoi sert ce code ?

[retwas]

Merci je vais regarder ce que je peux faire avec un fichier enregistré sur disque

Enfaîte il s'agit du lattice path, c'est à dire trouver le nombre de chemin possible sur une carré de côté n pour aller du coin en haut à gauche au coin en bas à droite en se déplacent uniquement vers le bas ou la droite. Par exemple sur un carré de côté 1x1 il existe 2 chemins, 6 chemins sur un carré de 2x2 et dans mon cas sur un carré de 20x20 il existe plus de 137 milliards de chemins.

Dans le premier cas j'ai une liste de TPoint qui contient les items, dans le 2ème cas je ne stock pas les items mais j'incrémente un compteur pour savoir combien il y a de chemins possible de ce fait cela m'évite l'erreur de mémoire insuffisante.

[sgmsg]

Au lieu de sauvegarder des chemins, pourquoi ne pas sauvegarder des branches?

Tu donnes toi même une partie de la solution qui ressemble à un codage de Hoffman

À chaque nœud, c'est binaire tu tournes à droite ou tu descends...

En utilisant un AnsiString de 4 million d'octets, tu codes 32 millions de chemins
Donc sans compression, il te faut environ 5000 chaines.

---

En partant de (20,0) (dernière colonne) ton chemin est (20,1),(20,2)...(20,20), elle est unique;
Ensuite en commençant à (19,0), tu as 20 chemins qui forcément rentrent dans la colonne précédente (20,y)
Ensuite tu es à (18,0) tu as vingt façons de rentrer dans la colonne (19,Y)
Etc.
Ce qui donne plutôt 5,24288e+24 chemins, tu n'auras (ni même google) pas un disque dur ni probablement de ferme de serveur qui codera tout ça même au niveau du bit...

Ce qui veut dire que tu dois pointer chaque point (x,y) sinon, car tu n'arriveras pas à dénombrer les chemins possible de ton vivant...

---

Une matrice de 20 x 20 fait 400 nœuds, ce qui est facilement programmable.

[retwas]

Ta solution me fait penser au triangle de Pascal, avec la fonction récursive j'obtiens bien le résultat pour un carré de 20x20, ma variable de type Int64 est bien de 137 milliards et quelques, seul "problème" cela met 15mn à s'exécuter.

Je vais faire un test avec ta méthode

[SergioMaster]

Bonjour,

Cela pourrait peut être se faire avec un SGBD acceptant les requêtes récursives (i.e. SQlite) si j'ai le temps je tenterai le coup, alliant ainsi sauvegarde en fichier et calculs

[Paul TOTH]

tu fais de la brute force attack

ceci est plus intéressant
http://www.robertdickau.com/lattices.html

[sgmsg]

Désolé, je n'avais pas compris que le carré s'appuyait sur un des coins, je croyais qu'il s'appuyait sur un des côtés... Et donc qu'il fallait traverser une diagonale tout en pouvant passer d'un point (x,y) à (x+1,y+1), je croyais qu'on était limité à (x,y) à (x+1,y) ou (x,y+1).

(Merci Paul)

---

Il y a quelque chose qui m'échappe, je ferais aussi bien de ne rien dire...

[retwas]

Bonjour,
Cela pourrait peut être se faire avec un SGBD acceptant les requêtes récursives (i.e. SQlite) si j'ai le temps je tenterai le coup, alliant ainsi sauvegarde en fichier et calculs

Si tu trouves je suis intéressé par le résultat

tu fais de la brute force attack
ceci est plus intéressant
http://www.robertdickau.com/lattices.html

Merci Paul, calcul pour un carré de 20x20 en 0 ms avec le Triangle de Pascal

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
type
   TCellule = class
      Value: Int64;
   end;
 
   TLigne = class(TObjectList<TCellule>)
   public
      function ToString: string;
   end;
 
   TTableau = TObjectList<TLigne>;
 
function TLigne.ToString: string;
var
   i: Integer;
begin
   Result := '';
 
   for i := 0 to Count - 1 do
      Result := Result + Items[i].Value.ToString;
end;

Le code de la procédure pour calculer :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
procedure TForm2.Calculer(aValue: integer);
var
   Tab    : TTableau;
   Ligne  : TLigne;
   Cellule: TCellule;
   i, j   : integer;
   Chrono : TStopwatch;
begin
   Tab    := TTableau.Create;
   Chrono := TStopwatch.StartNew;
   try
      // valeur de la cellule n sur la ligne n*2
      for i := 0 to aValue * 2 do
      begin
         Ligne := TLigne.Create;
 
         if i = 0 then
         begin
            Cellule := TCellule.Create;
            Cellule.Value := 1;
            Ligne.Add(Cellule);
         end else
         begin
            for j := 0 to i do
            begin
               if (j = 0) or (j = i) then
               begin
                  Cellule := TCellule.Create;
                  Cellule.Value := 1;
                  Ligne.Add(Cellule);
               end
               else
               begin
                  Cellule := TCellule.Create;
                  Cellule.Value := Tab[Tab.Count - 1][j - 1].Value + Tab[Tab.Count - 1][j].Value;
                  Ligne.Add(Cellule);
               end;
            end;
         end;
 
         Tab.Add(Ligne);
      end;
 
      Chrono.Stop;
      Label1.Caption := Tab[aValue * 2][aValue].Value.ToString + ' ' + Chrono.ElapsedMilliseconds.ToString + ' ms.';
   finally
      FreeAndNil(Tab);
   end;
end;