Keskustelu: Ohjelmointikysymykset: PHP, QB, VB6: Lukujen vertaaminen?

Mikä olisi paras tapa verrata erillaisia lukuja ja esim. lajitella ne pienimmästä suurimpaan?

http://www.norrahammarsmek.se/coelurus/program/sort.c -> fastsort, helppo portata.

Minä olen keksinyt tällaisen algoritmin. Ei välttämättä nopein, mutta ainakin toimii.

Private Sub Form_Load()

Dim luku(1 To 8)  'taulukoidaan luvut
luku(1) = 5: luku(2) = 20: luku(3) = 16: luku(4) = 2
luku(5) = 17: luku(6) = 22: luku(7) = 14: luku(8) = 9

Form1.Show   'formi näkyviin

For i = 1 To 8
  Print luku(i)    'tulostetaan sekalainen järjestys
Next i
Print

For i2 = 1 To 7    'järjestys alkaa...
For i = 1 To 7
  If luku(i) > luku(i + 1) Then
    temp = luku(i)
    luku(i) = luku(i + 1)
    luku(i + 1) = temp
  End If
Next i
Next i2    '...ja loppuu

For i = 1 To 8
  Print luku(i)   'tulostetaan järjestelty lukujoukko
Next i

End Sub

Edit: Tuota voi kyllä optimoida niin, että järjestämisessä kuluu sitä vähemmän aikaa, mitä paremmassa järjestyksessä luvut jo ennestään ovat.

Tässä taasen olisi QuickSort QBasicille:
https://www.ohjelmointiputka.net/koodivinkit/23441-qb-quicksort-lajittelu

Hm... ainakin jotain järkevää olen tehnyt tuota omaa algoritmiani suunnitellesani, kun siinäkin on mukana tuossa QuickSortissa käytetty SWAP-komento. (sitä ei siis VB:stä löytynyt, joten tein oman kolmirivisen korvikkeen tuohon koodiin)

Hunajavohveli: Tuo lienee bubblesort-algoritmi. Joku on tainnut keksiä sen jo vuosikymmeniä sinua aikaisemmin :)

Itseasiassa tuo hunajavohvelin algoritmi on n. puolet hitaampi kuin usein käytetty bubblesort ja se menee aikavaatimukseltaan luokkaan O(n^2), eli järjestämiseen vaadittava aika on suoraan verrannollinen järjestettävien alkioiden neliöön!

Jos järjestettävänä on esimerkiksi 100 alkiota ja yhteen vaihtamiseen kuluu aikaa n. 10^-8 sekuntia (= 10000 mikrosekuntia), niin taulukon järjestämiseen kuluu aikaa n. (10^-8)/(100^2) sekuntia = 10^-4 sekuntia = 0,1 millisekuntia, joka ei vielä ole paljoa.
Jos järjestettävänä on vaikkapa 10^5 (=100000) alkiota, niin koko taulukon järjestämiseen kuluisikin aikaa (10^8)/((10^5)^2) sekuntia = 10^2 sekuntia = 100 sekuntia, eli *hieman* turhan pitkä aika...

Quicksort taas on melko paljon vaikeampi koodata, mutta siinä aikavaatimus on vain luokkaa O(n log n), eli n * (kaksikantainen) logaritmi n:stä.
100 alkiota järjestettäessä ero bubblesortin ja quicksortin välillä on n. 15 kertainen, mutta 10^5 alkiolla ero on jo reilusti yli 1000 kertainen!

Tämän takia bubblesortia kannattaakin mielestäni käyttää vain, jos järjestettävä taulukko on riittävän pieni (<100 alkiota), koska silloin aikaero bubblesortin ja quicksortin välillä on vain muutamia sekunnin tuhannesosia tai jopa alle.
Toinen tapaus, missä käytän yleensä bubblesortia hieman isompienkin taulukoiden kanssa on, jos ohjelma on tarkoitettu ajettavaksi vain kerran tai pari, koska bubblesort on huomattavasti nopeampi koodata kuin mikään muu järjestelyalgoritmi (joskin valmiita quicksort-aliohjelmiakin löytyy luultavasti melkein kaikille ohjelmointikielille).

http://java.sun.com/applets/jdk/1.1/demo/SortDemo/index.html <- ihan hyvä esimerkki Bubblesortin, 2-suuntaisen bubblesortin ja quicksortin aikavaatimuksen erosta...

Hmm... itte tein jokin aikaa sitten tälläisen purkan:

<?php

function ffs_sort(&$array){
	$new = $array;
	foreach($array as $kerta){
		$max = "";
		$ulos = "";
		foreach($new as $num){
			if($num > $max){
				$max = $num;
			}
		}
		$p = 0;
		foreach($new as $num){
			if($num != $max){
				$ulos[] = $num;
			}else{
				if($p == 1){
					$ulos[] = $num;
				}
				$p = 1;
			}
		}
		$new = $ulos;
		$out[] = $max;
	}
	$array = $out;
}

?>

Kääntäkää toi C:lle ja kertokaa miten hidas toi on muihin verrattuna :D

Sami kirjoitti:

Jos järjestettävänä on esimerkiksi 100 alkiota ja yhteen vaihtamiseen kuluu aikaa n. 10^-8 sekuntia (= 10000 mikrosekuntia), niin taulukon järjestämiseen kuluu aikaa n. (10^-8)/(100^2) sekuntia = 10^-4 sekuntia = 0,1 millisekuntia, joka ei vielä ole paljoa.
Jos järjestettävänä on vaikkapa 10^5 (=100000) alkiota, niin koko taulukon järjestämiseen kuluisikin aikaa (10^8)/((10^5)^2) sekuntia = 10^2 sekuntia = 100 sekuntia, eli *hieman* turhan pitkä aika...

Pieni virhe tuossa.. (10^-8)*(100^2)

Niin muuten onkin. Laskun tosiaan pitäisi olla niin kuin NiLon sanoi, mutta väärästä merkinnästä huolimatta tulokset sentään on oikein :)
Yöllä kirjoittaessani näköjään kirjoitin tuon toisenkin laskulausekkeen väärin, mutta siinäkin tulos sentään on oikein (oikea lauseke olisi (10^-8)*((10^5)^2) )

Eräs ovela tapa järjestellä joukko lukuja, joiden tiedetään olevan tietyllä alueella, on laskea taulukkoon kunkin luvun määrä lajiteltavassa joukossa. Silloin luvut täytyy käydä vain kerran läpi, minkä jälkeen kunkin luvun määrä on tiedossa. Sitten määrät on helppo ilmoittaa pienimmästä suurimpaan. Seuraavassa esimerkissä arvotaan 10000 lukua väliltä 1 - 100. Sen jälkeen luvut ja niiden määrät ilmoitetaan järjestyksessä.

Dim luvut(1 To 10000) As Integer
Dim maarat(1 To 100) As Integer
Dim i As Integer

' arvotaan 10000 lukua väliltä 1 - 100
For i = 1 To 10000
    luvut(i) = Int(Rnd * 99) + 1
Next

' lasketaan lukujen määrät
For i = 1 To 10000
    maarat(luvut(i)) = maarat(luvut(i)) + 1
Next

' näytetään kunkin luvun määrä
For i = 1 To 100
    If maarat(i) > 0 Then
        Print i, maarat(i)
    End If
Next

Kuplalajittelu eli bubblesort tuntuu olevan se algoritmi, joka tulee ensimmäisenä mieleen, jos itse ilman ohjetta rupeaa miettimään lajittelun toteuttamista. Toisenlainen tarina liittyy pikalajittelun eli quicksortin syntyyn. Erään algoritmikirjan mukaan C.A.R. Hoare keksi pikalajittelun laatiessaan ohjelmaa, joka järjestelee sanakirjassa olevat sanat. Myöhemmin Hoare kertoo (vapaasti suomennettuna): "Ensin ajattelin käyttää kuplalajittelua, mutta hämmästyttävästi heti toisena mieleeni tuli pikalajittelu. Minulla oli kyllä onnea. Uuden lajittelualgoritmin kehittäminen on hieno aloitus tietojenkäsittelyuralle!"

Lajittelu on niin yleinen ohjelmointitehtävä, että se on kai tutkittu jo niin perusteellisesti, ettei uusien mullistavien algoritmien kehittäminen ole enää mahdollista. Nykypäivänä tällä tavalla ei siis voi saada nimeään tietojenkäsittelyn historiaan. Mutta monta muuta nerokasta algoritmia on varmasti vielä keksimättä...

Antti Laaksonen kirjoitti:

Mutta monta muuta nerokasta algoritmia on varmasti vielä keksimättä...

Ehkäpä juuri noita "muuhunkin kuin pelkkään vertailuihin perustuvia" algoritmeja (kuten esittämäsi "laskemislajittelu") voidaan vielä kehittää lisää, mutta vertailuihin perustuville algoritmeille on todistettu aikavaativuuden alarajaksi n*log n, johon esim. quicksort pääseekin.

Vaikka hunajavohvelin algoritmi olisikin "puolet hitaampi" kuin "oikea" bubblesort, se on kuitenkin samaa aikavaativuusluokkaa n^2, eli käytännössä sillä ei ole mitään väliä.

Okei, päätin minäkin sitten koodata jonkinlaisen lajittelun, ja onnistuinkin jopa :-P Vaan mihin miksi tälläistä lajittelua sitten kutsutaan?

RANDOMIZE TIMER
CLS
 Max% = 99
  DIM Luvut(Max%) AS INTEGER
   FOR I% = 0 TO Max%
  Luvut(I%) = INT(RND * 99 + 1)
 NEXT
Start! = TIMER
DO
 W$ = INKEY$
  IF Luvut(A%) > Luvut(B%) THEN SWAP Luvut(A%), Luvut(B%)
   IF Luvut(A%) > Luvut(B%) THEN SWAP Luvut(B%), Luvut(A%)
    A% = A% + 1
   IF A% >= Max% THEN A% = 0: B% = B% + 1
  IF B% > Max% THEN EXIT DO
 IF W$ = CHR$(27) THEN EXIT DO
LOOP
Finish! = TIMER
 FOR I% = 0 TO Max%
  PRINT Luvut(I%)
 NEXT
PRINT " Ja aika oli"; Finish! - Start!; "sekuntia!"

-Grey-

Marja kirjoitti:

Hunajavohveli: Tuo lienee bubblesort-algoritmi. Joku on tainnut keksiä sen jo vuosikymmeniä sinua aikaisemmin :)

Entä sitten? Ei kai se estä minua keksimästä algoritmia, vaikka joku olisikin tullut ajatelleeksi samaa joskus aikaisemmin? Joten tuo on ihan VohveliSort -algoritmi, koska sen keksin minä. :)

Jahas, huomasin vasta nyt että koodissani on ylimääräinen pätkä, jonka voi poistaa. Rivi 11 tai 12. Äsh, ei pitäisi koodata väsyneenä yhtään mitään :-P

-Grey-

Vohvelin kanssa samaa mieltä. Saa niitä itse keksiä vaikka kuinka löytyisi valmiita ratkaisuja jos vain aikaa ja harrastusta riittää. Itse jäin koukkuun. Teki mieli kokeilla miten sen omalla koodillani saan menemään. En laita koodeja näkyviin mutta kyselisin todellisia aikoja. Jos järjestetään 10000 singletyyppistä lukua suuruusjärjestykseen, sain ajaksi 9,7 sek omalla bubblesorttisella koodilla ja sitten vallan omintakeisella 1,4 sek. Molemmissa aika on verrannollinen lukumäärän neliöön ainakin likimäärin. Kuinkahan lujaa se menee tolla quicksortilla ?? (Athlon 1700+, Win XP Home, VB5)

En tietenkään tarkoittanut, että olisi jotenkin huonoa keksiä sellainen algoritmi, joka on keksitty jo joskus aikaisemmin. Aivan yhtä laillahan siinä on itse tehnyt ajatustyötä, vaikkei nimeään saisikaan mihinkään algoritmiikkakirjaan. Ja minkä me sille voidaan, ettei olla 30 vuotta nuorempia, jolloin oltaisiin itse voitu keksiä jotain uusia lajittelualgoritmeja. :)

(Ehkei kuitenkaan kannata nimetä sitä omaa algoritmiaan, vaan käyttää siitä jo aikaisemmin annettua nimeä. Helpottaa kommunikointia. En tiedä sitten, ovatko algoritmit joidenkin patentti- tms. lakien suojaamia, jolloin voisi saada jotain sanktioita, jos väittää keksineensä sellaisen algoritmin, jonka joku muu on jo keksinyt.)

Grey: Tuo sinunkin algoritmisi lienee olennaisesti bubblesort. En mene takuuseen. Ymmärrän tuota kieltä varsin vähän.

Joo, on siinä ainakin SWAP.

Kyllä se melko bubblesortilta näyttää.
Jostakin syystä en ole saanut Quicksortia toimimaan. Kokeilin sekä ylhäällä olevan linkin että Wikipedian versioita ja vielä muokkasinkin niitä hieman.

Kokeilin Laaksosen Quicksorttia muuttamalla sen 10000 singleluvulle ja aikaa meni 0,1 - 0,05 s eli siis huomattavasti nopeammin. Tosin ajanmittaus timer-funktiolla oli aika epämääräistä noin lyhyellä ajalla eikä lukumäärää saanut suuremmaksi ilman ylivuotoa. QB ei ole oikein handussa. Sain kyllä tuotaa omaa sortteeraustakin viilattua noin puoleen sekuntiin erästä parametria muuttamalla.

Joo, tuo määrien laskemiseen perustuva on ehdottomasti nopein, mutta ongelmana on, että vaihtoehtojen määrän kasvaessa voi tilaa mennä liikaa. Esim 0 .. 4294967295 vie aika lailla tilaa. Siinä vaiheessa kannattaa varmaankin pitää kahta taulukkoa, joista toiseen merkitään määrä ja toiseen se, mitä lukua kyseinen määrä oli, koska kaikkia 4294967296 eri lukua tuskin löytyy.
Yksi peruskikka, jolla saa bubblesortista nopeamman, on tehdä siitä kaksisuuntainen: ensin viedään pienin luku listan kärkeen, sitten tuodaan suurin viimeiseksi. Tätä toistetaan, kunnes ollaan listan keskellä, esim viedään 14. luku ylös ja 15. luku alas. jolloin seuraavaksi vietäisiin 15. luku taas ylös. _Sekavaa!!!

Tarkoitin Laaksosen quicksortilla DSwordin antaman linkin takaa löytyvää QB-koodia, joka on Laaksosen Antin kirjoittama. Siinä on käytetty jonkinlaista rekursiivista menetelmää eikä systeemi ole oikein vielä taipunut meikäläisen kaaliin. Mutta nopea se on. QB käyttää SWAP-toimintoa, joka on selvästi nopeampi kuin kolmen rivin vastine VB:ssä. Bubblesorttia on todellakin tavallisena ja kaksisuuntaisena. Tuossa omassa sortissani haetaan ensin minimi ja maksimi, joita käytetään jatkossa hyväksi lukujen siirtelyyn suunnilleen paikoilleen. Hakemalla jatkuvasti jäljelle jääneestä jonosta min ja max saadaan järjestys oikeaksi mutta tuskin nopeammin kuin bubblesortilla. Täytyy siirtää tuo rekursiivi VB:lle niin voi paremmin verrata. Määrien laskeminen sopii vain kokonaisluvuille, ei singletyypin liukuluvuille.
Edit: Sain siirrettyä VB:lle ja aikaa menee vain noin 0,07 s 10 000 satunnaisen liukuluvun järjestämiseen ja vaihto-operaatioita tarvitaan hieman yli 30 000.

Lisää vertailutuloksia erilaisista sorteista
Omasort1 9,8 s
Omasort2 0,4 s
Vohvelisort 36 s
minmaxsort 8,0 s
Quicksort 0,07 s
Kaikissa on arvottu 10 000 satunnaislukua (Single-tyyppi) välille 0...10 000. Minmaxsortissa on haettu järjestys kuten Metabolix selitti yllä. Jos käytän quicksorttia omasort2:ssa siitä ehkä voi tulla vielä nopeampi kuin quicksort.

Metabolix kirjoitti:

Joo, tuo määrien laskemiseen perustuva on ehdottomasti nopein, mutta ongelmana on, että vaihtoehtojen määrän kasvaessa voi tilaa mennä liikaa. Esim 0 .. 4294967295 vie aika lailla tilaa. Siinä vaiheessa kannattaa varmaankin pitää kahta taulukkoa, joista toiseen merkitään määrä ja toiseen se, mitä lukua kyseinen määrä oli, koska kaikkia 4294967296 eri lukua tuskin löytyy.

Hmm, en usko tuon toimivan ennen kuin näytät koodia. Laskentajärjestyksen nopeus nimittäin perustuu juuri siihen, että taulukossa olevalla luvulla _indeksoidaan_ toista taulukkoa. Siksi sillä päästään pienempään aikaan kuin n*log n, joka on alaraja vertailuun perustuville järjestyksille. Tosiaan haittapuoli on se, että jos lukualuetta ei tiedetä tai se on suuri, algoritmia ei voi käyttää.

Jos yhteen taulukkoon kerättäisiin vastaan tulleita lukuja ja toiseen niiden esiintymismääriä, niin pahimmassa tapauksessa jokaisen luvun kohdalla jouduttaisiin lukemaan n lukua lukutaulukosta (haetaan, onko luku kohdattu joskus aikaisemmin), eli ajasta tulisi luokkaa n^2 (tai jos haku tehtäisiin esim. binäärihaulla siitä tulisi n*log n, eli laskentajärjestyksen hyödyt menetettäisiin). Näin ainakin tuon ideasi ymmärsin, tiedä sitten, ymmärsinkö se on oikein..

Kyllä se tosiaan hidastui melkoisesti ainakin meikäläisen taidoilla. Aina on silti hyvä yrittää; oma ajatustyö on ehdottomasti tärkein asia jos vain aikaa riittää.
Opinpa muuten käyttämään vielä Pascalissakin linkitettyä listaa tuota yrittäessäni.