Newsgroup: it.scienza.informatica
Titolo: Sort II...

]

Bello!
Per cui se ho
3 1 4 2 6 5
e lo spezzo in 3
ho
3 1
4 2
6 5
gia' ordinati (in ordine decrescente) a questo punto prendo i valori
piu' piccoli in ogni pezzo e li metto nel file globale  ed ho
1 2 5 
e alla passata dopo
1 2 5 3 4 6 
Bello, non c'e' che dire...
Se per caso prendessi i piu' grandi avrei
3 4 6 1 2 5
I blocchetti li puoi anche ordinare in locale ma poi li dovresti ordinare fra 
loro e dato che m lo scegli in funzione di n (ad esempio n/3) non 
sai a priori il range di valori di ognuno dei pezzetti... per cui se 
anche li ordini non puoi sapere se il range di uno non si sovrappone
con quello di altri
Ad esempio anche se ordinasi in base al primo valore avrei la stessa situazione
di sopra ma 3 1 e 4 2 sono intervalli che si sovrappongono...
Cheers
Yuri

 localmente uno ad uno.
Quindi il file è ordinato a blocchi.
Non funziona.
--
Alessandro Monti

di sopra ma 3 1 e 4 2 sono intervalli che si sovrappongono...
No, non ne prendo uno per pagina, ma il minore fra i primi di tutte
le pagine (posso quindi continuare a prendere dalla stessa, vuotarla e
ricaricarla senza mai toccare le altre). Cosi' funziona e bene ^__^
indipendentemente dalla sovraposizione dei range. Provare per
credere...  


Non funziona.
E leggere anche il resto, da "Seconda passata" in avanti...?


]
Vediamo un'analisi della complessitą del tuo algoritmo...
Le "passate", come dici tu, sono due. Daccordo.
Prima passata: suddivisione della della lista numerica in m blocchi. O(n)
Seconda passata: O(m*(n/mlog(n/m)))=O(nlog(n/m)) (nel caso migliore) + O(n)
bello!
Meglio del merge sort!
Se solo non fosse che NON FUNZIONA!!!
4 6 7 10 14 2 1 7 20 31 3 60
m=3
4 6 7 10
14 2 1 7
20 31 3 60
quindi...
1 3 4 2 6 20 7 7 31 10 14 60 !!!!!!!!!(?)
Neurictas
f...@ctonline.it
fabi...@geocities.com
http://www.geocities.com/Paris/Jardin/6726/

1 3 4 2 6 20 7 7 31 10 14 60 !!!!!!!!!(?)
No, i blocchi innanzi tutto sono ordinati
quindi
4 6 7 10
1 2 7 14
3 20 31 60
Supponiamo che le pagine (la lettura potrebbe avvenire anche a singolo
record, ma si velocizza molto leggendo per pagine od entita' piu'
grandi sino alla siturazione della RAM) contengano due record. Ne
carico quindi una per blocco
ed ho in meoria:
4 6
1 2
3 20
A questo punto, secondo l'algoritmo, _seleziono ad ogni passo il
minore tra i primi record di ogni pagina_ (questo e' il punto
fondamentale, non tutti i primi di tutte le pagine come hai fatto tu),
quindi nel primo ciclo ho 1
In memoria resta:
4 6
2
3 20
Nel secondo ciclo non seleziono ne' 4 ne' 3, perche' tutte le pagine
sono "aperte" e quindi il minore e' il primo della pagina relativa al
secondo blocco, quindi il 2
A questo punto la pagina del secondo blocco e' vuota e carico la
pagina successiva del blocco, che e' 7 e 14, avendo cosi' in memoria:
4 6
7 14
3 20
Si selezioneranno quindi nei passi successivi il 3, il 4, il 6 e
quindi avverra' la lettura della pagina successiva del primo blocco e
cosi' via, esattamente come descritto nello pseudocodice nel messaggio
originale (magari un po' piu' di attenzione...)


credere...
Scusami per il precedente mio post, sotto. In effetti funziona il tuo
algoritmo, ma ti voglio mostrare che non č tanto meglio del merge sort.
Vedi, l'importante in un algoritmo non sono le "passate", come dici tu, ma
quello che succede in queste passate.
Allora:
Prima passata: O(n) operazioni. Perchč non fai altro che scorrere tutta la
lista e creare gli m gruppi  (ognuno formato da n/m elementi).
Seconda passata: ordiniamo con il merge sort gli m gruppetti:
O(m*n/m*log(n/m))=O(nlog(n/m))=O(nlogn)-O(nlogm).
Fin quě potrebbe sembrare meglio del mergesort, perchč si effettuano
O(nlogm) confronti in meno. Il problema invece č che questi confronti li
recuperi tenendo in considerazione le O(n) operazioni iniziali e gli
O(m) confronti finali, quando confronti tutti i minimi fra gli m gruppi.
In sostanza, sinceramente, č matematicamente impossibile che il tuo
algoritmo
ordini in meno di O(nlogn).


> E leggere anche il resto, da "Seconda passata" in avanti...?
Troppa fatica, è già chiaro che non funziona.
Per essere più precisi, funziona (forse) solo se puoi caricare in memoria
tutti i blocchi, oppure se l'ordinamento per blocchi che hai già fatto è
anche un ordinamento totale, altrimenti non funziona, e per rimediare non
puoi fare altro che fare altre passate o aumentare la memoria.
A meno che tu non intenda che la lettura di un blocco da disco non sia da
conteggiare come "passata", e allora hai ragione.
Se proprio sei così convinto, non devi fare altro che generare un file
contenente numeri casuali in quantità sufficentemente alta e provare ad
ordinarlo, poi dicci.
Se poi tenessi anche un contatore delle letture che fai, meglio ancora.
Nota: se hai 128M di RAM, e una dimensione di memoria virtuale illimitata,
forse è meglio se fai le prove sotto DOS, così un file di 640K può bastare.
--
Alessandro Monti

ordini in meno di O(nlogn).
Infatti non e' questo il punto (anche il merge sort essendo specifico
per file su disco ha una complessita' maggiore di n*log(n)
Questo ad occhio e', se m e' la lunghezza di un blocco:
n/m*m*log(m) nella prima passata => n*log(m)
Nella seconda occorre fare n estrazioni tra i piu' piccoli di ogni
pagina; con uno schema a "torneo" per la selezione, il costo ad ogni
ciclo e' solo quello dell'iserzione di un nuovo elemento ogni volta
quindi log(n/m); La seconda passata ha quindi complessita' n*log(n/m)
=n*log(n)-n*log(m).
Sommando, se non ho scritto bestialita' (potrei aver sbagliato
quslcosa, mi sembra bassa ad occhio, ma forse di mezzo ci sono delle
costanti trascurate che fanno lievitare leggermente il costo), viene
esattamente n*log(n), come d'altronde di meglio non ci si poteva
aspettare, ma con il notevole vantaggio di fare solo due scansioni del
file su disco...


ordini in meno di O(nlogn).
Su questo non ci sono dubbi, per algoritmi basati sul confronto e' il
minimo teorico. Non so che complessita' abbia il merge sort, ma e'
prob. che sia maggiore di nlogn; il suo dato caratteristico, essendo
un algoritmo pensato per ordinare i file su disco e' che richiede
"sole" log(n) letture del file (come avevo detto nel thread precedente
ci sono varianti che che riducono il costo di un fattore logm). Il mio
invece ne richiede 2 (se il file ha un milione di record, comunque
pochi per il campo di applicazione, il merge sort ne richiede 20 !).
Inoltre se non ci sono errori la complessita' del mio e' nlogn
Infatti (quelle che tu chiami le prime due passate sono in realta'
una: la suddiviione in blocchi avviene ordinando quello che si trova,
non ha senso leggere il file per suddividerlo semplicemnte in
blocchi), quindi:
	m*n/m*log(n/m) =n*log(n)-n*log(m)
Il secondo passo richiede la selezione dei minimi; con una tecnica a
"torneo", il costo per ogni selezione e' il semplice inserimento
nell'albero di selezione, ovvero
	log(m)
Questo e' da fare n volte, quindi il costo del secondo passo e'
	n*log(m)
Per un costo complessivo di n*log(n)
Probabilmente in mezzo c'e' qualche costante che fa lievitare
leggermente la complessita', ma poco importa, la sua peculiarita' sono
le due passate :)


}
Allora si hanno n/p letture e n/p scritture quindi ancora O(n). Tutto
a posto quindi?
Errore, questo funziona solo se e' possibile tenere in memoria n/(b*p)
pagine, cioe' una pagina per blocco. Se la memoria non basta a far
cio' non ci e' possibile scegliere il record piu' piccolo senza
accedere al disco.
In pratica il tuo algoritmo funziona solo se:
n/(b*p) < m/p --> n < (m*b)
Dato che deve essere b < m/p . Si ha:
n < (m^2)/p
Ovvero la quantita' di memoria (non disco) necessaria aumenta con la
radice della dimensione del disco (p e' costante).
Se si ha che n > (m^2)/p e' necessario modificare il tuo algoritmo
introducendo piu' passate.
Scoprirai che alla fine ottieni circa O(log(n)) passate, che
moltiplicato per O(n) che e' il costo di ogni passata ottieni proprio
O(n log(n)).
Quello che ti ha tratto in inganno e' che la base del logaritmo (che
dipende dalla quantita' di memoria disponibile) e' molto grande e
quindi se non consideri file molto (e ripeto molto) piu' grandi della
memoria si ha che log(n) < 1 e riesci a fare il tutto in un'unica
passata.
Considra una memoria di 1Mb, record di 1Kb e pagine di 4Kb. Il tuo
algoritmo smette di funzionare quando n (num. di record) e' maggiore
di:   (m^2)/p = (1K)^2 / 4K = 1M/4K = 256K
ovvero quando hai un file piu' grande di 256 Mb.
Se avevi 10 Mb di memoria arrivavi fino a circa 25 Gb.
Andrea Polci
apo...@geocities.com