Discussion :

[aragog]

Bonsoir,

il y a quelques semaines, mon prof mentionnait la création d'un allocateur spécialisé pour les chaînes de caractères afin d'éviter le dépassement de tas lors d'un tri par hachage.
En partant sur cette base, il me semble que l'on devait mettre les chaînes dans un enregistrement afin d'allouer au gré de nos besoins.

De ce fait, si j'ai une liste sur le type String, ses cellules ne contiendront plus directement 256 octets mais seulement l'adresse menant à la chaîne stockée dans le record.

Ce devrait ressembler à quelque chose comme :

Code :

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

1
2
3
4
5
6
7
8
  Allocateur = array [1..32000] of ^String;
  Alloc =
    record
       t : Allocateur;
       k : integer;
    end;
 
var maVar : Alloc.

Besoin de stocker une chaîne ? Boum !

Code :

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

1
2
New(maVar.t[i]);
maVar.t[i] := chaine;

Quelqu'un peut-il affirmer ou infirmer ce que j'avance et me donner davantage d'informations svp puisque j'aimerais le coder ?

Merci d'avance pour vos réponses.

Cordialement,

Aragog.

[Alcatîz]

Bonjour,

Je pense que le bât blesse au niveau de la taille du segment de données et de la taille maximale d'une variable.
Plutôt qu'un tableau de pointeurs vers des chaînes de caractères stockées dans le tas, tu pourrais utiliser une liste chaînée ?

S'il s'agit d'économiser de l'espace, l'utilisation des chaînes à zéro terminal au lieu du type String serait peut-être plus indiquée. Si tu veux avoir un aperçu de la gestion de ce type de chaînes : http://alcatiz.developpez.com/tutoriel/owl/?page=pg_azt (c'est un autre compilateur mais c'est compatible avec l'unité Strings de Turbo Pascal 7). La fin de la page traite de l'allocation dynamique des chaînes à zéro terminal.

[aragog]

J'utilise déjà une liste dynamique simplement chaînée.

Et malheureusement, je suis trop peu à l'aise avec cette notion de chaînes à zéro terminal pour pouvoir l'inclure dans toute ma structure.
Mais je comprends aisément pourquoi le tas explose, en effet, chaque cellule de ma liste peuvent contenir (entre autres qui plus est) 3 chaînes de 256 octets chacune donc lors du tri par hachage, ça ne fonctionne plus trop trop bien.

Merci quand même pour votre aide.

[Paul TOTH]

moi je verrais bien ceci

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
 
type
  PString = ^string;
 
function AllocString(Len: Integer):PString;
var
  S: PString;
begin
  GetMem(S, Len + 1);
  AllocString := S;
end;
 
var
  S: PString;
begin
  S := AllocString(5);
  S^ := 'Hello';
end;

ou encore

Code :

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

1
2
3
4
5
6
7
8
9
 
function AllocString(const s: string): PString;
var
  p: PString;
begin
  GetMem(p, Length(s) + 1);
  p^ := s;
  AllocString := p;
end;

[aragog]

Ah oui en effet, je comprend ici tout l'avantage d'une telle méthode, on ne gâche aucune mémoire, merci beaucoup, je vais essayer de suite sur mon programme et je vois si j'arrive à mettre tout ça en œuvre.

Cependant une question sûrement très bête, vous marquez

Code :

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

Length(s) + 1

car vous n'oubliez pas la taille de la chaîne stockée en s[0], c'est ça ?

[Paul TOTH]

Ah oui en effet, je comprend ici tout l'avantage d'une telle méthode, on ne gâche aucune mémoire, merci beaucoup, je vais essayer de suite sur mon programme et je vois si j'arrive à mettre tout ça en œuvre.

Cependant une question sûrement très bête, vous marquez

Code :

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

Length(s) + 1

car vous n'oubliez pas la taille de la chaîne stockée en s[0], c'est ça ?

tout à fait...note que depuis Dephi 2 les strings sont déjà des zones mémoires allouées dynamiquement sans qu'on ai besoin de s'en soucier