Doppioni in un vettore
Salve a tutti quelli della community,
Sto facendo un programma sul matlab e ad un certo punto devo verificare che un certo vettore b non contenga elementi uguali...
La prima idea è stata di prendere 2 cicli for e un ciclo if (come ho imparato a fare col c++)
Solo che mi pare troppo strano che un programma all'avanguardia come il matlab non abbia una function + compatta...
Se esiste, qualcuno me la saprebbe indicare?
Vi ringrazio anticipatamente,
Andrea
Sto facendo un programma sul matlab e ad un certo punto devo verificare che un certo vettore b non contenga elementi uguali...
La prima idea è stata di prendere 2 cicli for e un ciclo if (come ho imparato a fare col c++)
Solo che mi pare troppo strano che un programma all'avanguardia come il matlab non abbia una function + compatta...
Se esiste, qualcuno me la saprebbe indicare?
Vi ringrazio anticipatamente,
Andrea
Risposte
Potresti sfruttare l'ordinamento del vettore.
Dopo ordinato con un semplicissimo ciclo verifichi che ogni elemento non sia uguale al successivo.
Cosi' facendo potresti anche sapere quanti doppioni ci sono, ed eventualmente anche la frequenza delle ripetizioni.
Dopo ordinato con un semplicissimo ciclo verifichi che ogni elemento non sia uguale al successivo.
Cosi' facendo potresti anche sapere quanti doppioni ci sono, ed eventualmente anche la frequenza delle ripetizioni.
Giusto!!
Applico sort(b) e quindi ci schianto un ciclo for che mi controlla l'uguagliaza... Grazie mille Umby!^^
Applico sort(b) e quindi ci schianto un ciclo for che mi controlla l'uguagliaza... Grazie mille Umby!^^
non mi pare un gran che come soluzione
cioè
se ti interessa solo la compattezza e la chiarezza del codice potrebbe(e anche qua ho i miei dubbi) essere una soluzione accettabile
ma da un punto di vista della complessità computazionale non mi pare un gran che
il sort infatti è al massimo un nlogn, se poi dopo il sort vai fare un ciclo per controllare che tutti gli elementi non abbiano doppioni hai un altro n
è vero che asintoticamente hai un algoritmo nlogn ma...
scusa prima di continuare...hai altri vincoli alle hp?ad esempio i numeri contenibili nel vettore sono appartenenti ad un insieme limitato?
cioè
se ti interessa solo la compattezza e la chiarezza del codice potrebbe(e anche qua ho i miei dubbi) essere una soluzione accettabile
ma da un punto di vista della complessità computazionale non mi pare un gran che
il sort infatti è al massimo un nlogn, se poi dopo il sort vai fare un ciclo per controllare che tutti gli elementi non abbiano doppioni hai un altro n
è vero che asintoticamente hai un algoritmo nlogn ma...
scusa prima di continuare...hai altri vincoli alle hp?ad esempio i numeri contenibili nel vettore sono appartenenti ad un insieme limitato?
Un altro metodo potrebbe essere quello di verificare se
length(unique(b)) == length(b)
unique infatti trova tutti gli elementi di b, senza ripetizioni. Immagino che internamente faccia comunque un internamento. n*log(n) + n è comunque inferiore alla complessità n^2 dell'algoritmo naif. Non mi vengono in mente algoritmi con complessità inferiore (tranne forse quello di creare un albero binario con gli elementi dell'array).
length(unique(b)) == length(b)
unique infatti trova tutti gli elementi di b, senza ripetizioni. Immagino che internamente faccia comunque un internamento. n*log(n) + n è comunque inferiore alla complessità n^2 dell'algoritmo naif. Non mi vengono in mente algoritmi con complessità inferiore (tranne forse quello di creare un albero binario con gli elementi dell'array).
si ma qua stai parlando di complessità asintotica
per piccoli numeri non è detto che l'algoritmo naif sia peggiore di quello nlogn+n
stavo chiedendo se c'erano altri vincoli perchè ad esempio se i numeri fosser per dire < 100 si potrebbe creare un array di bool da 100 (o più piccolo ma gestito con una funzione hash e fatto da piccole liste ma qua si va in là...) elementi e porre ad 1 l'elemento corrispondente a quello trovato
questa soluzione sarebbe applicabile nel caso di n interi e limitati come dicevo ma quantomeno sarebbe O(n)
se fossero ponibili altri vincoli si potrebbe pensare un algoritmo migliore
per piccoli numeri non è detto che l'algoritmo naif sia peggiore di quello nlogn+n
stavo chiedendo se c'erano altri vincoli perchè ad esempio se i numeri fosser per dire < 100 si potrebbe creare un array di bool da 100 (o più piccolo ma gestito con una funzione hash e fatto da piccole liste ma qua si va in là...) elementi e porre ad 1 l'elemento corrispondente a quello trovato
questa soluzione sarebbe applicabile nel caso di n interi e limitati come dicevo ma quantomeno sarebbe O(n)
se fossero ponibili altri vincoli si potrebbe pensare un algoritmo migliore
Certamente. Credo si tratti però di un esercizio universitario e che qualsiasi soluzione, anche la più lenta, sia sufficiente.
si, si fa per un po' di sollazzo intellettuale XD
Ringrazio tutti per l'interesse... ^^ il livello a cui per ora mi affaccio è quello... ^^...
Beh, secondo me la soluzione di dzcosimo è molto intelligente, e potrebbe essere applicata in questo modo:
[list=1]
[*:386rn13u]Trovare l'elemento più grande del vettore (chiamato $max$)[/*:m:386rn13u]
[*:386rn13u]Creare un vettore di $max+1$ elementi booleani (chiamato $vet2$), in modo che gli indici $i$ del vettore siano $0 <= i <= max $[/*:m:386rn13u]
[*:386rn13u]Scorrere il vettore originario (con un contatore $k$, ad esempio) e porre $vet2=1$ quando $vet[k]=i$[/*:m:386rn13u]
[*:386rn13u]Se si incontra un elemento $vet2$ già uguale a 1 durante il ciclo, esso termina[/*:m:386rn13u][/list:o:386rn13u]
In questo modo, si hanno due cicli, entrambi con, al massimo, complessità $O(n)$ (almeno credo).
Quindi, complimenti dzcosimo !!
[list=1]
[*:386rn13u]Trovare l'elemento più grande del vettore (chiamato $max$)[/*:m:386rn13u]
[*:386rn13u]Creare un vettore di $max+1$ elementi booleani (chiamato $vet2$), in modo che gli indici $i$ del vettore siano $0 <= i <= max $[/*:m:386rn13u]
[*:386rn13u]Scorrere il vettore originario (con un contatore $k$, ad esempio) e porre $vet2=1$ quando $vet[k]=i$[/*:m:386rn13u]
[*:386rn13u]Se si incontra un elemento $vet2$ già uguale a 1 durante il ciclo, esso termina[/*:m:386rn13u][/list:o:386rn13u]
In questo modo, si hanno due cicli, entrambi con, al massimo, complessità $O(n)$ (almeno credo).
Quindi, complimenti dzcosimo !!
grazie
in effetti facendo come dici te lo si può applicare nel caso generale
certo se i numeri sono troppo sparsi sull'asse Z risulta comunque inefficiente dal punto di vista della memoria(parametro in genere trascurabile rispetto al tempo al giorno d'oggi)
comunque si deve imporre il vincolo che i numeri appartengano agli interi se no il metodo risulta comunque inapplicabile
a meno di discretizzare l'intervallo in diverse parti con distanza fra loro minore dell'errore tollerato per controllare l'uguaglianza fra i reali...credo che così potrebbe funzionare che dite?
in effetti facendo come dici te lo si può applicare nel caso generale
certo se i numeri sono troppo sparsi sull'asse Z risulta comunque inefficiente dal punto di vista della memoria(parametro in genere trascurabile rispetto al tempo al giorno d'oggi)
comunque si deve imporre il vincolo che i numeri appartengano agli interi se no il metodo risulta comunque inapplicabile
a meno di discretizzare l'intervallo in diverse parti con distanza fra loro minore dell'errore tollerato per controllare l'uguaglianza fra i reali...credo che così potrebbe funzionare che dite?
"dzcosimo":
grazie
in effetti facendo come dici te lo si può applicare nel caso generale
certo se i numeri sono troppo sparsi sull'asse Z risulta comunque inefficiente dal punto di vista della memoria(parametro in genere trascurabile rispetto al tempo al giorno d'oggi)
comunque si deve imporre il vincolo che i numeri appartengano agli interi se no il metodo risulta comunque inapplicabile
a meno di discretizzare l'intervallo in diverse parti con distanza fra loro minore dell'errore tollerato per controllare l'uguaglianza fra i reali...credo che così potrebbe funzionare che dite?
Per la cosa della memoria si potrebbe calcolare a priori il coefficiente di variazione (definito come il rapporto fra deviazione standard e media aritmetica) e scegliere, in base al suo valore, quale metodo applicare ...
Per quanto riguarda i reali si potrebbe certamente fare così, ma sarebbe un "suicidio"... Infatti, se, ad esempio, avessi il vettore $vet=[1,2,3,4,5.642335,6]$, dovresti prendere come "mattone di base" (non mi ricordo come si chiami ... ragione della serie?) il numero $0.000001$ e creare un vettore che sia così di $6*10^6$ (sei milioni) di elementi !!!
no scusa non mi sono spiegato allora
informaicamente parlando due numeri reali sono uguali se
errore relativo fra i due numeri minore valore prefissato(questo per tenere di conto dei vari errori di arrotondamento)
quindi la dim dei vari intervallini veniva ad essere minore del doppio di questo errore prefissato
informaicamente parlando due numeri reali sono uguali se
errore relativo fra i due numeri minore valore prefissato(questo per tenere di conto dei vari errori di arrotondamento)
quindi la dim dei vari intervallini veniva ad essere minore del doppio di questo errore prefissato
"pengo":
Trovare l'elemento più grande del vettore (chiamato $max$) Creare un vettore di $max+1$ elementi booleani (chiamato $vet2$), in modo che gli indici $i$ del vettore siano $0 <= i <= max $ Scorrere il vettore originario (con un contatore $k$, ad esempio) e porre $vet2=1$ quando $vet[k]=i$ Se si incontra un elemento $vet2$ già uguale a 1 durante il ciclo, esso termina
Hai messo una serie di limiti al quesito iniziale che il quesito stesso non aveva, ovvero:
Il vettore contiene numeri positivi.
Non decimali
Non eccessivamente grandi
In linea generale, non trovo corretto indicizzare un vettore con il contenuto di un campo,
ovviamente, se l'utente, conosce come si compone il vettore potrebbe usare questo metodo..
L'uso dell'array non è sempre ottimale (soprattutto dal punto di vista della memoria). Inoltre potrebbe essere difficile usare questo metodo con tipi più complicati come punti nello spazio (mi è in effetti capitato di scrivere una funzione che eliminasse i duplicati da una mesh poligonale). Più in generale è possibile affiancarsi ad una qualche struttura dati di supporto (che può essere un semplice array o un albero o una tabella di hash...). Se l'inserimento e l'accesso ad un elemento può essere effettuato in O(1), allora l'algoritmo finale avrà complessità O(n) come nel vostro caso. Nei casi più complessi una tabella di hash è meglio di un array.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo