Discussione:
Numero di elementi di un insieme e velocità.
(troppo vecchio per rispondere)
Cooper
2009-12-31 13:25:03 UTC
Permalink
Ciao a tutti,
se ho un insieme cosi definito:

Type X: Set Of Byte;

Io so l'insieme X può contenere da un minimo 0 elementi (insieme vuoto) fino
ad un massimo di 255 elementi.
Ora per determinare il numero di elementi di un insieme ho utilizzato questa
funzione:

Function TIdv.GeTElementsNumber (Ins: X): Byte;
Var X, Y: Byte;
Begin
X := 0;
For Y := 0 To 255 Do
Begin
If Y In Ins Then Inc (X);
End;
Result := X;
End;

Che svolge egregiamente il suo compito; purtroppo però in un contesto dove
viene richiamata migliaia di volte, essa rallenta la velocità di
elaborazione dei dati, in conseguenza di ciò cercavo una soluzione
alternativa e di conseguenza più veloce.
Sapete indicarmi una soluzione alternativa che mi fornisca l'informazione
richiesta (il numero di elementi) in modo più veloce, senza ricorrere ad un
ciclo?
Grazie in anticipo.
Cooper.
MBulu
2009-12-31 15:33:55 UTC
Permalink
Post by Cooper
Sapete indicarmi una soluzione alternativa che mi fornisca l'informazione
richiesta (il numero di elementi) in modo più veloce, senza ricorrere ad un
ciclo?
Grazie in anticipo.
Cooper.
Non l'ho mai provato, ma stando a quello che c'è scritto qui:
http://www.delphibasics.co.uk/RTL.asp?Name=Set
dovrebbe andar bene "X:=SizeOf(Ins)"

Ciao, Mario
MBulu
2009-12-31 16:09:29 UTC
Permalink
Post by MBulu
http://www.delphibasics.co.uk/RTL.asp?Name=Set
dovrebbe andar bene "X:=SizeOf(Ins)"
Come non detto, non è quello che volevi tu ...

Ciao, Mario
Marco Breveglieri
2010-01-02 15:21:41 UTC
Permalink
Post by Cooper
Io so l'insieme X può contenere da un minimo 0 elementi (insieme vuoto)
fino ad un massimo di 255 elementi.
Ora per determinare il numero di elementi di un insieme ho utilizzato
questa funzione [...]
Sapete indicarmi una soluzione alternativa che mi fornisca
l'informazione richiesta (il numero di elementi) in modo più veloce,
senza ricorrere ad un ciclo?
Temo che non vi sia una soluzione alternativa a quella che hai adottato
tu; cercando in giro, ho individuato un codice che probabilmente
velocizza l'operazione ottimizzando la verifica dei singoli byte della
variabile che rappresenta il *set*:
http://codecentral.embarcadero.com/Item/14018

Personalmente, non mi è mai capitato di dover effettuare un simile
conteggio su una variabile di tipo *set*... sei sicuro che questo tipo
di variabile sia realmente adatto alla tua esigenza e che non sia invece
più proficuo usare una struttura diversa, come un *array* o ancora
meglio una *TList*?

Ciao,
Marco.
--
MARCO BREVEGLIERI
(http://www.marco.breveglieri.name)
MBulu
2010-01-02 16:53:25 UTC
Permalink
Post by Cooper
Sapete indicarmi una soluzione alternativa che mi fornisca
l'informazione richiesta (il numero di elementi) in modo più veloce,
senza ricorrere ad un ciclo?
Personalmente, non mi è mai capitato di dover effettuare un simile conteggio
su una variabile di tipo *set*... sei sicuro che questo tipo di variabile sia
realmente adatto alla tua esigenza e che non sia invece più proficuo usare
una struttura diversa, come un *array* o ancora meglio una *TList*?
Ciao,
Marco.
In alternativa, potresti creare una struttura composta in questa
maniera:
- totale elementi
- set

In fase di creazione il set è vuoto ed il totale degli elementi è 0.
Quando aggiungi un elemento al set, incrementi il totale.
Quando togli un elemento dal set, decrementi il totale.
Se inizializzi il set azzeri il totale.

In questo modo, quando vuoi conoscere il numero degli elementi, ti
basta testare il campo del totale.

Ciao, Mario
Cooper
2010-01-02 21:05:41 UTC
Permalink
Post by MBulu
Post by Marco Breveglieri
Post by Cooper
Sapete indicarmi una soluzione alternativa che mi fornisca
l'informazione richiesta (il numero di elementi) in modo più veloce,
senza ricorrere ad un ciclo?
Personalmente, non mi è mai capitato di dover effettuare un simile
conteggio su una variabile di tipo *set*... sei sicuro che questo tipo di
variabile sia realmente adatto alla tua esigenza e che non sia invece più
proficuo usare una struttura diversa, come un *array* o ancora meglio una
*TList*?
Ciao,
Marco.
- totale elementi
- set
In fase di creazione il set è vuoto ed il totale degli elementi è 0.
Quando aggiungi un elemento al set, incrementi il totale.
Quando togli un elemento dal set, decrementi il totale.
Se inizializzi il set azzeri il totale.
In questo modo, quando vuoi conoscere il numero degli elementi, ti basta
testare il campo del totale.
Avevo pensato a una soluzione del genere, creando una classe che simulasse
un insieme e le operazioni ad esso connesse (unione, intersezione etc) ma
poi facendo quattro conti l'ho scartata, nel senso che il numero di
istruzioni eseguite diventa superiore a quelle della soluzione precedente.
Il mio obiettivo è velocizzare il processo di elaborazione per "grandi
numeri"; in questo modo mi trovo costretto a monitorare l'insieme facendo in
ogni caso delle assegnazioni quando poi non mi servirebbero.
Invece ho risolto il problema riscrivendo l'algoritmo, e passando da circa 3
minuti di "attesa" per l'elaborazione a circa 1 minuto e 20 secondi, circa
20-30 secondi in più rispetto allo stesso algoritmo escludendo il conteggio
degli elementi.
Insomma sono riuscito comunque a dimezzare i tempi di elaborazione e già è
qualcosa.
Alberto Salvati
2010-01-04 11:33:36 UTC
Permalink
Post by Cooper
Avevo pensato a una soluzione del genere, creando una classe che simulasse
un insieme e le operazioni ad esso connesse (unione, intersezione etc)  ma
poi facendo quattro conti l'ho scartata,
come l'avevi pensata per farti i 4 conti ? Spiega.
Post by Cooper
Il mio obiettivo è velocizzare il processo di elaborazione per "grandi
numeri";
Che vuol dire "grandi numeri"? Quantifica.

A.
Cooper
2010-01-04 12:15:57 UTC
Permalink
Post by Alberto Salvati
Post by Cooper
Avevo pensato a una soluzione del genere, creando una classe che simulasse
un insieme e le operazioni ad esso connesse (unione, intersezione etc)
ma
poi facendo quattro conti l'ho scartata,
come l'avevi pensata per farti i 4 conti ? Spiega.
Brevemente come array di record; dove il record contiene un campo
informazione (dove appunto è memorizzato il dato) e un campo flag di tipo
booleano inizializzato a false; il primo elemento (posizione 0 dell'array)
invece contiene solo il numero di elementi effettivamente utilizzati.
Ogni qualvolta si andava a inserire un elemento il campo flag veniva posto a
true e il contatore in posizione 0 incrementato di 1; ovviamente le
informazioni sono univoche per cui se una informazione era già presente
l'inserimento veniva ignorato.
A questo punto le operazioni di unione intersezione e via dicendo
diventavano scontate mediante un processo di confronti, fra i due vettori.
L'array ovviamente era di tipo di dinamico. le liste le ho escluse a priori
perchè è vero che semplificano la scrittura del codice ma nello specifico
io puntavo alla velocità, ragione per cui non erano opportune dal momento
che una lista alla fin fine implementa sempre e comunque una struttura ad
array anche se magari non usa un array ma dei puntatori per concatenare un
elemento ad un altro.
I quattro conti li ho fatti misurando i tempi di elaborazione.
Post by Alberto Salvati
Post by Cooper
Il mio obiettivo è velocizzare il processo di elaborazione per "grandi
numeri";
Che vuol dire "grandi numeri"? Quantifica.
Significa che ci sono cicli che vengono eseguiti che nel TOTALE vengono
eseguiti nell'ordine 8 zeri.; non c'è un ciclo con otto zeri, ma diversi
cicli annidati che portano a quell'ordine di grandezza; non potendo quindi
togliere quelli più esterni potevo agire su quelli più interni tipo
l'esempio della funzione postata precedentemente.
Alberto Salvati
2010-01-04 13:17:13 UTC
Permalink
Post by Cooper
Brevemente come array di record;
dove il record contiene un campo
informazione (dove appunto è memorizzato il dato) e un campo flag di tipo
booleano inizializzato a false; il primo elemento (posizione 0 dell'array)
invece contiene solo il numero di elementi effettivamente utilizzati.
Ogni qualvolta si andava a inserire un elemento il campo flag veniva posto a
true  e il contatore in posizione 0 incrementato di 1; ovviamente le
informazioni sono univoche per cui se una informazione era già presente
l'inserimento veniva ignorato.
Tutto qui? Nessun altra idea?
Post by Cooper
Significa che ci sono cicli che vengono eseguiti che nel TOTALE vengono
eseguiti nell'ordine 8 zeri.; non c'è un ciclo con otto zeri, ma diversi
Non ho capito gli 8 zeri... vuo dire N00.000.000?
Post by Cooper
cicli annidati che portano a quell'ordine di grandezza; non potendo quindi
xche cicli annidati? fai permutazioni o cos'altro?

A.
Post by Cooper
togliere quelli più esterni potevo agire su quelli più interni tipo
l'esempio della funzione postata precedentemente.
Cooper
2010-01-04 14:19:35 UTC
Permalink
Post by Alberto Salvati
Tutto qui? Nessun altra idea?
Questa è una.
Post by Alberto Salvati
Non ho capito gli 8 zeri... vuo dire N00.000.000?
Si
Post by Alberto Salvati
xche cicli annidati? fai permutazioni o cos'altro?
Non proprio permutazioni ma dei calcoli statistici; più precisamente
parliamo di combinazioni.
Alberto Salvati
2010-01-04 15:38:41 UTC
Permalink
Post by Cooper
Non proprio permutazioni ma dei calcoli statistici; più precisamente
parliamo di combinazioni.
e non esiste qualche algoritmo che fa combinazioni senza cicli
annidati?
Mi sembra strano...Se ti basi sul n di elementi non potrai mai
generalizzare.

A.
Cooper
2010-01-04 16:41:52 UTC
Permalink
Post by Alberto Salvati
Post by Cooper
Non proprio permutazioni ma dei calcoli statistici; più precisamente
parliamo di combinazioni.
e non esiste qualche algoritmo che fa combinazioni senza cicli
annidati?
No perchè l'algoritmo non si compone di soli cicli.... alcune istruzioni
contenute all'interno dell'algoritmo contengono a loro volta altri cicli per
svolgere delle operazioni che magari non centrano nulla con l'algoritmo fine
a se stesso ma che contribuiscono a ottenere il risultato necessario per
l'algoritmo, tipo il conteggio degli elementi di un insieme che portavo a
esempio.
Post by Alberto Salvati
Mi sembra strano...Se ti basi sul n di elementi non potrai mai
generalizzare.
Infatti io non mi baso sugli n elementi.
Marco Breveglieri
2010-01-05 09:07:00 UTC
Permalink
Post by Cooper
Avevo pensato a una soluzione del genere, creando una classe che
simulasse un insieme e le operazioni ad esso connesse [...]
Non è questo ciò che ti è stato suggerito, nel senso che non ti è stato
suggerito di sostituire il set con altro, ma di inglobarlo all'interno
di una struttura che contenga e gestisca anche le informazioni
accessorie di cui hai bisogno, come il numero di elementi presenti
nell'insieme, ovviamente evitando l'accesso diretto al campo privato che
rappresenta proprio l'insieme.

Ciao,
Marco.
--
MARCO BREVEGLIERI
(http://www.marco.breveglieri.name)
Marco Breveglieri
2010-01-05 09:04:34 UTC
Permalink
Post by MBulu
- totale elementi
- set
[...]
Le soluzioni più semplici sono quelle migliori... :)
Non ci avevo nemmeno pensato... siamo messi bene... ;)

Ciao,
Marco.
--
MARCO BREVEGLIERI
(http://www.marco.breveglieri.name)
Alberto Salvati
2010-01-05 10:38:03 UTC
Permalink
Post by Marco Breveglieri
Non ci avevo nemmeno pensato... siamo messi bene... ;)
Su, Marco, su...
Sono i postumi delle megamangiate di queste festivita'.... :-D

A.
Andrea Laforgia
2010-01-05 15:51:43 UTC
Permalink
Post by Cooper
Io so l'insieme X può contenere da un minimo 0 elementi (insieme vuoto) fino
ad un massimo di 255 elementi.
Se l'insieme su cui lavori è fisso, una buona soluzione è la seguente:

var
S: set of char;
SetBytes: array [0..Sizeof(S)-1] of Byte absolute S;
I, J, ByteCard: Cardinal;

begin
S:= ['a','b','c'];
ByteCard := 0;
for I := Low(SetBytes) to High(SetBytes) do
for J := 0 to 7 do
Inc(ByteCard, (SetBytes[I] shr J) and 1);
...
--
questo articolo e` stato inviato via web dal servizio gratuito
http://www.newsland.it/news segnala gli abusi ad ***@newsland.it
Cooper
2010-01-05 16:37:47 UTC
Permalink
Post by Andrea Laforgia
Post by Cooper
Io so l'insieme X può contenere da un minimo 0 elementi (insieme vuoto) fino
ad un massimo di 255 elementi.
Per fisso intendi di dimensione fissa e contenuto variabile o di dimensione
fissa e contenuto fisso?
Post by Andrea Laforgia
var
S: set of char;
SetBytes: array [0..Sizeof(S)-1] of Byte absolute S;
I, J, ByteCard: Cardinal;
begin
S:= ['a','b','c'];
ByteCard := 0;
for I := Low(SetBytes) to High(SetBytes) do
for J := 0 to 7 do
Inc(ByteCard, (SetBytes[I] shr J) and 1);
...
Provo. Non avevo pensato agli operatori logici, una soluzione cosi mi era
tornata utile in passato per calcolare il binario di un numero usando
l'operatore shr.
Andrea Laforgia
2010-01-05 17:40:25 UTC
Permalink
Post by Cooper
Per fisso intendi di dimensione fissa e contenuto variabile o di dimensione
fissa e contenuto fisso?
Intendo che accedi sempre alla stessa variabile. Con la mia soluzione
dipendi strettamente da SetBytes, che è allocato staticamente presso il
set, in memoria. E' anche vero che potresti ovviare usando un puntatore.
Post by Cooper
Provo. Non avevo pensato agli operatori logici, una soluzione cosi mi era
tornata utile in passato per calcolare il binario di un numero usando
l'operatore shr.
In realtà puoi anche fare a meno del secondo ciclo, esplicitando gli shift
per ogni posizione.
--
questo articolo e` stato inviato via web dal servizio gratuito
http://www.newsland.it/news segnala gli abusi ad ***@newsland.it
Continua a leggere su narkive:
Loading...