Newsgroup: it.scienza.informatica
Titolo: Sort di file di grosse dimensioni

]

Salve
fammi capire: te sostieni che dato un file di n records riesci ad ordinarlo
esaminandolo solo 2 volte e con un algoritmo e non per esempio dandoci
un'occhiata?
Cioe' se hai il vettore
3 2 4 1 8 5 9 6 7
te in due passate lo ordini? ossia fai l'ordinamento in O(1)? se e' cosi' butta 
giu' due righe e brevetta il tutto perche' BG ti fara' presto da lacche'...
Cheers 
Yuri

ridottissimo della memoria.
????
Che cosa intendi per 2 passate?
Se n sono i record da ordinare, nessun algoritmo puo` fare meglio
di nlog(n). E` un limite inferiore dimostrato.
Comunque quando si devono ordinare dati contenuti in file, la
prima cosa da minimizzare sono gli accessi al disco...
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

Pape' Satan, pape' Satan aleppe, comincio' Sciasbat con voce chioccia:
S> opportuno. Ho trovano il merge sort, il multiway merge ed il poliphase
S> sorting (quest'ultimo una variante del secondo).
interessante, questi ultimi due non li ho mai sentiti nominare...
come funzionano?
S> ridottissimo della memoria. L'unico inconveniente e' che richiede su
S> disco uno spazio doppio della dimensione del file da ordinare (lavora
S> su una copia). E' il mio libro che e' vecchiotto ed ho scoperto
S> l'acqua calda (in questo caso gradirei dei reference) o sono incappato
probabilmente hai scoperto il counting sort, algoritmo di ordinamento
non basato sul confronto che richiede tempo lineare :-)
-- 
ciao,
Claudio

prima cosa da minimizzare sono gli accessi al disco...
Appunto: gli algoritmi che ho menzionato limitano gli accessi al
disco. Io riesco farlo leggendo due volte il file, il merge sort
log(n) volte (passate=scansioni file).  


 in qualcosa di interessante?
Non potresti dare qualche indicazione in piu'? Ad esempio, un po' piu'
di precisione sull'uso di risorse, la cosa mi incuriosisce .
-- 
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it
 UIN : 43385135

non basato sul confronto che richiede tempo lineare :-)
L'algoritmo e' esposto nella risposta a Davide, che aveva frainteso
cosa intendevo per "passata". Counting sort? Mai sentito, assomiglia
al radix sort?
Questo thread mi fa venire in mente una cosa: l'anno scorso, prima che
dovessi abbandonare usenet per qualche mese, su questo gruppo si
discuteva di costruire un archivio di algoritmi in pseudocodice,
commentati e divisi per il loro uso; se mi ricordo bene s'era pure
pensato di creare una ML apposita per organizzare il lavoro. Qualcuno
ne sa qualcosa od e' tutto caduto nel dimenticatoio? Se fosse cosi' io
rilancerei l'idea...


   Computer Science, University of Pisa
Ahi, ahi, ahi, signor Marotta, ma non li insegnano
piu' Algoritmi e strutture dati all'university of Pisa ? :-)
Il limite inferiore di n log(n) vale in un modello
di calcolo ben definito. Ad esempio,
e' valido se l'algoritmo puo' solo dire se una
chiave e' <, >, o = ad un altra.
Se invece il mio modello di calcolo prevede
che io possa in qualche modo sapere "quanto" una
chiave e' piu' grande di un'altra, allora le cose
cambiano.
Ad esempio, se lei suppone di dover ordinare 
n record con chiavi di ordinamento costituite
da interi non ripetuti nel range 1..c*n dove
c e' una costante, allora dovrebbe vedere facilmente
che usando un vettore di appoggio (solo per le
chiavi) di c*n posizioni, si possono banalmente
ordinare i record proprio in due passate (se vogliamo
chiamarle cosi') e comunque con un costo O(c*n)=O(n).
Piu' in generale, esiste una vasta letteratura
sulla famiglia di algoritmi di ordinamento
che vengono chiamati bucket-sort, counting-sort,
(o anche in qualche altro modo che mi sfugge).
Saluti,
Giovanni.

 (passate=scansioni file).  
Ok... avevo inteso un'altra cosa...
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

che vengono chiamati bucket-sort, counting-sort,
Onestamente ignoravo la cosa, il Bertossi all'epoca
non accenno` minimamente a nessun altra tipologia
di casi eccezion fatta per quelli "standard", ne io mi sono
ritrovato a far fronte a casi diversi da questi ultimi.
Saluti,
Paolo
P.s.
   Per favore se ti sta bene diamoci pure del tu...


L'algoritmo e' esposto nella risposta a Davide, 
Evidentemente andare a dormire alle 3 di notte non fa bene. A Yuri,
anche se non vedo ancora la risposta, benche' sia stata inviata prima
delle altre (c'e' un moderatore stocastico?^__^). Davide non da dove
spunti se non da qualche neurone ancora addormentato.


 >L'algoritmo e' esposto nella risposta a Davide, 
Chi è Davide?
A me non mi e' arrivato nulla
-- 
# Giorgio Vecchiocattivi.
# Osra Toscana srl

al radix sort?
Solo nella complessita' che e' lineare per il tempo. Counting sort, una
volta che sa di che grandezza
e' il range che contiene i numeri da sorteggiare, li tratta come indirizzi e
li spedisce direttamente al posto giusto...
.... almeno penso!
ciao
Dangermouse

giu' due righe e brevetta il tutto perche' BG ti fara' presto da lacche'...
Lo fa in O(n), se lo fa in due passate, per la precisione in un tempo 2*n.
Algoritmi come Counting Sort e Radix Sort (che ordina i numeri come se
fossero parole in un vocabolario, sorteggiando
prima le chiavi meno importanti, cioe' l'ultima cifra del numero) fanno il
tutto in tempo lineare. La velocita' si paga pero'
con un grande utilizzo di memoria.
Il tutto non e' in contrasto con il limite piu' basso teorico degli
algoritmi di sorteggiamento che vale O(n log n), perche'
questo limite e' calcolato per algoritmi che si basano sui confronti fra due
cifre del vettore.
Quindi BG continuera' a restare BG e pace all'anima nostra ;-)
ciao!
Dangermouse

 che vengono chiamati bucket-sort, counting-sort,
scusate la duplicazione, ho rispost di getto
ga
-- 
______________________________________________________________________
Guglielmo Alfieri				
dark...@inrete.it
PGP public key 
http://www.linux.it/~darklord/darklord.asc
PGP key fingerprint = 15 CC DB 37 9E A8 DF 6A  7A 89 72 05 EC 20 49 FB
"Much of the excitement we get out of our work is that we don't really
 know what we are doing."
                -- E. Dijkstra 
______________________________________________________________________

 di nlog(n). E` un limite inferiore dimostrato.
insomma...quello che tu dici e' vero per algoritmi che operano per
confronto...ci sono algoritmi, mi viene in mente il counting sort, che
sono O(n)
guglielmo


A me non mi e' arrivato nulla
Nessuno... Col secondo messaggio mi sono corretto: risposta a Yuri,
che sembra essersi persa. Pazienza, ridescrivero' l'algoritmo.


 Onestamente ignoravo la cosa, il Bertossi all'epoca
adesso pero' ha curato l'edizione italiana del
cormen-leiserson-rivest...


 # Osra Toscana srl
-- 
Ciao
Roberto
-------
Collabora alla creazione di un mondo migliore. Se ne sei capace.

Salve, non capisco...
"Evidentemente andare a dormire alle 3 di notte non fa bene. A Yuri,
anche se non vedo ancora la risposta, benche' sia stata inviata prima
delle altre (c'e' un moderatore stocastico?^__^)."
Dove sta il senso? Non vedo perche' mi si tiri in ballo "per quei scherzucci
di dozzina". La risposta al quesito e' poi affermativa dato che esiste una
lista di "trusted address" e che i messaggi da tali address sono postati senza
moderazione per cui il loro ordine dipende dalle velocita' relative dei messaggi
sulla rete.
Comunque premessa la mia ignoranza in materia di sorting vorrei capire una cosa:
quando scrivete n in espressioni come O(n) e simili intendete la dimensione
dell'input, vero? e se si come si fa a dire come sostiene Dangermouse
"Lo fa in O(n), se lo fa in due passate, per la precisione in un tempo 2*n"?
Se lo fa in O(n) che mi frega del numero di passate a meno che questi non
dipenda dalla dimensione dell'input?
Poi se non ho capito male i metodi di cui avete detto fanno ipotesi sulla
struttura dell'input
"una volta che sa di che grandezza e' il range che contiene i numeri da
sorteggiare"
e anche cio' non mi pare che li presenti come di tipo generale. Va be' mi
fermo qui, volevo piu' che altro cercare di capire il motivi per cui Sciasbat
mi ha tirato in ballo, me che a malapena cammino...:-)
Cheers 
Yuri

--
non penso proprio. Se č basato su confronti meglio di nlog(n) non puoi
ottenere, ed anche non lo fosse dubito che possa funzionare meglio del
counting sort (che prende tempo lineare ma in compenso occupa uno spazio
proporzionale al massimo intero da ordinare!).
Non č che il tuo file era gią ordinato ?
Neurictas
f...@ctonline.it
fabi...@geocities.com
http://www.geocities.com/Paris/Jardin/6726/

Le notazioni O(n), O(n^2), (che si leggono O grande di...) servono ad
indicare in modo sintetico la dipendenza di un algoritmo dalla
dimensione dei suoi dati in ingresso, in termini di operazioni.
Un algoritmo O(n) dipende in modo lineare dai suoi dati in ingresso, a
meno di costanti e/o fattori moltiplicativi; un algoritmo O(n^2)
tendera' ad effettuare un numero di operazioni che aumenteranno col
quadrato dei dati in ingresso, sempre a meno di costanti e/o fattori
moltiplicativi.
Questa notazione, insomma, da' un'idea immediata dell'efficienza di un
algoritmo.

cormen-leiserson-rivest...
Scusa l'ignoranza, ma sarebbe?
Paolo


sono O(n)
Infatti io pensavo solo ai primi, anche perche` dal contesto niente
faceva presagire che ci fossero paticolari informazioni sulla
distribuzione dei dati.


"Introduzione agli algoritmi" non ricordo l'editore inglese perche' non
ho il libro sottomano, ed italiana a cura della jackson (ovviamente 
errori a sfare...) buona panoramica e buon ricettario algoritmico
ciao
guglielmo


errori a sfare...) buona panoramica e buon ricettario algoritmico
Penso che in biblioteca l'avranno... controllero`, chissa che non
decida che valga la pena acquistarlo.
Paolo


sono O(n)
Sapete dove rintracciare qualche link o faq riguardante questi algoritmi?
Bye,
            BackSlash
--- "Se il destino ci è contro... peggio per lui."
--- Per rispondere in e-mail, togliere "abc" dall'indirizzo.