PB_LinkedLists

[ParkL]

geil !

[Deeem2031]

Finds ja schön wenn du den Cod egut findest, aber der Beitrag war bisl sinnlos
Egal, die SortierProc ist nu auch fertig, das hoffe ich zumindest, meine Test waren nämlich nicht so sehr umfangreich da ich jetzt ins Bett will.
Die Proc sortiert nur nach longs (dabei ist es aber egal ob diese in einer Structure stehen oder nicht)

Code: Alles auswählen

Structure PB_LinkedListData_Struc
  *FirstElement.PB_LinkedListElement_Struc ; FirstElement(LL()): = @LL()-8
  *LastElement.PB_LinkedListElement_Struc ; LastElement(LL()): = @LL()-8
  SizeofElement.l ; (Structure + *NextElement.l and *PrevElement.l (8 Byte))
  AmountofElements.l ; = CountList()
  NumberofCurrentElement.l ; = ListIndex() + 1 (with the normal PB 3.92 LL-Library NumberofCurrentElement.l is equal to the result of ListIndex(), with the new one from purebasic.com/beta its bigger by 1)
  StructureMap.l ; "the StructureMap is the address of the structure associated with the list, so if there is string in it they can be freed easily" by AlphaSND (explained at the end of the file)
  IsSetNumberofCurrentElement.l ; Is NumberofCurrentElement saving the correct value? (0=yes,other=no)
EndStructure

Structure PB_LinkedListElement_Struc
  *NextElement.l
  *PrevElement.l
  ;[...] Content
EndStructure

Structure PB_LinkedList_Struc
  *PB_LinkedListData.PB_LinkedListData_Struc
  *CurrentElement.PB_LinkedListElement_Struc
EndStructure

#SortLL_rising = 1
#SortLL_descending = 2

Procedure SortLL(*p.PB_LinkedList_Struc,Offset.l,flags)
  Protected LL_Elements,LL_CurrentValue,*PValsBufC.LONG,MemOffsetHigh,*LL_CurrentElement.PB_LinkedListElement_Struc,*LL_LastElement.PB_LinkedListElement_Struc
  Protected i
  
  Offset + 8
  LL_Elements = *p\PB_LinkedListData\AmountofElements
  If LL_Elements
    PValsBuf = AllocateMemory(LL_Elements*8)
    If PValsBuf
      PValsBufEnd = PValsBuf+LL_Elements*8-8
      
      *LL_CurrentElement = *p\PB_LinkedListData\FirstElement
      
      MemOffsetHigh = 0
      Repeat
        LL_CurrentValue = PeekL(*LL_CurrentElement+Offset)
        *PValsBufC = PValsBufEnd
        If flags & #SortLL_rising
          While *PValsBufC\l >= LL_CurrentValue And MemOffsetHigh > PValsBufEnd-*PValsBufC
            *PValsBufC-8
          Wend
        ElseIf  flags & #SortLL_descending
          While *PValsBufC\l <= LL_CurrentValue And MemOffsetHigh > PValsBufEnd-*PValsBufC
            *PValsBufC-8
          Wend
        EndIf
        If MemOffsetHigh <> PValsBufEnd-*PValsBufC
          ;Debug Str(PValsBufEnd-MemOffsetHigh)+" "+Str(PValsBufEnd-MemOffsetHigh)+" "+Str(MemOffsetHigh-(PValsBufEnd-*PValsBufC))
          CopyMemory(PValsBufEnd-MemOffsetHigh+8,PValsBufEnd-MemOffsetHigh,MemOffsetHigh-(PValsBufEnd-*PValsBufC))
        EndIf
        *PValsBufC\l = LL_CurrentValue
        *PValsBufC+4
        *PValsBufC\l = *LL_CurrentElement
        *PValsBufC+4
        MemOffsetHigh+8
        
        *LL_CurrentElement = *LL_CurrentElement\NextElement
      Until *LL_CurrentElement = 0
      
      *PValsBufC = PValsBuf+4
      *LL_CurrentElement = *p\PB_LinkedListData\FirstElement
      *LL_LastElement = 0
      *p\PB_LinkedListData\FirstElement = *PValsBufC\l
      For i = 1 To LL_Elements
        *LL_CurrentElement\PrevElement = *LL_LastElement
        *LL_LastElement = *LL_CurrentElement
        *LL_CurrentElement\NextElement = *PValsBufC\l
        *LL_CurrentElement = *LL_CurrentElement\NextElement
        
        *PValsBufC+8
      Next
      *p\PB_LinkedListData\LastElement = *LL_CurrentElement
      *LL_CurrentElement\NextElement = 0 
      
      FreeMemory(PValsBuf)
      
      *p\PB_LinkedListData\IsSetNumberofCurrentElement = 1 ;Set ListIndex to invalid
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
  Else
    ProcedureReturn #True
  EndIf
EndProcedure

;-Beispiel

Structure player_struc
  x.l
  y.l
  quality.l
  l.l
EndStructure

NewList Playerlist.player_struc()

AddElement(Playerlist())
Playerlist()\quality = 11
AddElement(Playerlist())
Playerlist()\quality = 8
AddElement(Playerlist())
Playerlist()\quality = 3
AddElement(Playerlist())
Playerlist()\quality = 4
AddElement(Playerlist())
Playerlist()\quality = 2
AddElement(Playerlist())
Playerlist()\quality = 10

Global tmp.l
!MOV dword [v_tmp], t_Playerlist
SortLL(tmp,OffsetOf(player_struc,quality),#SortLL_descending)

ForEach Playerlist()
  Debug Playerlist()\quality
Next



Dim TestArray.l(5)
TestArray(0) = 11:TestArray(1) = 8:TestArray(2) = 3:TestArray(3) = 4:TestArray(4) = 2:TestArray(5) = 10
NewList TestLL.l()
AddElement(TestLL()):TestLL() = 11
AddElement(TestLL()):TestLL() = 8
AddElement(TestLL()):TestLL() = 3
AddElement(TestLL()):TestLL() = 4
AddElement(TestLL()):TestLL() = 2
AddElement(TestLL()):TestLL() = 10

#r = 1000000

!MOV dword [v_tmp], t_TestLL
StartTime = timegettime_()
For i = 1 To #r
  SortLL(tmp,0,#SortLL_descending)
Next
Time1 = timegettime_()-StartTime


StartTime = timegettime_()
For i = 1 To #r
  SortArray(TestArray(),1)
Next
Time2 = timegettime_()-StartTime

MessageRequester("","SortLL: "+StrF(Time1/#r)+"ms/call"+Chr(13)+Chr(10)+"SortArray: "+StrF(Time2/#r)+"ms/call")

Ich hoffe das Beispiel ist verständlich..

EDIT: Ein Bug entfernt und Flags hinzugefügt.

EDIT2: Noch ein Bug entfernt und Zeitvergleich zu SortArray hinzugefügt.

[Deeem2031]

Hab noch zwei Bugs ausm Code entfernt, ich hatte nämlich *PreviousElement vergessen, so das wenn man in der Liste zurückgegangen wäre völlig wonanders gelandet wäre. Der zweite verhinderte das FreeMemory() richtig funktioniert, die Proc schrieb nämlich immer 8 bytes zu weit vorne und überschrieb warscheinlich eine ID für PB.

Ich hab meine Proc auch mal mit SortArray() verglichen (obwohl das ja bisl unfair ist, Linkedlist gegen Array ) und meine Proc schaffts bei mir auf erstaunliche 0.00083 ms/call, SortArray auf 0.00027 ms/call und dabei weiß ich nichtmal was für eine Art von Sortierung ich verwendet habe, hab mir einfach einen Sortieralgo ausgedacht

Wär übrigens über Feedback erfreud

[Rings]

mal ne besondere art des feedbacks von mir:

Nachdem ich dich nu schon etwas länger kenne (hier aus dem forum),
teilweise aus dem irc,
bist du das beste beispiel das auch aus einem Noob was werden kann.
Wenn ich an deine erste Versuche und posts denke und was du nu ablieferst,
respekt.
Gerade mit einem solchem post hast du bewiesen das du selbstständig Probleme lösen kannst (ich hoffe ich klinge nich wie ein Lehrer) .
Ach und gerade zu diesem Post:

Ja, jeder der Listen verarbeitet kann irgendwann eine Sortierroutine dazu gebrauchen. Ich weiss eigentlich nicht warum sowas nicht in Pure eingebaut ist. Bei mir sinds meine mittlerweile fast 30000 Mp3's die sortiert werden wollen, da hat die cpu was zu schaffen .
Danke für deine Mühe und deine Code,kommt mir sehr gelegen.

[Deeem2031]

Thx, schön das jemand meinen Code gebrauchen kann. Ich selber brauch die SortierProc nämlich garnicht, hab 'se für jemand anderen gebastelt. Aber nu weiß ich wenigstens auch wie Linkedlists intern funktionieren. Und die Proc kann ich vielleicht auch irgendwann gebrauchen.

Btw. Purefan hatte zuerst Probs mitm Code, lag aber daran das er nich die neuste Library hatte. Wenn also die Proc die LL nicht sortieren sollte die Lib von www.purebasic.com/beta ausprobieren.

[Dostej]

Irgendwer hat schon mal ne sortierroutine geschrieben, die auch mit strings zurecht kam, dafür mehrere Unterprozeduren braucht.

Ich finde eher den Einblick in die Funktionsweise hilfreich. Danke

[PAMKKKKK]

Das läuft bei mir gegen einen Fehler:

Code: Alles auswählen

SortLL(tmp,OffsetOf(player_struc,quality),#SortLL_descending)

die Procedure OffsetOf(player_struc,quality) fehlt wohl ....

PureBasic 3.93 WinXP

[Deeem2031]

OffsetOf() ist eigentlich eine Procedure von PB, die also bei jedem dabei sein sollte. Was steht denn da wenn der Fehler angezeigt wird?

[Batze]

Man könnte höchstens vor dem ablauf die einzellnen Indexe (oder was ist die mehrzahl?) in die entsprechenden Pointer verwandeln ...

Die Mehrzahl ist Indices (du hast ja gefragt)

[Kiffi]

> Die Mehrzahl ist Indices

sowohl als auch