Newsgroup: it.comp.lang.delphi
Titolo: TList, new, dispose et similia

Ciao a tutti.
Il mio problema è questo.
Un metodo di una mia classe riceve in ingresso un codice.
Per questo codice devo recuperare un ID tramite una query.
Poichè questa operazione deve essere eseguita circa 30.000 volte al giorno,
ho pensato di creare una tlist nella quale assegno alla proprietà Items un
puntatore a questa struttura:
type PQualcosa = ^Qualcosa;
type TQualcosa= record
  Codice: string;
  Id: integer;
  end;
Ora, nel mio metodo dovrei quindi scrivere una cosa del tipo:
var p:  PQualcosa;
New(p);
With Lista do
begin
  for i:= o to count -1 do
  begin
    P := Items[i];
    if  p^.Codice = ACodice then
    begin
      result := p^.Id
      Dispose(p);
      exit;
   end;
Questo bloccco dovrebbe poi essere eseguito dopo la query per aggiungere la
nuova sequenza codice-id alla lista:
With Lista do
begin
  P^.Codice := ACodice;
  P?.Id := Id;
  Add(p)
end;
Questo codice è giusto, tenendo conto del fatto che nella destroy della
classe scrivo:
With Lista do
  for i:= o to count -1 do
   P := Nil
oppure nel metodo devo dare una dispose per liberare p?
E se do una dispose per liberarlo un uscita dal metodo, potro poi
referenziarlo?
Scusate se ho scrittto kazzate ma è forse la 1° volta che uso i puntatori.
Normalmente uso classi e le appioppo alla prorp. objects di una tstringlist.
Bye
AS


Fare P := nil non libera nulla, semplicemente dici alla variabile che
punta a nil.
for i := 0 to Lista.Count - 1 do 
  Dispose(PQualcosa(Lista[I]));
Lista.Free;
Massimo.
-- 
Ore 18.30: premo invio.

Scusami: non ho capito ne 1 ne 2 :(((
Bye
AS

   end;
Parte 1)
esempio:
type TStruttura = record
            A: Integer;
            B: Rea;
          end;
         PStruttura = ^TStruttura;
Procedure Pippo;
var P: PStruttura;
  MyList: TList;
begin
  New(P); //Alloco memoria per contenere una TStruttura e passo a P
l'indirizzo.
  New(P); //alloco altra memoria e conseguentemente perdo per sempre
l'indirizzo della prima struttura
end;
Procedure Pippo;
var P: PStruttura;
  MyList: TList;
begin
  New(P); //Alloco memoria per contenere una TStruttura e passo a P
l'indirizzo.
  MyList.Add(P);  //Salvo in una lista *l'indirizzo* della struttura
  New(P); // Alloco nuova memoria e passo l'indirizzo a P
  MyList.Add(P); //A questo punto a me di P non me ne frega più niente
e quindi lo riutilizzo nel mio ciclo
  for I := 0 to MyList.Count -1 do 
    P := MyList[I];
end;
Parte 2)
Tu trovi il puntatore che ti serve (if P^.Codice = x then)
e quindi, rilasci correttamente il puntatore (Dispose(P)) e poi esci.
Cosa succede in questo modo? Semplice: quando deciderai di rilasciare
la lista ad un certo pinto...
for I := 0 to MyList.Count - 1 do 
  Dispose(PStruttura(MyList[I]))
tenterai di fare un'altra volta il dipose del puntatore che avevi già
rilasciato in precedenza (EAccessViolation).
Le soluzioni sono quindi tre:
1) rilasci anche l'item sulla lista (MyList.Delete(I)) oppure, ma a me
piace meno,
2) MyList.Items[I] := nil e poi
for I := 0 to MyList.Count - 1 do 
  if Assigned(PStruttura(MyList[I])) then
  Dispose(PStruttura(MyList[I]))
e mi sembra quella corretta in questa situazione,
3) Non fai quel New(P) all'inizio e NON fai il Dispose(P) prima
dell'exit.
Spero di essere stato almeno un pelino piu' chiaro, spiegare queste
cose non è esattamente il mio forte.
Ciao.


 ho pensato di creare una tlist nella quale assegno alla proprietą Items un
Un consiglio:
La lista, a mio avviso, non e' il container migliore per il tipo 
di operazione che vuoi fare.  Potresti ottimizzare di molto le 
prestazioni se, anziche' una lista, costruissi un albero binario.
type PTreeNode = ^TreeNode;
     TreeNode = record
                  ID: Integer;
                  Codice: String;
                  Sx, Dx: PTreeNode;
                end;
procedure Insert(var Root: PTreeNode;
                 ID: Integer; Codice: String);
begin
  if Root = nil then
  begin
    New(Root);
    Root.ID := ID;
    Root.Codice := Codice;
    Root.Sx := 0;
    Root.Dx := 0;
  end
  else
  if Codice <= Root.Codice then
    Insert(Root.Sx, ID, Codice)
  else
    Insert(Root.Dx, ID, Codice);
end;
function FindId(Root: PTreeNode;
                Codice: String): Integer;
begin
  if Root = nil then
    Result := -1
  else
  if Codice = Root.Codice then
    Result := Root.ID
  else
  if Codice < Root.Codice then
    Result := FindId(Root.Sx, Codice)
  else
    Result := FindId(Root.Dx, Codice);
end;
procedure TForm1.Button1Click(Sender: TObject);
var
  Root: PTreeNode;
begin
  Root := nil;
  Insert(Root, 3221, 'armadio');
  Insert(Root, 3222, 'scopa');
  Insert(Root, 3223, 'libro');
  ShowMessage(IntToStr(FindId(Root, 'scopa')));
  ShowMessage(IntToStr(FindId(Root, 'armadio')));
  ShowMessage(IntToStr(FindId(Root, 'libro')));
  ShowMessage(IntToStr(FindId(Root, 'orologio')));
end;
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 prestazioni se, anziche' una lista, costruissi un albero binario.
Questa me la studio con calma.
Magari non la uso adesso, pero'
I codici che devo memorizzare nella lista sono circa 100.
Quindi non ho particolati problemi di prestazioni.
Tnx
AS


Scusa, ma che senso ha fare un albero binario se poi, di fatto, fai
una ricerca sequenziale? La lista è molto più semplice da gestire e
anche più performante. Piuttosto, IMHO, se hai una lista di valori
unvoci conviene ordinarla e poi fare una ricerca dicotomica.
Tipo questo prototipo
function GetMyPointer(Codice: Integer): PQualchecosa;
var
  MinV, MaxV, CursPos: Integer;
begin
  MinV := 0;
  MaxV := MyList.Count - 1;
  CursPos := MyList.Count div 2;
  while MinV <= MaxV do begin  
    P := MyList[CursPos];
    if P.Codice <> Codice then begin
      if P.Codice < Codice then
          MinV := Succ(CursPos)
      else
          MaxV := Pred(CursPos);
        CursPos := (MaxV + MinV) div 2;
    end else begin
       Result := P;
       Break;
    end
  end;
end;
Ciao,


 Quindi non ho particolati problemi di prestazioni.
Se i codici da memorizzare sono cosi' pochi, allora usa un
array dinamico.  Lo allunghi e lo accorci, se ti serve e non
hai bisogno di gestire meccanismi strani.
Io ti ho suggerito l'albero perche' supponevo i codici fossero
tanti e se fai quell'operazione 30.000 volte al giorno, un 
algoritmo O(logn) e' sempre preferibile ad uno O(n).


 una ricerca sequenziale?
Chi l'ha detto che e' una ricerca sequenziale ?
La ricerca fatta con l'albero binario e' dicotomica.


La ricerca fatta con l'albero binario e' dicotomica.
Siccome con Laforgia si rischia sempre di sembrare dei deficienti....
1) la tua ricerca NON è dicotomica ma sequenziale. Parti da root a vai
SEMPRE  a destra In quanto non parti da metà lista e poi incrementi o
decrementi di un solo Item.
2) visto che va di moda ho fatto anch'io un test per vedere la
differenza di performance tra una albero binario siffatto (male) e
l'uso di TList e ricerca dicotomica come dico io.
I risultati sono per lo meni sorprendenti.
Ho inserito 1000 puntatori e ho fatto 100000 ricerche:
Metodo Laforgia: 881 cicli e 49.000.000 loops.
Metodo Pini: 450 cicli e 900.000 loops.
Tutto ciò non per essere più bravo ma semplicemente per non passare
per pirla.
Il test e' fatto di corsa, non rilascio i puntatori, e inserisco già
gli item in ordine.
program Project2;
{$APPTYPE CONSOLE}
uses
  SysUtils,
  Windows, classes;
type
  PLaforgia = ^TLaforgia;
  TLaforgia = record
    ID: Integer;
    DX, SX: PLaforgia;
  end;
  PMax = ^TMax;
  TMax = record
    ID: Integer;
  end;
var
  S: Cardinal;
  I: Integer;
  Root: PLaforgia;
  MaxList: TList;
  MaxRoot: PMax;
  MaxLoop, LFLoop: Integer;
procedure LFInsert(var Root: PLaforgia; ID: Integer);
begin
  if Root = nil then
  begin
    New(Root);
    Root.ID := ID;
    Root.Sx := nil;
    Root.Dx := nil;
  end
  else
  if  ID <= Root.ID then
    LFInsert(Root.Sx, ID)
  else
    LFInsert(Root.Dx, ID);
end;
function LFFindId(Root: PLaforgia; Valore: Integer): Integer;
begin
  Inc(LFLoop);
  if Root = nil then
    Result := -1
  else
  if Valore = Root.ID then
    Result := Root.ID
  else
  if Valore < Root.ID then
    Result := LFFindId(Root.Sx, Valore)
  else
    Result := LFFindId(Root.Dx, Valore);
end;
function MaxFind(Valore: Integer): Integer;
var
  MaxV, MinV, CP: Integer;
  P: PMax;
begin
  Result := -1;
  MinV := 0;
  MaxV := MaxList.Count - 1;
  CP := MaxList.Count div 2;
  while MinV <= MaxV do begin
    Inc(MaxLoop);
    P := MaxList[CP];
    if 
P.ID
 <> Valore then begin
      if 
P.ID
 < Valore then
        MinV := Succ(CP)
      else
        MaxV := Pred(CP);
      CP := (MaxV + MinV) div 2;
    end else begin
      Result := 
P.ID
;
      Break;
    end;
  end;
end;
begin
  MaxLoop := 0;
  LFLoop := 0;
  writeln('Procedura Laforgia');
  Readln;
  S := GetTickCount;
  Root := nil;
  Randomize;
  for I := 1 to 1000 do
    LFInsert(Root, I);
  for I := 1 to 100000 do
    LFFindId(Root, Random(1000) + 1);
  S := GetTickCount - S;
  Writeln;
  Writeln('Tempo richiesto: ' + Inttostr(S));
  writeln('loop eseguiti ' + IntToStr(LFLoop));
  Readln;
  Writeln('Procedura Max');
  S := GetTickCount;
  MaxList := TList.Create;
  for I := 1 to 1000 do begin
    New(MaxRoot);
    MaxRoot.ID := I;
    MaxList.Add(MaxRoot);
  end;
  for I := 1 to 100000 do begin
    MaxFind(Random(1000) + 1);
  end;
  S := GetTickCount - S;
  Writeln;
  Writeln('Tempo richiesto: ' + Inttostr(S));
  writeln('loop eseguiti ' + IntToStr(MaxLoop));
  Readln;
end.


 Siccome con Laforgia si rischia sempre di sembrare dei deficienti....
Pini, qua nessuno ti vuol far passare per deficiente, ma devi
stare attento ai test che fai.  Tutti sanno che il "worst-case"
dell'attraversamento di un albero binario, si ha nel caso in
cui gli elementi siano gia' ordinati (nel qual caso la ricerca
"decade" in una ricerca sequenziale e quindi l'albero degenera
in una lista).  Ora, qual e' il trucco perche' l'albero sia
performante ? quello di lasciare che sia esso stesso ad ordinare 
gli elementi.  Non e' affatto vero che nel mio metodo 
l'attraversamento va sempre a destra, dipende dal modo in cui
inserisci gli elementi.  E' chiaro che se gli elementi sono
gia' ordinati, gli inserimenti avverranno sempre sul lato destro
del nodo che consideri (a seconda, poi, se sono ordinati in
modo ascendente o discendente) e quindi le performance non 
saranno ottimali (in quanto il famoso O(logn) degenera in un O(n)).
Ma non e' previsto, a priori, che gli elementi siano gia' 
ordinati.  Tieni anche presente che l'uso della lista che tu
fai equivale ad utilizzare un albero binario, la lista e', 
per definizione, una struttura dati sequenziale, che prevede 
un attraversamento sequenziale.
La ricerca che Alberto fa e' una ricerca sequenziale, che
viene ottimizzata con una ricerca dicotomica e, nel caso peggiore,
ha le stesse performance.


     MaxList.Add(MaxRoot);
Aggiungo una nota importante: nel caso non si conosca a priori il
numero di elementi da considerare, l'uso del metodo Add non e'
ovviamente consigliabile, perche' significherebbe riordinare tutte
le volte la lista.  E' quindi necessario usare Insert, dopo 
essersi assicurati qual'e' l'indice giusto, in cui inserire il
nuovo elemento, affinche' sia preservato l'ordine.
Ora, Insert prevede che ci sia lo "shift" di tutti gli elementi 
(la lista e' una struttura dati sequenziale) e lo scostamento di 
tutti gli elementi di un posto puo' essere un'operazione abbastanza 
onerosa, se il numero degli elementi nella struttura dati cresce.




Su questo non si discute, le soluzioni che si devono prendere, spesso,
variano in base alla premessa.
Un po' di tempo fa avevo sviluppato una classe che, mantenendo
esternamente l'aspetto di TList, utilizzava il metodo dell'albero
binario proprio perché la creazione della lista avveniva nel tempo.
Fatto sta che, comunque, ogni metodo ha i suoi pregi e difetti,
l'albero binario l'ho usato per anni, ma con l'avvento del tlist, la
pigrizia ha preso il sopravvento essendo molto piů facile da
mantenere.
Comunque, in effetti, su sistemi altamente disordinati, il metodo da
te postato č efficace.


 te postato è efficace.
Gli alberi sono le strutture che si preferiscono, generalmente,
per implementare i dbms (btree, red-black tree, AVL, ecc...), 
proprio perche' i tempi di ricerca vengono ottimizzati al massimo.
