Archief - mediaan: recursieve functie

Ik stootte dit weekend op een (recursief) algoritme voor het berekenen van de mediaan. Dit is een heel andere aanpak dan eenvoudigweg de lijst (van N elementen) sorteren van klein naar groot en dan element op positie N\2 te nemen (voor een oneven N).
Als ik het algoritme doorloop, stel ik vast dat men idd. tot het juist resultaat komt, maar het probleem is dat ik deze aanpak conceptueel niet "zie"/vat/snap. Ik zou er nooit zelf zo opgekomen zijn. Het gaat niet over de syntax, die snap ik wel, maar over het algoritme zelf.
Wat ik ook niet goed begrijp is de berekening van de nieuwe waarde voor de tweede parameter vd functie indien de mediaan zich in de higherlist bevindt (position - lowerList.Count - 1)
Kan er iemand een uitleg voorzien die mij een aha-erlebnis kan bezorgen?

Hieronder het algoritme (in VB.net, met generics).

als je een lijst hebt met getallen. Niet geordend dus.
neemt hij bij start
guess = list(0) je eerste item dus.
als er maar 1 item is, ja dan is dit de mediaan.

verder. ga je dit eerste item, uw gok dit is de mediaan gaan vergelijken met alle items in de lijst
en verdelen over 2 lijsten, alle getallen die groter zijn en alle die kleiner zijn.

eens dit gebeurd is ga je , gaan kijken of de lagelijst meer items telt dan 'positie' die de helft is van de initiele lijst. Als je dus 50 items hebt is dit 25, als uw lage lijst groter is dan 25, wil dit zeggen dat er meer 'lage' getallen zijn dan hoge. Waar je dus kunt uit afleiden dat uw mediaan hier in zal vallen.

Want mediaan is het 'middelste' getal. het midden van uw initiële lijst zal dus een getal zijn die in deze 'lage'-lijst zit, en kun je dit gaan herhalen.
tot je ofwel 1tje overhebt.

of tot uw 'guess' effectief in het midden ligt.

Hopelijk is dit een goede verklaring

Je kiest overigens als guess eender welk element uit de lijst, omdat je totaal niet weet of je guess goed of fout is

Als je recursief verder gaat moet je je positie aanpassen.
Als je lagereLijst groter is, is dit niet nodig, want de positie van de mediaan is dan nog altijd op de helft van de oude lijst.
Maar als je hogereLijst groter is, moet je je positie als het ware opschuiven zodat die overeenkomt met de posities van de items in de hogereLijst.
Als een item voordien het 5e grootste was, en de lagereLijst heeft een lengte van 3, dan heeft dat item nu de positie 2 in de hogereLijst. Op dezelfde manier moet je je positie aanpassen. Als je positie 4 was, heeft die nu positie 3, wat overeenkomt met 'positie - lagereLijst.lengte'

Gurdt zei:

Als je recursief verder gaat moet je je positie aanpassen.
Als je lagereLijst groter is, is dit niet nodig, want de positie van de mediaan is dan nog altijd op de helft van de oude lijst.

Klik om te vergroten...

Dit begrijp ik niet. Bij dit algoritme moet de lijst niet geordend zijn. Je kunt dan toch niet met zekerheid zeggen dat de mediaan in het midden van de lijst ligt?

Een moelijkere vraag: welk resultaat krijg je als je de functie aanroept met bijv. 0 of 2 als tweede parameter?

is het niet makkelijker om dit via debug te snappen voor je?

Gitan zei:

Je kunt dan toch niet met zekerheid zeggen dat de mediaan in het midden van de lijst ligt?

Klik om te vergroten...

Er wordt een spilelement gekozen, daarna worden alle waarden kleiner dan dat element in een aparte lijst gestoken, en alle waarden groter dan dat element in een andere. Naar gelang de grootte van de 2 lijsten ga je ofwel verder met de kleinere elementen of de grotere. Je kan bv eens naar quicksort kijken, daar gebeurt ongeveer hetzelfde.

Ik moest ook meteen aan quicksort denken inderdaad.
Het is ook niet zo dat de mediaan in het midden ligt, maar je wilt de waarde die in het midden zou liggen

Die positie zelf invullen zou dus ongewenste resultaten geven. Bv 2 invullen gaat uiteindelijk de waarde teruggeven die op de 2e plaats zou voorkomen als de lijst gesorteerd zou zijn van klein naar groot.

0 geeft de kleinste waarde
Even elaboreren:
* ge pakt ne random waarde en ge deelt uw lijst op in ne hogereLijst en ne lagereLijst.
* op het punt dat ge gaat kijken welke lijst 'te lang' is ga je iets vreemds zien, natuurlijk is de lengte van de lagereLijst groter dan 0, die is namelijk altijd minstens 1.
* die lagerelijst blijft dan opgedeeld worden tot de lengte ervan nog maar 1 is, en dan zegt de functie, DIT is de enige waarde in de lijst, dit is de waarde die je zoekt.
* omdat je altijd bent verdergegaan met alle getalen die LAGER zijn dan je guess, wilt het zeggen dat dat ene getal lager is dan alle andere getallen

Voordeel van deze procedure is dat de berekeningstijd enorm verlaagd. Met jouw aanpak zit je altijd te werken met n^2 bewerkingen, terwijl dit met deze procedure herleidt wordt naar n * log2 n
Voor een korte reeks zal je niet meteen veel verschil zien, maar eens je met enkele tienduizenden elementen zit, zal je enorm verschil merken in berekeningstijd.

Zhergan zei:

Voordeel van deze procedure is dat de berekeningstijd enorm verlaagd. Met jouw aanpak zit je altijd te werken met n^2 bewerkingen, terwijl dit met deze procedure herleidt wordt naar n * log2 n
Voor een korte reeks zal je niet meteen veel verschil zien, maar eens je met enkele tienduizenden elementen zit, zal je enorm verschil merken in berekeningstijd.

Klik om te vergroten...

Welke 2 aanpakken vergelijk je eigenlijk?

Die quicksort werd enkel vermeld omdat het principe hetzelfde is. Je mag die dingen echter niet vergelijken omdat ze een totaal verschillend resultaat hebben. Bij quicksort is de hele lijst gesorteerd.

-alle getallen in een array knallen
-waardes van de array sorteren van klein naar groot
-lengte van de array opvragen
-lengte array % 2 (restdeling)
-als het resultaat = 0 -> neem de getallen op positie (lengte array / 2) en (lengte (array / 2) -1)
-

Zhergan zei:

Voordeel van deze procedure is dat de berekeningstijd enorm verlaagd. Met jouw aanpak zit je altijd te werken met n^2 bewerkingen, terwijl dit met deze procedure herleidt wordt naar n * log2 n
Voor een korte reeks zal je niet meteen veel verschil zien, maar eens je met enkele tienduizenden elementen zit, zal je enorm verschil merken in berekeningstijd.

Klik om te vergroten...

Toch even op inpikken (ook al is het al even geleden gepost). In het slechtste geval is dit algoritme ook O(n²), want het heeft net dezelfde tekortkomingen als quicksort. Overigens zijn bijna alle sorteeralgoritmen O(nlgn) waardoor eerst sorteren en dan het midden pakken bijna even performant zal zijn als dit algoritme.

centralzero zei:

-alle getallen in een array knallen
-waardes van de array sorteren van klein naar groot
-lengte van de array opvragen
-lengte array % 2 (restdeling)
-als het resultaat = 0 -> neem de getallen op positie (lengte array / 2) en (lengte (array / 2) -1)
-

Klik om te vergroten...

Heb je ook meer enige moeite gedaan om de topic te lezen, of zag je gewoon mediaan in de topic, en dacht je even je super-algoritme te posten waar niemand zou kunnen opkomen? :ironic: