sorting

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	hitokiri Betreff: sorting	Sa, Nov 18, 2006 1:57 Antworten mit Zitat
hallo allerseits, hab mich mal nach langer absenz an ner quicksort implementation für floating pointer arrays in bmax versucht... als mögliches z-sorting. krieg aber auf nem sempron 2000 mit 200mb ram nich so die tollen zeiten.. bei zwischen 0,1 und 0,5 sekunden für 100000 einträge wäre das ne framerate von 1 :/ muss wohl irgendwo absolute scheisse geschrieben haben, wäre schon wenn jemand mal ein auge drauf haben könnte. hier der code (und ja, debugging ist disabled) was mich auch verwundert ist, dass mein in-place qsort fast genauso schnell ist.... Code: [AUSKLAPPEN] [EINKLAPPEN] SeedRnd(MilliSecs()) Global bugger:Float[]=New Float[100000] Global bp:Float Ptr[]=New Float Ptr[100000] size:Int=99999 For i:Int=0 To 99999 bugger[i]=Rnd!(-1000,1000) bp[i]=Varptr bugger[i] Next time:Double=MilliSecs() qsort(bp,0,99999) time=MilliSecs()-time For i=0 To 999'99 Print bp[i][0] Next Print time/1000+" seconds" Function qsort(array:Float Ptr[],l:Int,r:Int) If r>l i:Int=l j:Int=r Local tmp:Float Ptr If (r-l)>3 m:Int=(l+r)/2 If array[l][0]>array[m][0] tmp=array[l] array[l]=array[m] array[m]=tmp EndIf If array[l][0]>array[r][0] tmp=array[l] array[l]=array[r] array[r]=tmp EndIf If array[r][0]>array[m][0] tmp=array[r] array[r]=array[m] array[m]=array[r] EndIf EndIf Repeat While array[i][0]<array[r][0] 'And i<j i:+1 Wend While array[j][0]>=array[r][0] And j>i j:-1 Wend If i>=j Then Exit tmp=array[i] array[i]=array[j] array[j]=tmp Forever tmp=array[i] array[i]=array[r] array[r]=tmp qsort(array,l,i-1) qsort(array,i+1,r) EndIf End Function

hitokiri

Betreff: sorting

Sa, Nov 18, 2006 1:57
Antworten mit Zitat

hallo allerseits,
hab mich mal nach langer absenz an ner quicksort implementation für
floating pointer arrays in bmax versucht... als mögliches z-sorting.
krieg aber auf nem sempron 2000 mit 200mb ram nich so die tollen zeiten..
bei zwischen 0,1 und 0,5 sekunden für 100000 einträge wäre das ne framerate von 1 :/
muss wohl irgendwo absolute scheisse geschrieben haben, wäre schon wenn jemand mal ein auge drauf haben könnte.
hier der code (und ja, debugging ist disabled)
was mich auch verwundert ist, dass mein in-place qsort fast genauso schnell ist....

Code:

SeedRnd(MilliSecs())
Global bugger:Float[]=New Float[100000]
Global bp:Float Ptr[]=New Float Ptr[100000]
size:Int=99999
For i:Int=0 To 99999
bugger[i]=Rnd!(-1000,1000)
bp[i]=Varptr bugger[i]
Next

time:Double=MilliSecs()
qsort(bp,0,99999)
time=MilliSecs()-time

For i=0 To 999'99
Print bp[i][0]

Next
Print time/1000+" seconds"

Function qsort(array:Float Ptr[],l:Int,r:Int)
If r>l
   i:Int=l
   j:Int=r
   Local tmp:Float Ptr
   If (r-l)>3
      m:Int=(l+r)/2
      If array[l][0]>array[m][0]
         tmp=array[l]
         array[l]=array[m]
         array[m]=tmp
      EndIf
      If array[l][0]>array[r][0]
         tmp=array[l]
         array[l]=array[r]
         array[r]=tmp
      EndIf
      If array[r][0]>array[m][0]
         tmp=array[r]
         array[r]=array[m]
         array[m]=array[r]
      EndIf
   EndIf

   Repeat


      While array[i][0]<array[r][0] 'And i<j
      i:+1
      Wend

      While array[j][0]>=array[r][0] And j>i

      j:-1




      Wend

      If i>=j Then Exit
      tmp=array[i]
      array[i]=array[j]
      array[j]=tmp
   Forever

   tmp=array[i]
   array[i]=array[r]
   array[r]=tmp

   qsort(array,l,i-1)
   qsort(array,i+1,r)

EndIf

End Function