Newsgroup: it.discussioni.litigi
Titolo: Fuori i coglioni, quaquaraqua'!

Programmatori di database, insegnanti di informatica senza if, progettisti
virtuali di quake, visionari di .net, venite qui e vediamo quanto valete.
Domanda secca, banale: qual'e' il miglior algoritmo di sorting che
conoscete?
Gli incapaci sono pregati di astenersi e di continuare i giochini
nazionalpopolari a chi dice per primo "rodi" in altri thread.

nazionalpopolari a chi dice per primo "rodi" in altri thread.
rodi.
---
http://www.gianlucabove.com

 ha scritto:

dimenticavo: esiste anche lo shell sort (stessa complessità) ma meno
performante in media.
Precisazione importante: lo saprei scrivere, ma non l'ho mai fatto in
vita mia (se non all'università). 
Quando mi serve uso solo librerie già fatte.
---
http://www.gianlucabove.com

 con complessità logaritmica: Quick sort.
Visconte vota "Quick Sort".
Attendiamo gli altri.

 conoscete?
coglione, demente, incapace, testa di cazzo.
niubbo, incompetente, scarso.
non esiste.
idiota
appartenente ad una subrazza.
ho gia' postato su questo.
vai in gugol, cerca, infilati un dito in culo e taci.


 conoscete?
Non ne esiste uno migliore. Dipende dalle esigenze.
Un Quick Sort per ordinare 50 numeri è superfluo e uno stupido bubble è più
indicato.
Per i grandi ordinamenti voto Quick o Shell

 ha scritto nel messaggio
news:pMbib.270098$R32.8...@news2.tin.it...

dal 5 al 6.
puoi andare.

coglione.
la domanda era sul "miglior algoritmo".
E' una cosa che si studia a informatica.
Poi nella RL (rotfl) non si usa mai.
Accademia, insomma.
---
http://www.gianlucabove.com

, yello73
@
musicoff.com
 says...

U cazz, il bubble sort è imbattibile.

 ha scritto nel messaggio
news:bmbg7j$kqd8p$1...@ID-173504.news.uni-berlin.de...

1kO6a.233343$
0v.65...@news1.tin.it
per esempio, mio piccolo mostro di plastica.


ha scritto:

meglio il comando qsort().
---
http://www.gianlucabove.com

 meglio il comando qsort().
PArlavo di algoritmi non di implementazioni.
Intendevi il quick sort?

Intendevi il quick sort?
no, è un istruzione di base del C (ANSI). Non so cosa faccia dietro,
ma lo fa bene e veloce.
Non ho mai dovuto perdere tempo a pensare quale algoritmo scegliere,
insomma.
---
http://www.gianlucabove.com

 non esiste.
Charlie vota "non esiste".
Bene... chi tocca ancora?

 insomma.
Evidentemente perchè il tuo lavoro era di un certo livello.

 ha scritto nel messaggio
news:pMbib.270098$R32.8...@news2.tin.it...

BluDiesel vota "Dipende dalla numerosita' dei dati, sopra una certa cifra
Quick, sotto qualcos'altro"

 dipende da quello che cazzo devi fare, subdemente. dipende
Alkatraz vota "dipende"

 
Questa pero', in termini computaizonali, č una boiata.

 insomma.
Se devi ordinare dati in una struttura o te lo fai il quick sort o la tieni
random

 Questa pero', in termini computaizonali, è una boiata.
Sergio sostiene che la numerosita' dei dati, in termini computazionali, non
cambia l'efficienza dell'argomento.

, 
fatt...@yahoo.com
 says...

Nessuno ha parlato di argomenti.

 ha scritto nel messaggio
news:bmbil4$kppkr$1...@ID-173504.news.uni-berlin.de...

AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH
AHHAHAHAHAAHHAAHAHAHHAHAHAHAHAAHAH

 Nessuno ha parlato di argomenti.
Algoritmo, typo.

, 

Allora sě, č quello che ho detto.

 ha
scritto:

conosci le rogue waves?
Anche se basterebbero le STL di GNU.
---
http://www.gianlucabove.com

 Anche se basterebbero le STL di GNU.
E che ne dici delle GPRS delle SMS nell'ambito delle VIP della GU?

E che ne dici delle GPRS delle SMS nell'ambito delle VIP della GU?
ah, scusa. Tu sei un programmatore java, l'avevo dimenticato.
---
http://www.gianlucabove.com


Tu sarai un programmatore, io sono un analista.

Tu sarai un programmatore, io sono un analista.
ti eri offeso?
---
http://www.gianlucabove.com

 
Certo il progrmmatore č un lavoro da diplomati.


ha scritto:

e il project leader?
---
http://www.gianlucabove.com

, yello73

Quella č una scelta di vita.

Quella è una scelta di vita.
ma un diploma potrebbe bastare, secondo te?
---
http://www.gianlucabove.com

conoscete?
Domanda da coglione.
Qual'e' la quantita' di dati da ordinare?

E' una cosa che si studia a informatica.
A informatica, se hai avuto un professore degno di tal nome e se sei
stato presente alla lezione, avranno sicuramente detto che non esiste
in assoluto un algoritmo di ordinamento piu' veloce degli altri.

 conoscete?
Indubbiamente l'a-sor-t
S:>>>
-- 
Sei su IDL, qui si scherza: non prendertela
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

conoscete?
De Poli (1) - De Poli (2).
Eppercortesia finiamola con 'ste tristezze.
-- 
Nadja Jacur

 ha scritto nel messaggio
news:vdijov0h1g214iqbk...@4ax.com...

De Poli? Ettecredo.
Io avevo orsetto Bilardi, ed ancora ne ho nostalgia.
L'uomo piu' mansueto della terra.
Una volta si e' fatto "flammare" dalla moglie, davanti a noi. "Tu sei un
cretino!!! Deficiente!!!" "oh oh oh..cara... ma io..."
Pippo.

cretino!!! Deficiente!!!" "oh oh oh..cara... ma io..."
Che brav'uomo. Chissa' cosa fanno gli insegnanti di info nel loro
tempo libero...
-- 
Nadja Jacur

 Sono certo: sei un idiota.
Dipende dai punti di visti.
(Peer Gynt, 6 Ottobre 2003)

conoscete?
Dipende: per un numero non troppo elevato di interi, ce n'e' uno
particolarmente furbo che nessuno di voi, programmatori della
domenica, ha nominato (anche perche' non ha un nome) e che risolve il
problema con complessita' O(1). Or ora lo scrivero' in un
pseudolinguaggio:
supponiamo che il vettore da ordinare contenga interi positivi (cioe'
naturali) da 0 a NMAX.
for ($i=0; $i<=NMAX; $i++):
	$vettorerisultato[$i]=0;
end for;
for ($i=0; $i<dimensione($vettoredaordinare); $i++):
	$vettorerisulato[$vettoredaordinare[$i]]+=1;
end for;
alla fine, se $vettoredaordinare era, per esempio:
(10,4,8,2,4)
allora, $vettorerisulato sara' fatto cosi':
0 -> 0
1 -> 0
2 -> 1
3 -> 0
4 -> 2
5 -> 0
6 -> 0
7 -> 0
8 -> 1
9 -> 0
10 -> 1

 naturali) da 0 a NMAX.
Grazie: se il dominio e' limitato sono gia' di per se stesso ordinati.
Basta che pensi alla tombola, man mano che li estrai li metti nel tabellone
nella casellina, e alla fine sono ordinati.
Ma parlando di un insieme il cui dominio e' illimitato, con n elementi ci
si mette non meno di n log n. E' dimostrato matematicamaente.


si mette non meno di n log n. E' dimostrato matematicamaente.
Un insieme dal dominio illimitato non e' rappresentabile da un
elaboratore.

si mette non meno di n log n. E' dimostrato matematicamaente.
dimenticavo: questo lo so. Ho studiato anch'io informatica.



ed il tuo algoritmo va bene solo per dominii estremamente piccoli.
Chi citava i numeri interi a 32 bit, ad esempio, non ha poi aggiunto che
per ordinarli in tempo n, occorrono 2^64 bytes di ram, e questo solo nel
caso in cui i numeri siano tutti diversi tra loro, altrimenti ce ne vuole
anche di piu'.
Quindi se parliamo di modelli, e di teoria, vale quanto ti ho detto.
Parlando di pratica vale comunque quel che ti ho detto, visto che quando
devi ordinare qualcosa, tranne casi banali (la tombola, il mazzo di carte)
in ogni caso ti devi affidare ad algoritmi bastati sul confronto & scambio,
e da li nlogn, non c'e' nulla da fare.


ed il tuo algoritmo va bene solo per dominii estremamente piccoli.
chiaramente e' limitato, ma all'interno di questi limiti caga in testa
a qualsiasi altro algoritmo: O(1).
BTW, definiamoli questi limiti:
un intero da 4 byte rappresenta da -
2147483648
 a 
2147483647
 .
Visto che stiamo parlando di naturali, allora siamo sui 2^32, cioe'
4294967296, numeri. Ma, in realta', dobbiamo fare i conti anche con la
RAM, e quel 2^32 deve essere moltiplicato per 2^2 (bytes necessari per
rappresentare un intero): 2^34 bytes, cioe' 2^24 kbytes, 2^14, 2^4
giga: effettivamente, un po' troppo.
Ci si dovrebbe accontentare di interi senza segno a 2 byte.

Ci si dovrebbe accontentare di interi senza segno a 2 byte.
ci ho ripensato: ho trovato un modo per superare il limite della
memoria. Resta il solo vincolo sull'essere numeri naturali.
Il trucco e' semlice: in PHP, si possono fare cose di questo tipo:
$vettore=array();
$vettore[5]=6;
$vettore[20]=1;
e' il risultato e' questo:
Array ( [5] => 6 [20] => 1 ) 
A questo punto, il vettore risultato dell'esempio fatto prima sara':
2 -> 1
4 -> 2
8 -> 1
10 -> 1
mentre array[i] non sara' definito per i non appartenente all'insieme
{2,4,8,10}.
Quindi, nessun problema di RAM ;-)

 Ci si dovrebbe accontentare di interi senza segno a 2 byte.
Io stavo cercando di ricordare la dimostrazione di nlogn. Son passati
anni..
Si partiva senz'altro dalla considerazione che dati n elementi, possono
essere disposti in n! modi, e dalla considerazione che un'operazione di
confronto/scambio poteva avere due esiti: il confronto da esito positivo, e
la permutazione rimane invariata, il confronto da esito negativo, si
scambiano due elementi tra loro e si ottiene un'altra permutazione.
Alla fine si riusciva a costruire un albero binario rovesciato (e purtroppo
non ricordo come), dove le foglie sono le n! possibili configurazioni
iniziali, la radice e' l'unica configurazione finale possibile.
Quest'albero, per come e' configurato (ripeto, non ricordo i dettagli),
rappresenta tutti i possibili algoritmi di ordinamento su quegli n dati, e
un percorso qualsiasi dalla foglia alla radice ne rappresenta
un'implementazione.
Ora ogni percorso ha una lunghezza maggiore dell'altezza dell'albero
(teorema di pitagora), e l'altezza dell'albero e' pari al logaritmo in base
due del numero di foglie, quindi log n!. 
Da qui e' semplice: n! = n(n-1)(n-2)...1 < n*n*n...*n, quindi n! < nexp(n),
da qui log n! < log (nexp(n))= nlog(n)


 anni..
Io, che sono un ricchione, mi accontento di questo, invece.
PhFree
-- 
xxx
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG



Ma problema di tempo.
Tu usi una feature del PHP (array associativi).
Un array associativo ha un tempo di lettura non immediato. Per andare a
leggere l'elemento i-esimo, se li deve scandire tutti. 


[snip]
Dovrei cercare sugli appunti o avere voglia di seguire la tua traccia.

 ha
scritto:

senti un po', ma non sarà ora di trovarti un lavoro?
-- 
http://www.gianlucabove.com

 $vettorerisultato[5]=15
Secondo me fai un errore di fondo: ti affidi a linguaggi ad alto livello di
cui non conosci l'implementazione fisica.
$vettorerisulato[$vettoredaordinare[$i]]+=1;
e
$vettorerisultato[5]=15
che complessita' hanno? costante?


leggere l'elemento i-esimo, se li deve scandire tutti. 
Alla fine dell'algoritmo, bisognerebbe trasformare l'array associativo
in un array normale. A questo punto pero', sarebbe il caso di
riconsiderare la complessita'.

 a leggere l'elemento i-esimo, se li deve scandire tutti.
No. (a meno che in php le hash siano implementata proprio alla cazzo)
-- 
Saluti,
Giancarlo

 No. (a meno che in php le hash siano implementata proprio alla cazzo)
Bene bisso, visto che parli ostentando sicurezza, ti do un compito.
Sacchettino della tombola, con 90 numeri dentro.
Tabellone, nel quale puoi tracciare x cerchietti.
Estrai diciamo 10 numeri.
Ogni numero estratto lo devi posare su uno di questi cerchietti.
L'atto del posizionamento di un numero su un cerchietto e' considerata 
un'operazione elementare, l'atto di spostare un numero da un cerchietto ad 
un altro, un'altra operazione elementare. Se scambi tra loro due numeri 
idem: operazione elementare.
Alla fine di tutto, i 10 numeri devono essere ordinati.
Calcolami il numero x di cerchietti che ti servono per far si' che il tuo 
algoritmo abbia, per qualsiasi combinazione dei 10 numeri estratta, un 
numero di operazioni elementari minori di 10*log 10, ovvero 34 operazioni 
elementari.


PdG wrote:

Non ho caputo un cazzo, PdG. Cazzo sono i cerchietti?
-- 
Saluti,
Giancarlo

un'operazione elementare
piu' che altro, l'utilizzo degli array associativi sposta il problema
della complessita'. Se, prima, l'operazione computazionalmente
importante ero lo scambio di due elementi di un array, qua potremmo
considerare, come operazione elementare, l'accedere ad un elemento
dell'array. Questa e' la via che intraprenderebbe un europeo.
Un americano, invece, farebbe dei benchmark.