forum.boolean.name - Ускоренный TList

Приветствую!

Как то давно Джимон делал кэшируемый TList, я подхватил это начинание и представляю вам наиболее оптимизированную версию.

Основное отличие в том что он является односвязным - отсюда выигрыш в скорости, так как в нем происходят меньше телодвижений в различных операциях.

Практически по всем показателям мой лист оказался быстрее кроме одного метода - RemoveLast()

Модуль :

Код:



Rem

 Copyright (c) 2011 Al'bert Gaskarov

 

 Permission is hereby granted, free of charge, to any person obtaining a copy

 of this software and associated documentation files (the "Software"), to deal

 in the Software without restriction, including without limitation the rights

 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the Software is

 furnished to do so, subject to the following conditions:

 

 The above copyright notice and this permission notice shall be included in

 all copies or substantial portions of the Software.

 

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

 THE SOFTWARE.

 

endrem

SuperStrict

Module api.list

ModuleInfo "Версия : 1.01"

ModuleInfo "Автор : Al'bert G."

ModuleInfo "Лицензия : GPL"

ModuleInfo "Правообладатель : Dynamic bytes"

ModuleInfo "Сервер : API"

ModuleInfo "История: 1.01"

ModuleInfo "История: Некоторые оптимизации"

ModuleInfo "История: 1.0"

ModuleInfo "История: Первый релиз"

Private

Global _prev:TLink = Null

Type THeadLink Extends TLink

 Field _length:Int

 

 Method Delete()

  _length = Null

 End Method

End Type

Public

Type TLink

 Field _next:TLink

 Field _value:Object

  

 Method Delete()

  _next = Null

  _value = Null

 End Method

End Type

Type TList

 Field _head:TLink

 

 Method _pad()

 End Method

 

 Method New()

  _head = New THeadLink

  _head._next = _head

  _head._value = _head

 End Method

?Not Threaded

 Method Delete()

  Clear()

  _head._next = Null

  _head._value = Null

  _head = Null

 End Method

?

 Method Clear()

  _head._value = _head

  THeadLink(_head)._length = 0

  While _head._next <> _head

  _head._next._value = Null

  _head._next = _head._next._next

  Wend

 End Method

 

 Method Count:Int()

  Return THeadLink(_head)._length

 End Method

 

 Method Contains:Byte(value:Object)

  Local link:TLink = _head._next

  While link <> _head

  If (link._value.Compare(value) = 0) Then Return True

  link = link._next

  Wend

 End Method

 

 Method AddFirst:TLink(value:Object)

  'Assert value Else "Can't insert Null object into list"

  Local link:TLink = New TLink

  link._value = value

  link._next = _head._next

  If (link._next = _head) Then _head._value = link

  THeadLink(_head)._length:-~0

  Return link

 End Method

 

 Method AddLast:TLink(value:Object)

  'Assert value Else "Can't insert Null object into list"

  Local link:TLink = New TLink'.Create(_head, value)

  link._value = value

  link._next = _head

  TLink(_head._value)._next = link

  _head._value = link

  THeadLink(_head)._length:-~0

  Return link

 End Method

 

 Method First:Object()

  If Not THeadLink(_head)._length Then Return Null

  Return _head._next._value

 End Method

 

 Method Last:Object()

  If Not THeadLink(_head)._length Then Return Null

  Return TLink(_head._value)._value

 End Method

 

 Method RemoveFirst:Object()

  If Not THeadLink(_head)._length Then Return Null

  Local value:Object = _head._next._value

  _head._next = _head._next._next

  THeadLink(_head)._length:+~0

  Return value

 End Method

 

 Method RemoveLast:Object()

  If Not THeadLink(_head)._length Then Return Null

  Local link:TLink = FindLink(TLink(_head._value)._value)

  Local value:Object = link._value

  _prev._next = _head

  _head._value = _prev

  THeadLink(_head)._length:+~0

  _prev = Null

  Return value

 End Method

 

 Method FindLink:TLink(value:Object)

  _prev = _head

  Local link:TLink = _head._next

  While link <> _head

  If (link._value.Compare(value) = 0) Then Return link

  _prev = link

  link = link._next

  Wend

 End Method

 

 Method Remove:Byte(value:Object)

  Local link:TLink = FindLink(value)

  If Not link

  _prev = Null

  Return False

  EndIf

  _prev._next = link._next

  THeadLink(_head)._length:+~0

  _prev = Null

  Return True

 End Method

 

 Method FirstLink:TLink()

  If (_head._next <> _head) Then Return _head._next

 End Method

 

 Method LastLink:TLink()

  If (THeadLink(_head)._length > 0) Then Return TLink(_head._value)

 End Method

 

 Method InsertAfterLink:TLink(value:Object, link:TLink)

  Local nlink:TLink = New TLink

  nlink._value = value

  nlink._next = link._next

  link._next = nlink

  THeadLink(_head)._length:-~0

  Return nlink

 End Method

 

 Method InsertBeforeLink:TLink(value:Object, link:TLink)

  Local nlink:TLink = New TLink

  nlink._value = value

  FindLink(link._value)

  _prev._next = nlink

  _prev = Null

  nlink._next = link

  THeadLink(_head)._length:-~0

  Return nlink

 End Method

 

 Method ValueAtIndex:Object(index:Int)

  Local link:TLink = _head._next

  While link <> _head

  If (index = 0) Then Return link._value

  link = link._next

  index:+~0

  Wend

 End Method

 

 Method Copy:TList()

  Local list:TList = New TList

  Local link:TLink = _head._next

  While link <> _head

  list.AddLast(link._value)

  link = link._next

  Wend

  Return list

 End Method

 

 Method Swap(list:TList)

  Local head:TLink = _head

  _head = list._head

  list._head = head

 End Method

 

 Method ToArray:Object[]()

  Local array:Object[THeadLink(_head)._length], i:Int

  Local link:TLink = _head._next

  While link <> _head

  array[i] = link._value

  link = link._next

  i:-~0

  Wend

  Return array

 End Method

 

 Function FromArray:TList(array:Object[])

  Local list:TList = New TList

  For Local i:Int = 0 Until array.Length

  list.AddLast(array[i])

  Next

  Return list

 End Function

 

 Method Reverse:TList()

  Local list:TList = New TList

  Local link:TLink = _head._next

  While link <> _head

  list.AddFirst(link._value)

  link = link._next

  Wend

  Return list

 End Method

 

 Method ObjectEnumerator:TListEnum()

  Return New TListEnum.Create(_head)

 End Method

End Type

Type TListEnum

 Field _link:TLink

 Field _length:Int

 

 Method Delete()

  _link = Null

  _length = Null

 End Method

 

 Method Create:TListEnum(link:TLink)

  _link = link

  _length = THeadLink(link)._length

  Return Self

 End Method

 

 Method HasNext:Int()

  Return (_length <> 0)

 End Method

 

 Method NextObject:Object()

  _length:+~0

  _link = _link._next

  Return _link._value

 End Method

End Type

Тест

Код:



'Framework api.list

Import brl.blitz

Local list:TList = New TList

Local s:String = "4"

Local i:Int

Local speed:Int = MilliSecs()

For i = 0 Until 200000

 list.AddLast(s)

Next

'WriteStdout "Count = " + list.Count() + "~n"

speed = MilliSecs() - speed

WriteStdout "AddLast Test: "+ speed + "~n"

speed:Int = MilliSecs()

For s:String = EachIn list

 'list.Remove(s)

Next

speed = MilliSecs() - speed

WriteStdout "EachIn Test: "+ speed + "~n"

speed:Int = MilliSecs()

For i = 0 Until 1000

 list.Count()

Next

speed = MilliSecs() - speed

WriteStdout "Count Test: "+ speed + "~n"

speed:Int = MilliSecs()

For s:String = EachIn list

 list.Remove(s)

Next

speed = MilliSecs() - speed

WriteStdout "EachIn Remove Test: "+ speed + "~n"