Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Algoritmo di ordinamento e compressione
Forum - Algoritmi - Algoritmo di ordinamento e compressione

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 16:53
Domenica, 01/02/2015
Io ho pensato ad un algoritmo di compressione (che forse non coprime ma espande, non saprei, dipende....)

Io pensavo di ordinare i dati con un algoritmo di compressione che effettui MENO SCAMBI POSSIBILI e poi di memorizzare il risultato come
<byte><2byte>

con <byte> che è il byte e <2byte> che è il numero di volte che un byte si ripete (2byte è a 16-bit). Una volta ottenuto questo output dal file si salva prima una lista degli scambi effettuati e poi l'output dell'ordinamento/compressione.

Per decomprimere si ri-espande tutte le sequenze di <byte><2byte> e si ripercorrono gli sbambi al contrario, così da ri-avere la sequenza originale.

Ora, io chiedo: quanto è efficente questo algoritmo (inteso come compressione)? Che algoritmo di sorting dovrei usare (quello che esegue meno scambi)? quanto sarebbe performante la DECOMPRESSIONE? e quanto la decompressione? Ho re-inventato l'acqua calda(sicuramente si, ma intanto io chiedo, visto che non so con che nome è chiamato questo algoritmo)? Quanto sarebbe performante la COMPRESSIONE (questo è il fattore che mi interessa meno)?

Non sarebbe un algoritmo tanto difficile da implementare, e per ciò che sto facendo se la decompressione fosse veloce e il ratio di compressione abbastanza buono sarebbe il top....

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6109
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 17:01
Domenica, 01/02/2015
Implementalo e fai qualche benchmark. :k:


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 17:46
Domenica, 01/02/2015
Io non so calcolare la complessità di un algoritmo, qualcuno può dirmi qualcosa? O almeno qual'è l'algoritmo di ordinamento che esegue meno scambi?

PM Quote
Avatar
Ultimo (Member)
Expert


Messaggi: 513
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 19:45
Domenica, 01/02/2015

credo che sia il Quicksort che effettua meno scambi




Ultimo (Hai voluto la bicicletta ? ....)

Studiare LINQ, WPF, ASP.NET MVC, Entity Framwork, C#, Blend, XAML, Javascript, HTML5, CSS .....(tanta roba)

https://www.dropbox.com/s/c2aots5x4urgbhf/setup_game_sudoku ...
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1127
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 20:10
Domenica, 01/02/2015
Testo quotato

Postato originariamente da TheDarkJuster: se la decompressione fosse veloce e il ratio di compressione abbastanza buono sarebbe il top....



Secondo me queste due affermazioni cozzano un po', è vero che si possono ottenere algoritmi sia veloci che preformanti dal punto di vista della compressione, ma se si vuole massimizzare uno dei due parametri bisognerebbe essere disposti a sacrificare in parte o totalmente l'altro, e sottolineo disposti e non costretti!
Comunque prova ad implementarlo e facci sapere il risultato di qualche test.


La programmazione è arte... fa che i tuoi script siano degni di un museo.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 20:14
Domenica, 01/02/2015
Sto costruendo una applicazione che ha bisogno di un tempo di decompressione eccellente, comunque con ratio di compressione abbastanza buono intendo 4/5 MB su 100MB, quello che un'altra persona reputerebbe pessimo. Forse avrei dovuto specificarlo un po' prima :D

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 20:26
Domenica, 01/02/2015
Ah, prima che io cominci a scrivere del codice, qualcuno ha idee su come ottimizzare gli scambi? Mi spiego meglio, gli scambi che ho effettuato vanno registrati, ma memorizzarli occupa spazio, come faccio a ottimizzare il numero di scambi mantenendo il risultato finale? In pratica: il quicksort fa il MINIMO INDISPENSABILE di spostamenti sempre e comunque?

P.S. in relazione al tempo di decompressione: se ci mettesse un secondo o mezzo secondo per comprimere un MB andrebbe bene, non deve essere usato per comprimere molto spesso.

Ultima modifica effettuata da TheDarkJuster il 01/02/2015 alle 20:32
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1127
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 20:27
Domenica, 01/02/2015
Vedi, tutto è relativo.

Mi permetto di farti notare che la tua implementazioni nel caso peggiore puo triplicare il peso di un byte, per non parlare dell'aggiunta di peso per l'ordinamento.

Ultima modifica effettuata da Roby94 il 01/02/2015 alle 20:30


La programmazione è arte... fa che i tuoi script siano degni di un museo.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1452
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 20:37
Domenica, 01/02/2015
Devo comprimerci modelli 3D, texture, file ficrati ecc.... Quindi gli ordinamenti saranno molti ma sarà difficile non avere ripetizioni dello stesso byte.....

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo