Page 1 of 2
Not a bug, but lists are nearly useless because of speed
Posted: Sun Aug 19, 2007 11:53 am
by technicorn
Or better said, because lack of speed.
Try this and you see what I mean:
Code: Select all
EnableExplicit
Define n.l, nEnd.l = 5000
Define i.l, iEnd.l = 10000
Define tStart.l, tExec1.d, tExec2.d
NewList l1.l()
For i = 1 To iEnd
AddElement(l1())
l1() = i
Next i
tStart = ElapsedMilliseconds()
For n = 1 To nEnd
For i = 1 To 10
SelectElement(l1(), i)
Next i
Next n
tExec1 = (ElapsedMilliseconds() - tStart) / 1000.0
tStart = ElapsedMilliseconds()
For n = 1 To nEnd
For i = 9990 To 10000
SelectElement(l1(), i)
Next i
Next n
tExec2 = (ElapsedMilliseconds() - tStart) / 1000.0
MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end: " + StrD(tExec2, 3))
If you have a slow comp, the second part might take some minutes!
I understand that going from one index in the list to another means,
the program has to scan over all items inbetween,
but going, for example, from index 9999 to 10000 should be the same
as using NextElement(), but instead the list is always scanded from the start!!
The linkedlist library already uses a flag to avoid the problem of
using ChangeCurrentElement() (at least it was so in previous versions),
which will make the list index invalide.
But using ListIndex() rescaned the list once and reseted the flag to show
that the index is valide again, so way not use this flag to have a save way
to go from one index of SelectIndex() to another in a faster way?
And before someone suggested to use NextElement() to go from index 9999 to 10000,
this was just an example for the (slow-)speed, it is also true for 7777 to 666
And I would rather not have to use a loop with NextElement() / PreviousElement() to iterate throgh the list,
which is much faster at the moment.
Greatings
technicorn
Posted: Sun Aug 19, 2007 12:54 pm
by Trond
If you need fast random access use an array.
Posted: Sun Aug 19, 2007 2:05 pm
by technicorn
That isn't an option if you have a huge count of items, and the
amount of items is constantly changing.
For example a server program, where people log on and off,
or databases.
Using an array for such tasks you
1. Have to redim it, at least for adding items,
2. Keep track of empty entries, or copy all itmes after a removed one down on place
that would be very impractical if the removed one was the first of, say 100000 items.
Or if you have to keep the array sorted that would mean copy 99999 items to higher places,
if the new item has to go in front of all other,
with a list that is just a question of adding one element at the front.
Posted: Sun Aug 19, 2007 2:13 pm
by Derek
Get a faster computer, only takes 3.4 seconds on mine.
But you are right, there should be a flag to say it is ok to use faster methods of scanning.
Posted: Sun Aug 19, 2007 2:38 pm
by Trond
technicorn wrote:That isn't an option if you have a huge count of items, and the
amount of items is constantly changing.
For example a server program, where people log on and off,
or databases.
Using an array for such tasks you
1. Have to redim it, at least for adding items,
2. Keep track of empty entries, or copy all itmes after a removed one down on place
that would be very impractical if the removed one was the first of, say 100000 items.
Or if you have to keep the array sorted that would mean copy 99999 items to higher places,
if the new item has to go in front of all other,
with a list that is just a question of adding one element at the front.
If lists could be as fast as arrays for random access we wouldn't have arrays. And if you could quickly insert items at the start of an array we wouldn't have lists.
That being said, there is absolutely NO reason EVER to use SelectElement(). Everything it does can be done faster with other functions.
Posted: Sun Aug 19, 2007 5:17 pm
by technicorn
@Derek
Takes 6.8 sec. on mine, just wrote that, so no one with a slower comp. think the program hangs.
@Trond
So what would that faster method be?
Using Previous/NextElement() ?
When I can program that in a loop in PB, why can't the lib do that in asm.
And yes, I could do that in asm myself, but that's beside the point
of having a function like SelectElement() for people who don't want to learn asm,
and it wouldn't be neither cross platform, nor version save,
like some of the userlibs.
Posted: Sun Aug 19, 2007 5:30 pm
by Trond
@Trond
So what would that faster method be?
Using Previous/NextElement() ?
When I can program that in a loop in PB, why can't the lib do that in asm.
And yes, I could do that in asm myself, but that's beside the point
of having a function like SelectElement() for people who don't want to learn asm,
and it wouldn't be neither cross platform, nor version save,
like some of the userlibs.
I don't understand the problem. Just avoid SelectElement(). You don't need it, ever. The reason for that, is that the following uses covers everything possible:
- If you want to access every element of the list going forwards you use a ForEach() loop.
- If you want to access every element of the list going backwards, you use a LastElement() followed by a For loop with PreviousElement().
- If you want to access a subrange of the list you should use one SelectElement() before a For loop with a NextElement() (or a PreviousElement() depending on which order you want to access the lements).
- If you want to access one particular element by ID you use ChangeCurrentElement().
That covers every use possible of the linked list, and you don't need (or want!!!!!!!!!!!!!!) SelectElement(). Where exactly is the problem? Did you read the manual?
Posted: Sun Aug 26, 2007 10:30 am
by pcfreak
here you have some workaround, btw you can't select the last element of a linkedlist with 10000 items by selecting position 10000 as the index is zero-based (possible values from 0 to 9999)
Code: Select all
Enumeration
;creates the linked list
#DLL_CREATE_LIST
;adds an element to the end of the linked list
#DLL_ADD_ELEMENT
;adds an element to the position of the current selected element
#DLL_INSERT_ELEMENT
;deletes the currently selected element
#DLL_DEL_ELEMENT
;moves the pointer to the next element
#DLL_NEXT_ELEMENT
;moves the pointer to the previous element
#DLL_PRIOR_ELEMENT
;moves the pointer to the first element
#DLL_FIRST_ELEMENT
;moves the pointer to the last element
#DLL_LAST_ELEMENT
;returns the index of the current element (-1 = no element selected, 0 = first element)
#DLL_GET_INDEX
;moves the pointer to the element defined
#DLL_SELECT_ELEMENT
;returns the number of elements in the linked list
#DLL_COUNT_ELEMENTS
;resets to pointer
#DLL_RESET_LIST
;deletes all elements of the linked list
#DLL_CLEAR_LIST
;deletes all elements of the linked list and the linked list itself, returns 0 if successful
#DLL_DELETE
EndEnumeration
Macro CreateDoublyLinkedListClass(dataVariable, dataType)
CompilerIf Defined(DoublyLinkedList_#dataType, #PB_Procedure)=#False
Structure DOUBLY_LINKED_LIST_STRUC_#dataType
size.l
index.l
*first.DOUBLY_LINKED_LIST_ENTRY_#dataType
*last.DOUBLY_LINKED_LIST_ENTRY_#dataType
*current.DOUBLY_LINKED_LIST_ENTRY_#dataType
EndStructure
Structure DOUBLY_LINKED_LIST_ENTRY_#dataType
*after.DOUBLY_LINKED_LIST_ENTRY_#dataType
*before.DOUBLY_LINKED_LIST_ENTRY_#dataType
dataVariable#.dataType#
EndStructure
Procedure.l DoublyLinkedList_#dataType#(option.l, *handle.DOUBLY_LINKED_LIST_STRUC_#dataType = 0, flag.l = 0)
Select option
Case #DLL_CREATE_LIST
*handle = 0
*handle.DOUBLY_LINKED_LIST_STRUC_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_STRUC_#dataType))
If *handle<>0
*handle\size = 0
*handle\index = -1
*handle\first = 0
*handle\last = 0
*handle\current = 0
EndIf
Case #DLL_ADD_ELEMENT
If *handle<>0
*newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
If *newEntry
*handle\index = *handle\size
*handle\size + 1
If *handle\last=0
*handle\first = *newEntry
*handle\last = *newEntry
Else
*newEntry\before = *handle\last
*handle\last\after = *newEntry
*handle\last = *newEntry
EndIf
*handle\current = *newEntry
EndIf
EndIf
Case #DLL_INSERT_ELEMENT
If *handle<>0
*newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
If *newEntry
*handle\size + 1
If *handle\current = 0
*handle\index = -1
If *handle\first=0
*handle\first = *newEntry
*handle\last = *newEntry
Else
*newEntry\after = *handle\first
*handle\first\before = *newEntry
*handle\first = *newEntry
EndIf
Else
If *handle\current\before=*handle\first
*newEntry\after = *handle\first
*handle\first\before = *newEntry
*handle\first = *newEntry
*handle\current = *newEntry
Else
*newEntry\after = *handle\current
*newEntry\before = *handle\current\before
*handle\current\before\after = *newEntry
*handle\current\before = *newEntry
*handle\current = *newEntry
EndIf
EndIf
EndIf
EndIf
Case #DLL_DEL_ELEMENT
If *handle<>0
If *handle\current<>0
*handle\size - 1
If *handle\current=*handle\first And *handle\current=*handle\last
FreeMemory(*handle\current)
*handle\first = 0
*handle\last = 0
*handle\current = 0
*handle\index = -1
ElseIf *handle\current=*handle\first
*handle\first = *handle\first\after
*handle\first\before = 0
FreeMemory(*handle\current)
*handle\current = *handle\first
ElseIf *handle\current=*handle\last
*handle\last = *handle\last\before
*handle\last\after = 0
FreeMemory(*handle\current)
*handle\current = *handle\last
*handle\index - 1
Else
*newCurrent.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle\current\after
*handle\current\before\after = *handle\current\after
*handle\current\after\before = *handle\current\before
FreeMemory(*handle\current)
*handle\current = *newCurrent
EndIf
EndIf
EndIf
Case #DLL_NEXT_ELEMENT
If *handle<>0
If *handle\current=0
*handle\current = *handle\first
*handle\index = 0
ElseIf *handle\current=*handle\last
*handle\current = 0
*handle\index = -1
Else
*handle\current = *handle\current\after
*handle\index + 1
EndIf
EndIf
Case #DLL_PRIOR_ELEMENT
If *handle<>0
If *handle\current=0
*handle\current = *handle\last
*handle\index = *handle\size - 1
ElseIf *handle\current=*handle\first
*handle\current = 0
*handle\index = -1
Else
*handle\current = *handle\current\before
*handle\index - 1
EndIf
EndIf
Case #DLL_FIRST_ELEMENT
If *handle<>0
*handle\current = *handle\first
*handle\index = 0
EndIf
Case #DLL_LAST_ELEMENT
If *handle<>0
*handle\current = *handle\last
*handle\index = *handle\size - 1
EndIf
Case #DLL_GET_INDEX
If *handle<>0
ProcedureReturn *handle\index
EndIf
Case #DLL_SELECT_ELEMENT
If *handle<>0
If flag<0 Or flag>=*handle\size
*handle\current = 0
*handle\index = -1
ElseIf flag=0 And *handle\first
*handle\current = *handle\first
*handle\index = 0
ElseIf flag=*handle\size-1
*handle\current = *handle\last
*handle\index = *handle\size - 1
ElseIf flag<*handle\index
If flag<*handle\index-flag
*handle\current = *handle\first
For i=1 To flag
*handle\current = *handle\current\after
Next
*handle\index = flag
Else
While *handle\index > flag
*handle\current = *handle\current\before
*handle\index - 1
Wend
EndIf
ElseIf flag>*handle\index
If *handle\current=0
If flag<(*handle\size-1)-flag
*handle\current = *handle\first
For i=1 To flag
*handle\current = *handle\current\after
Next
*handle\index = flag
Else
*handle\current = *handle\last
*handle\index = *handle\size - 1
While *handle\index > flag
*handle\current = *handle\current\before
*handle\index - 1
Wend
EndIf
Else
If (*handle\size-1)-flag<flag-*handle\index
*handle\current = *handle\last
*handle\index = *handle\size - 1
While *handle\index > flag
*handle\current = *handle\current\before
*handle\index - 1
Wend
Else
While *handle\index < flag
*handle\current = *handle\current\after
*handle\index + 1
Wend
EndIf
EndIf
EndIf
EndIf
Case #DLL_COUNT_ELEMENTS
If *handle<>0
ProcedureReturn *handle\size
EndIf
Case #DLL_RESET_LIST
If *handle<>0
*handle\current = 0
*handle\index = -1
EndIf
Case #DLL_CLEAR_LIST
If *handle<>0
If *handle\size<>0
*handle\current = *handle\first
*nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
While *handle\current<>0
*nextElement = *handle\current\after
FreeMemory(*handle\current)
*handle\current = *nextElement
Wend
*handle\first = 0
*handle\last = 0
*handle\current = 0
*handle\index = -1
EndIf
EndIf
Case #DLL_DELETE
If *handle<>0
If *handle\size<>0
*handle\current = *handle\first
*nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
While *handle\current<>0
*nextElement = *handle\current\after
FreeMemory(*handle\current)
*handle\current = *nextElement
Wend
FreeMemory(*handle)
*handle = 0
EndIf
EndIf
EndSelect
ProcedureReturn *handle
EndProcedure
CompilerEndIf
EndMacro
Macro InitDoublyLinkedListSortField(dataType, id, field, caseSensitive=1)
CompilerIf Defined(SortDoublyLinkedListByField_#dataType#id, #PB_Procedure)=#False
Procedure.l SortDoublyLinkedListByField_#dataType#id#(*handle1.DOUBLY_LINKED_LIST_STRUC_#dataType, option=0)
If *handle1<>0
If *handle1\size>1
*handle2.DOUBLY_LINKED_LIST_STRUC_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_STRUC_#dataType))
If *handle2<>0
*handle2\size = *handle1\size
For i=1 To *handle1\size
*newEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType))
If *newEntry<>0
If *handle2\current=0
*handle2\current = *newEntry
*handle2\first = *newEntry
Else
*newEntry\before = *handle2\current
*handle2\current\after = *newEntry
*handle2\current = *newEntry
EndIf
EndIf
Next
*handle2\last = *handle2\current
;sort here >>
left.l = 1
right.l = 1
start.l = 0
sortLen = 1
length.l = *handle1\size
While left <= length
sortLen << 1
start = 0
*handle2\current = *handle2\first
*pointerL.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle1\first
*pointerR.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle1\first
changedOrder.l = #False
While start < length
If (length - start) < sortLen
If (length - start) > (sortLen >> 1)
left = sortLen >> 1
right = length - start - left
Else
left = length - start
right = 0
EndIf
EndIf
posL.l = start
posR.l = start + left
posM.l = 0
If start=0
For i=1 To left
*pointerR = *pointerR\after
Next
Else
For i=1 To sortLen>>1
*pointerL = *pointerL\after
Next
*pointerR = *pointerL
For i=1 To left
*pointerR = *pointerR\after
Next
EndIf
While (posL < (start + left)) And (posR < (start + left + right))
CompilerIf caseSensitive=1
If option = 0
If *pointerL\field# <= *pointerR\field#
CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerL = *pointerL\after
posL + 1
Else
CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerR = *pointerR\after
posR + 1
changedOrder = #True
EndIf
Else
If *pointerL\field# >= *pointerR\field#
CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerL = *pointerL\after
posL + 1
Else
CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerR = *pointerR\after
posR + 1
changedOrder = #True
EndIf
EndIf
CompilerElse
If option = 0
If LCase(*pointerL\field#) <= LCase(*pointerR\field#)
CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerL = *pointerL\after
posL + 1
Else
CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerR = *pointerR\after
posR + 1
changedOrder = #True
EndIf
Else
If LCase(*pointerL\field#) >= LCase(*pointerR\field#)
CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerL = *pointerL\after
posL + 1
Else
CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerR = *pointerR\after
posR + 1
changedOrder = #True
EndIf
EndIf
CompilerEndIf
*handle2\current = *handle2\current\after
posM + 1
Wend
While (posL < (start + left))
*nextEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle2\current\after
CopyMemory(*pointerL+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerL = *pointerL\after
*handle2\current = *handle2\current\after
posL + 1
posM + 1
Wend
While (posR < (start + left + right))
*nextEntry.DOUBLY_LINKED_LIST_ENTRY_#dataType = *handle2\current\after
CopyMemory(*pointerR+8, *handle2\current+8, SizeOf(DOUBLY_LINKED_LIST_ENTRY_#dataType)-8)
*pointerR = *pointerR\after
*handle2\current = *handle2\current\after
posR + 1
posM + 1
Wend
start = start + sortLen
Wend
Swap *handle1, *handle2
left = sortLen
right = sortLen
If changedOrder = #False
Break
EndIf
Wend
*handle2\current = *handle2\first
*nextElement.DOUBLY_LINKED_LIST_ENTRY_#dataType
While *handle2\current<>0
*nextElement = *handle2\current\after
FreeMemory(*handle2\current)
*handle2\current = *nextElement
Wend
;sort here <<
FreeMemory(*handle2)
EndIf
EndIf
*handle1\current = 0
*handle1\index = -1
EndIf
ProcedureReturn *handle1
EndProcedure
CompilerEndIf
EndMacro
Macro SortDoublyLinkedListByField(dataType, id, handle, option=0)
SortDoublyLinkedListByField_#dataType#id#(handle, option)
EndMacro
Macro DefineDoublyLinkedList(variable, dataType)
variable#.DOUBLY_LINKED_LIST_STRUC_#dataType
EndMacro
Macro DoublyLinkedList(dataType, option, handle=0, flag=0)
DoublyLinkedList_#dataType#(option, handle, flag)
EndMacro
Macro DLLForEach(handle)
If handle#\first
handle#\current = handle#\first
handle#\index = 0
While handle#\current<>0
EndMacro
Macro DLLNext(handle)
handle#\current = handle#\current\after
handle#\index + 1
Wend
handle#\index=-1
EndIf
EndMacro
CreateDoublyLinkedListClass(value, l)
InitDoublyLinkedListSortField(l, 1, value)
DefineDoublyLinkedList(*list1, l)
*list1 = DoublyLinkedList(l, #DLL_CREATE_LIST)
For a = 0 To 10000
*list1 = DoublyLinkedList(l, #DLL_ADD_ELEMENT, *list1)
*list1\current\value = a
Next
tStart.l = ElapsedMilliseconds()
For n = 1 To 5000
For i = 1 To 10
*list1 = DoublyLinkedList(l, #DLL_SELECT_ELEMENT, *list1, i)
Next
Next
tExec1.d = (ElapsedMilliseconds() - tStart) / 1000.0
tStart = ElapsedMilliseconds()
For n = 1 To 5000
For i = 9990 To 10000
*list1 = DoublyLinkedList(l, #DLL_SELECT_ELEMENT, *list1, i)
Next
Next
tExec2.d = (ElapsedMilliseconds() - tStart) / 1000.0
*list1 = DoublyLinkedList(l, #DLL_DELETE, *list1)
MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end: " + StrD(tExec2, 3))
Posted: Sun Aug 26, 2007 3:08 pm
by Fred
SelectElement() isn't optimized for speed, it is a convenience function. You have to use Previous/NextElement() to iterate through the list with maximum speed.
BTW, rewriting SelectElement() in asm won't change anything, it's an algorithm problem.
Posted: Sun Aug 26, 2007 3:28 pm
by Ollivier
Else you can create a temporary array during the treatment.
Code: Select all
Procedure Map(Lst() )
max.L = CountList(Lst() )
Global Dim *Ptr(max)
n.L = 0
ResetList(Lst())
While NextElement(Lst())
*Ptr(n) = @Lst()
n + 1
Wend
EndProcedure
Procedure EndMap()
Global Dim *Ptr(0)
EndProcedure
Define n.l, nEnd.l = 5000
Define i.l, iEnd.l = 10000
Define tStart.l, tExec1.d, tExec2.d
NewList l1.l()
For i = 1 To iEnd
AddElement(l1())
l1() = i
Next i
Map(l1() )
tStart = ElapsedMilliseconds()
For n = 1 To nEnd
For i = 1 To 10
;SelectElement(l1(), i)
ChangeCurrentElement(l1(), *Ptr(i) )
Next i
Next n
tExec1 = (ElapsedMilliseconds() - tStart) / 1000.0
tStart = ElapsedMilliseconds()
For n = 1 To nEnd
For i = 9990 To 10000
;SelectElement(l1(), i)
ChangeCurrentElement(l1(), *Ptr(i) )
Next i
Next n
tExec2 = (ElapsedMilliseconds() - tStart) / 1000.0
EndMap()
MessageRequester("Timing", "List begin: " + StrD(tExec1, 3) + #LF$ + "List end: " + StrD(tExec2, 3))
Posted: Sun Aug 26, 2007 4:50 pm
by technicorn
Thanks pcfreak and Ollivier,
but I want to stick with the PB lists, because they can be viewed with the debugger,
and already using an algorithm to get faster to the wanted index by avoiding SelectElement().
@Fred
I was just surprised that SelectElement() isn't using the same flag that ListIndex() does to select an internal prev/next algo to get to the selected element.
I'll simply avoid using SelectElement() now that I know that.
Posted: Tue Aug 28, 2007 9:32 pm
by Ollivier
I don't understand what do you really want : 'stick with the PB list'
What is the goal?
Posted: Wed Aug 29, 2007 12:39 pm
by nco2k
Fred wrote:SelectElement() isn't optimized for speed, it is a convenience function. You have to use Previous/NextElement() to iterate through the list with maximum speed.
fred, the problem is that SelectElement() ignores the current index position and always starts to search from the beginning of the list. it would be much faster, if it would behave like in this example by Deem2031:
Code: Select all
EnableASM
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 Abs(WaytoCurrent) < WaytoLast And Abs(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 "----------------------------"
a position dependent SelectElement() was requested many times, i dont understand why it hasnt been changed yet.
c ya,
nco2k
Posted: Wed Aug 29, 2007 3:13 pm
by Trond
a position dependent SelectElement() was requested many times, i dont understand why it hasnt been changed yet.
World peace was also requested quite a few times. Besides, as I said above, you never need SelectElement().
Posted: Wed Aug 29, 2007 4:16 pm
by Ollivier
It's clear! I'm ok with Trond : using an array is the best solution, I posted the code above. If you want to know where there is a bug, you create a 2nd array. Each element of this second array can contain flags and values allowing tracability. It's speed. If there's a problem of available memory, you could use a memory area instead of these arrays.
I think 'SelectElement' was created to avoid allocating too much memory!
Nice coding
