1. #1
    Gitan's Avatar
    Registered
    05/09/03
    Location
    Gent
    Posts
    77
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0

    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).
    Code:
    Function MedianValue(Of T As IComparable)(ByVal list As List(Of T), _
    Optional ByVal position As Integer = -1) As T
     
    ' Provide a default value for second argument.
    If position < 0 Then position = list.Count \ 2
     
    ' If the list has just one element, we've found its median.
    Dim guess As T = list(0)
    If list.Count = 1 Then Return guess
    ' This list will contain values lower and higher than the current guess.
    Dim lowerList As New List(Of T)
    Dim higherList As New List(Of T)
     
    For i As Integer = 1 To list.Count - 1
      Dim value As T = list(i)
      If guess.CompareTo(value) <= 0 Then
        ' The value is higher than or equal to the current guess.
        higherList.Add(value)
      Else
        ' The value is lower than the current guess.
        lowerList.Add(value)
      End If
    Next
     
    If lowerList.Count > position Then
      ' The median value must be in the lower-than list.
      Return MedianValue(lowerList, position)
    ElseIf lowerList.Count < position Then
      ' The median value must be in the higher-than list.
      Return MedianValue(higherList, position - lowerList.Count - 1)
    Else
      ' The guess is correct.
      Return guess
    End If
     
    End Function
    no votes  

  2. #2
    woony's Avatar
    Registered
    03/12/03
    Location
    Oostende
    Posts
    2,599
    iTrader
    78 (100%)
    Mentioned
    0 Post(s)
    Reputation
    7/10
    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
    no votes  

  3. #3
    Gurdt's Avatar
    Registered
    21/08/08
    Location
    Hasselt
    Posts
    2,653
    iTrader
    8 (100%)
    Mentioned
    0 Post(s)
    Reputation
    5/46
    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'
    no votes  

  4. #4
    Gitan's Avatar
    Registered
    05/09/03
    Location
    Gent
    Posts
    77
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0
    Quote Originally Posted by Gurdt View Post
    This quote is hidden because you are ignoring this member. Show
    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.
    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?
    no votes  

  5. #5
    woony's Avatar
    Registered
    03/12/03
    Location
    Oostende
    Posts
    2,599
    iTrader
    78 (100%)
    Mentioned
    0 Post(s)
    Reputation
    7/10
    is het niet makkelijker om dit via debug te snappen voor je?
    no votes  

  6. #6
    Cycloon's Avatar
    Registered
    18/01/04
    Location
    Melle
    Posts
    10,535
    iTrader
    56 (100%)
    Mentioned
    0 Post(s)
    Reputation
    27/102
    Quote Originally Posted by Gitan View Post
    This quote is hidden because you are ignoring this member. Show
    Je kunt dan toch niet met zekerheid zeggen dat de mediaan in het midden van de lijst ligt?
    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.
    “In terms of how we evaluate schooling, everything is about working by yourself. If you work with someone else, it’s called cheating. Once you get out in the real world, everything you do involves working with other people.”
    PSN: Cycloon - Final Fantasy XIV: A realm reborn character
    no votes  

  7. #7
    Gurdt's Avatar
    Registered
    21/08/08
    Location
    Hasselt
    Posts
    2,653
    iTrader
    8 (100%)
    Mentioned
    0 Post(s)
    Reputation
    5/46
    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
    no votes  

  8. #8
    Zhergan's Avatar
    Registered
    22/09/03
    Location
    xx
    Posts
    194
    iTrader
    0
    Mentioned
    0 Post(s)
    Reputation
    0/0
    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.
    no votes  

  9. #9
    Gurdt's Avatar
    Registered
    21/08/08
    Location
    Hasselt
    Posts
    2,653
    iTrader
    8 (100%)
    Mentioned
    0 Post(s)
    Reputation
    5/46
    Quote Originally Posted by Zhergan View Post
    This quote is hidden because you are ignoring this member. Show
    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.
    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.
    no votes  

  10. #10
    centralzero's Avatar
    Registered
    17/03/05
    Location
    Lommel
    Posts
    863
    iTrader
    7 (67%)
    Mentioned
    0 Post(s)
    Reputation
    0/0
    -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)
    -
    /
    no votes  

  11. #11
    Cycloon's Avatar
    Registered
    18/01/04
    Location
    Melle
    Posts
    10,535
    iTrader
    56 (100%)
    Mentioned
    0 Post(s)
    Reputation
    27/102
    Quote Originally Posted by Zhergan View Post
    This quote is hidden because you are ignoring this member. Show
    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.
    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.
    “In terms of how we evaluate schooling, everything is about working by yourself. If you work with someone else, it’s called cheating. Once you get out in the real world, everything you do involves working with other people.”
    PSN: Cycloon - Final Fantasy XIV: A realm reborn character
    no votes  

  12. #12

    Registered
    30/09/02
    Location
    Mariakerke
    Posts
    554
    iTrader
    1 (100%)
    Mentioned
    0 Post(s)
    Reputation
    2/2
    Quote Originally Posted by centralzero View Post
    This quote is hidden because you are ignoring this member. Show
    -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)
    -
    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?
    no votes  

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Log in

Log in