PureBoard

Verfasst: **11.12.2006 19:32**

Ich schreib grad an einem Programm, bei dem ich Listen recht häufig durchsuche und Teilweise rückwärts durchlaufen lasse. Anfänglich hab ich aus verschiedenen Gründen die Elemente meist mit SelectElement() angegeben. Heut hab ich schließlich PreviousElement() bei weiteren Routinen benutzt. Zwar ist es für mein Programm kaum relevant, was nun schneller funktioniert, jedoch kam ich dadurch auf die Idee, mal zu schauen, was nun schneller ist. Ich hätte nicht gedacht, daß SelectElement() so extrem langsamer funktioniert, bei größeren Listen sollte man das aber unbedingt wissen. Hier ein Speedvergleich, wobei man vielleicht beachten sollte, daß es bei alten Rechnern eventuell ewig dauern kann und man vielleicht den Endwert der For:Next-Schleife runter setzen sollte... ich selbst hab 'nen Doppelprozi mit 2100 mHz.

Code: Alles auswählen

NewList Liste()

Debug "Liste füllen"
Start = ElapsedMilliseconds()
For a = 0 To 100000
  AddElement(Liste())
Next
Debug Str(ElapsedMilliseconds() - Start) + " ms"
Debug "----------------------------"

Debug "Mit PreviousElement()"
pos = ListenEnde
Start = ElapsedMilliseconds()
While ListIndex(Liste()) <> 0
  PreviousElement(Liste())
  pos - 1 
Wend
Debug Str(ElapsedMilliseconds() - Start) + " ms"
Debug "----------------------------"

ListenEnde = CountList(Liste()) - 1
Debug "Mit SelectElement()"
pos = ListenEnde
Start = ElapsedMilliseconds()
While pos <> 0
  SelectElement(Liste(), pos)
  pos - 1
Wend
Debug Str(ElapsedMilliseconds() - Start) + " ms"
Debug "----------------------------"

16 ms (PreviousElement()) vs 63250 ms (SelectElement())

Verfasst: **11.12.2006 19:46**

was völlig logisch ist:

PB-Help SelectElement() hat geschrieben:Da LinkedLists keinen Index verwenden, wird allerdings zwangsweise bis zu der Zielposition jedes Element schrittweise angesprungen.

Verfasst: **11.12.2006 20:39**

Naja, nicht unbedingt:

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

Global NewList Liste() 

DisableDebugger
Procedure SelectElement2(LinkedList(),Position)
  Protected *LL.PB_LinkedList_Struc
  MOV *LL, Eax ;LinkedList()
  
  LastElement = *LL\PB_LinkedListData\AmountofElements - 1
  
  WaytoLast = LastElement - Position
  If WaytoLast < 0 Or Position < 0
    ;invalid position
    ProcedureReturn #False
  EndIf
  WaytoFirst = Position
    
  If *LL\PB_LinkedListData\IsSetNumberofCurrentElement = 0 ;We know the index of the current element
    CurrentElement = *LL\PB_LinkedListData\NumberofCurrentElement - 1
    
    WaytoCurrent = Position - CurrentElement
    
    If AbsInt(WaytoCurrent) < WaytoLast And AbsInt(WaytoCurrent) < WaytoFirst ; The distance from the current element to element at 'position' is smaller than to the first or last element 
      While WaytoCurrent < 0 ;so we go back if WaytoCurrent < 0 ...
        PreviousElement(LinkedList())
        WaytoCurrent + 1
      Wend
      While WaytoCurrent > 0 ;or forward to reach 'position'
        NextElement(LinkedList())
        WaytoCurrent - 1
      Wend
    ElseIf WaytoLast < WaytoFirst
      LastElement(LinkedList())
      While WaytoLast
        PreviousElement(LinkedList())
        WaytoLast - 1
      Wend
    Else
      FirstElement(LinkedList())
      While WaytoFirst
        NextElement(LinkedList())
        WaytoFirst - 1
      Wend
    EndIf
  Else ; We dont know it :)
    If WaytoLast < WaytoFirst
      LastElement(LinkedList())
      While WaytoLast
        PreviousElement(LinkedList())
        WaytoLast - 1
      Wend
    Else
      FirstElement(LinkedList())
      While WaytoFirst
        NextElement(LinkedList())
        WaytoFirst - 1
      Wend
    EndIf
  EndIf
  ProcedureReturn @LinkedList()
EndProcedure
EnableDebugger

Debug "Liste füllen" 
Start = ElapsedMilliseconds() 
For a = 0 To 20000
  AddElement(Liste()) 
  Liste() = a
Next 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------" 

Debug "Mit PreviousElement()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While ListIndex(Liste()) <> 0 
  PreviousElement(Liste()) 
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------" 

ListenEnde = CountList(Liste()) - 1 
Debug "Mit SelectElement()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While pos <> 0 
  SelectElement(Liste(), pos) 
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------"

ListenEnde = CountList(Liste()) - 1 
Debug "Mit SelectElement2()" 
pos = ListenEnde 
Start = ElapsedMilliseconds() 
While pos <> 0 
  SelectElement2(Liste(), pos)
  If ListIndex(Liste()) <> pos
    MessageRequester(Str(ListIndex(Liste())),Str(pos),16)
    End
  EndIf
  pos - 1 
Wend 
Debug Str(ElapsedMilliseconds() - Start) + " ms" 
Debug "----------------------------"

(Ja, ich hab Fred gerade gezeigt

)

Verfasst: **12.12.2006 12:04**

So wie Deeem2031 das macht, hab ich es mit meinen LinkedLists auch immer
gemacht und in meiner Datenbank hab ich auch sowas drin.

Verfasst: **12.12.2006 16:09**

Da fehlt ein 'h'!
Wußte gar nicht, daß PB Alkohol mag und sich deshalb bei obigem Pgm über das fehlende 'h' bei

If AbsInt(WaytoCurrent) < WaytoLast And AbsInt(WaytoCurrent) < WaytoFirst ; The distance from the current element to element at 'position' is smaller than to the first or last element
While WaytoCurrent < 0 ;so we go back if WaytoCurrent < 0 ...

beschwert.

Oder bedeutet 'AbsInt' hier was anderes?

PureBoard

SelectElement() vs PreviousElement()

SelectElement() vs PreviousElement()