Приветствую!
Как то давно Джимон делал кэшируемый 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"