Linked List Benchmark -> ListIndex() is very slow

[dige]

ForEach - Next ist very handy. But if you need the current index,
you have to use ListIndex() wich is very slow in some cases.

The best choice ist For ... NextElement() .... next

Please try this code:

Code: Select all

NewList Test.s()
#MAX = 20000

Debug "-------LinkedList Benchmarking-------"

count = GetTickcount_()
For a = 1 To #MAX
  AddElement( Test() )
  Test() = Space(Random(255))
Next
Debug "Adding: " + Str(GetTickcount_() - count)

count = GetTickcount_()
ForEach Test()
  Test() = Space(Random(255))
  i = ListIndex(Test())
Next
Debug "ForEach + ListIndex " + Str(GetTickcount_() - count)

count = GetTickcount_()
ResetList( Test() )
For a = 1 To #MAX
  NextElement(Test())
  Test() = Space(Random(255))
Next
Debug "For Next -> " + Str(GetTickcount_() - count)

count = GetTickcount_()
For a = #MAX To 1 Step -1
  PreviousElement( Test() )
  Test() = Space(Random(255))
Next
Debug "For Next <- " + Str(GetTickcount_() - count)

count = GetTickcount_()
For a = 1 To #MAX
  SelectElement( Test(), a )
  Test() = Space(Random(255))
Next
Debug "For Next + Select  " + Str(GetTickcount_() - count)

count = GetTickcount_()
ResetList( Test() )
For a = 1 To #MAX
  NextElement(Test())
  i = ListIndex(Test())
  Test() = Space(Random(255))
Next
Debug "ForNext + ListIndex " + Str(GetTickcount_() - count)

cya dige

[freedimension]

Interesting Results. But please, never use the Debugger while Benchmarking, it can falsify the results.

Better use:

Code: Select all

OpenConsole()

NewList Test.s() 
#MAX = 5000 

count = GetTickcount_() 
For a = 1 To #MAX 
  AddElement( Test() ) 
  Test() = Space(Random(255)) 
Next 
PrintN("Adding: " + Str(GetTickcount_() - count))

count = GetTickcount_() 
ForEach Test() 
  Test() = Space(Random(255)) 
  i = ListIndex(Test()) 
Next 
PrintN("ForEach + ListIndex " + Str(GetTickcount_() - count))

count = GetTickcount_() 
ResetList( Test() ) 
For a = 1 To #MAX 
  NextElement(Test()) 
  Test() = Space(Random(255)) 
Next 
PrintN("For Next -> " + Str(GetTickcount_() - count) )

count = GetTickcount_() 
For a = #MAX To 1 Step -1 
  PreviousElement( Test() ) 
  Test() = Space(Random(255)) 
Next 
PrintN("For Next <- " + Str(GetTickcount_() - count) )

count = GetTickcount_() 
For a = 1 To #MAX 
  SelectElement( Test(), a ) 
  Test() = Space(Random(255)) 
Next 
PrintN("For Next + Select  " + Str(GetTickcount_() - count) )

count = GetTickcount_() 
ResetList( Test() ) 
For a = 1 To #MAX 
  NextElement(Test()) 
  i = ListIndex(Test()) 
  Test() = Space(Random(255)) 
Next 
PrintN("ForNext + ListIndex " + Str(GetTickcount_() - count))

Input()

[Fred]

ListIndex() always start from the start of the list to find the element index, as a list element doesn't store its index (any element can be inserted, removed etc...). It's not supposed to be used to get the current index from a sequential loop, which is of course a bad test (you have it with 'a' ). This function is as efficient as possible (asm written).