Newsgroup: it.comp.lang.delphi
Titolo: Efficienza confronto liste

Ciao a tutti!
Ho due liste di stringhe TCheckListBox che devo confrontare tra loro
per verificare che non abbiano elementi in comune. Gli elementi sono in
ordine alfabetico ed il confronto l'ho realizzato con un algoritmo che
tiene conto della posizione dell'ultimo elemento trovato, in modo da
non dover cercare sempre da inizio lista. Quando la dimensione delle
liste supera i 9000 elementi, il tempo di elaborazione diventa troppo
elevato. Avete qualche idea in merito? Se memorizzo le liste su un DB
le prestazioni per il confronto migliorerebbero??
Grazie mille in anticipo!

carmelo ha scritto:

Ciao,
   scusa ma non sono sicuro di aver capito bene. Mi spiego.
Hai 2 liste di stringhe gia' ordinate alfabeticamente: Lista1 e Lista2. 
Diciamo che vuoi sapere, per ogni elemento di Lista2, se esso sia 
contenuto in Lista1.
Mi sembra abbastanza chiaro che i problemi di prestazioni possono 
presentarsi in due punti:
1. in fase di scorrimento di Lista2: in questo caso la complessita' 
computazionale, per come hai descritto il problema tu, e' chiaramente "n";
2. in fase di ricerca dell'i-esimo elemento di Lista2 in Lista1. Qui la 
complessita' computazionale puo' crescere linearmente se tu scorri 
Lista1, elemento per elemento.
Da quanto mi sembra di capire pero', hai trovato il modo di ridurre il 
set di elementi in cui effettuare la ricerca, ma questo non ti aiuta 
abbastanza in quanto, fatta "m" la dimensione del nuovo insieme, allora 
la complessita' totale sarebbe:
  	n*(m1+m2+m3+...);  // dove m1, m2, m3 sono le dimensioni dei vari 
insiemi di ricerca, sottoinsiemi di Lista1
Un'alternativa potrebbe consistere nell'utilizzare una libreria di 
contenitori (e relativi algoritmi) gia' sviluppata (io ricordo che un 
paio di anni fa utilizzammo una Delphi Container Library - OpenSource e 
freeware- prova con Google) e sfruttare un albero binario di ricerca 
(bilanciato) per memorizzare i dati contenuti nelle TCheckListBox.
In questo caso consumeresti piu' memoria (a causa degli alberi binari 
legati alle liste) pero' potresti poi sfruttare questi "adattatori" (gli 
alberi binari) per i compiti che le TCheckListBox non ti permettono di 
risolvere facilmente.
Nella fattispecie, per sapere se Lista1 contiene l'i-esimo elemento di 
Lista2, potresti semplicemente chiamare un metodo "Contains", passando 
l'i-esima stringa di Lista2:
var
   i: Integer;
{
TAdvancedCheckListBox e' una classe derivata da TCheckListBox 		che 
aggrega un oggetto di tipo TStrBinaryTree, reimplementa metodi "Add" e 
"Delete" per aggiungere e togliere elementi da tale oggetto etc.
}
   Lista1, Lista2: TAdvancedCheckListBox;
begin
   for i:=0 to (Lista2.Count-1) do
     //	SearchAdapter e' di tipo TStrBinaryTree
     if Lista1.SearchAdapter.Contains(Lista2.Items[i]) then
       ShowMessage('Trovato!');
end;
Gli alberi binari hanno una complessita' computazionale degli algoritmi 
di ricerca che e' logaritmica e quindi piu' bassa e dipenderebbe 
dall'altezza (h) dell'albero, che essendo bilanciato e' sempre ottimizzata.
E' chiaro che, fin quando scorrerai *uno a uno* gli elementi di Lista2 
per cercarli in Lista1, la complessita' computazionale di qualsiasi 
soluzione tu adotti, agira' da moltiplicatore della complessita' 
computazionale "n" di scorrimento di Lista2.
Fammi sapere se ho frainteso.
baba.

 non dover cercare sempre da inizio lista
Ordina con un bubble o quicksort le due liste, e confrontane gli elementi,
con una passata troverai tutte le differenze.
ciao
-- 
Morde. 
ICLDweb: 
http://www2.samatel.com/icld/



Se le liste,come immagiono, con contengono duplicati puoi usare una
THashedStringList.
-- 
Ore 18.30: premo invio.

Baba hai capito bene. Quindi il tuo consiglio è quello di installare
la Delphi Container Library e di usare TAdvancedCheckListBox, che
implementa gli alberi binari di ricerca... sai se esiste qualcosa del
genere anche per C++Builder?
Massimo Pini, grazie per il tuo consiglio, effettivamente le hash table
sono molto efficienti per la ricerca di un elemento. Però il problema
è che non sto usando un TStringList, ma un TCheckListBox... hai una
idea su come potrei fare?

 idea su come potrei fare?
Forse lui voleva dirti di associare le stringhe che visualizzi nella 
TCheckListBox ad una THashedStringList la quale ti fornirebbe la 
capacita' di ordinare, ricercare etc.
Ciao,
baba.

Ok baba garzie!
Come potrei fare per associare le stringhe che visualizzo nella
TCheckListBox ad una THashedStringList??
Per risolvere il mio problema dovrei creare due THashedStringList ed
associarle una alla CheckListBox1 e l'altra alla CheckListBox2?? Per
poi fare la ricerca sulle THashedStringList, farmi restituire la
posizione della stringa trovata, ed intervenire poi sulle
TCheckListBox...



Senza entrare nello specifico del tuo problema, per l'assegnazione è
molto semplice:
HashStringList.Assign(CheckListBox1.Items);


 TCheckListBox...
Qui non ti seguo piu'. A te non serviva *SOLO* sapere se un elemento di 
Lista2 e' contenuto in Lista1? Se si, la soluzione a cui sei arrivato ti 
basta gia'.
Ora supponiamo che tu scopra che l'elemento i-esimo di Lista2 sia 
presente in Lista1, cosa vuoi farci?
Ciao,
baba.

 presente in Lista1, cosa vuoi farci?
devo marcare gli elementi presenti

 
Marcare in Lista1 l'elemento corrispondente all'i-esimo di Lista2?
Ciao,
baba.

Ho CheckListBox1 e CheckListBox2. Devo cercare gli elementi di
CheckListBox1 su CheckListBox2, e marcare su CheckListBox2 quelli
trovati

per verificare che non abbiano elementi in comune.
Usa un TClientDataSet.  Crei un solo campo, ci scrivi dentro le
stringhe, lo indicizzi (IndexFieldNames=campo) e cerchi con delle
belle Locate() la stringa incriminata.  Facile, sicuro, veloce.

Grazie Massimo!
Grazie ragazzi per i vostri consigli. Ho risolto così: ho creato due
THashedStringList, una per ogni TCheckListBox, ed ho assegnato alle
THashedStringList gli elementi dei TCheckListBox. Eseguo la ricerca
degli elementi sulle THashedStringList, le quali rispondono
praticamente all'istante... infatti, se non sbaglio, la complessità in
questo caso è O(1)...

 ha scritto nel messaggio 
news:1142861476....@v46g2000cwv.googlegroups.com...

Oltre all'uso dell'algoritmo citato potresti esguire un ricerca dicotomica 
nella seconda ChickListBox, che e' molto piu' veloce che scorrere i 
rimanenti elementi, Giorgio.