Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > BlitzMax

Ответ
 
Опции темы
Старый 06.08.2011, 17:15   #1
Черный крыс
 
Сообщений: n/a
Ускоренный 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"
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Nerd (06.08.2011)
Старый 08.08.2011, 11:52   #2
dimanche13
Мастер
 
Регистрация: 19.03.2007
Сообщений: 1,039
Написано 153 полезных сообщений
(для 252 пользователей)
Ответ: Ускоренный TList

слово с 6-тью буквами "ы" ?
забыл как здесь ставится срач-тэг, короче когда-то, я С двухсвязные списки биндил в БМ и сравнивал с родными БМовскими по скорости. Выяснилось, в ближайшем приближении, что они примерно одинаковы.
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Черный крыс (16.10.2011)
Старый 16.10.2011, 22:43   #3
Черный крыс
 
Сообщений: n/a
Ответ: Ускоренный TList

2 dimanche13

А мою работу тестировал? какие результаты?

Сигареты в руках, чай на столе –
эта схема проста,
И больше нет ничего -
все находится в нас
Респект тебе! +1
Я тоже кроме Цоя, Высоцкого и Шевчука никого не признаю... =)

ЗЫ
А снег идет весь день...
А снег идет стеной...
А за той стеной...
Стоит апрель!
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Reizel (17.10.2011)
Старый 26.03.2012, 11:54   #4
dimanche13
Мастер
 
Регистрация: 19.03.2007
Сообщений: 1,039
Написано 153 полезных сообщений
(для 252 пользователей)
Ответ: Ускоренный TList

Привет, оставлю здесь ссылку
http://www.blitzmax.com/Community/posts.php?topic=97352
там приведен тест выполнения перебора контейнеров с объектами

результат:
_next:item speed= 312
eachin speed= 1037
TLink speed= 762
Array speed= 65
Array eachin speed= 65

вывод, хотите скорости - юзайте массивы, нужны списки - перебирайте через _next
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Жека (26.03.2012)
Старый 11.04.2012, 08:45   #5
Matt Merkulov
Модератор
 
Аватар для Matt Merkulov
 
Регистрация: 23.10.2005
Сообщений: 219
Написано 62 полезных сообщений
(для 247 пользователей)
Ответ: Ускоренный TList

Сообщение от Diablo1909 Посмотреть сообщение
Приветствую!
Практически по всем показателям мой лист оказался быстрее кроме одного метода - RemoveLast()
Еще InsertBeforeLink.

Такой вопрос: зачем писать +~0 вместо -1? Так быстрее разве?
(Offline)
 
Ответить с цитированием
Старый 11.04.2012, 13:28   #6
Платон Александрович
Нуждающийся
 
Аватар для Платон Александрович
 
Регистрация: 05.10.2011
Адрес: Россия, Южно-Сахалинск
Сообщений: 66
Написано 42 полезных сообщений
(для 83 пользователей)
Ответ: Ускоренный TList

Сообщение от Matt Merkulov Посмотреть сообщение
Такой вопрос: зачем писать +~0 вместо -1? Так быстрее разве?
Это константное выражение, без разницы как по скорости, так и по результату, но видимо ему нравится "усложнять" себе задачи
(Offline)
 
Ответить с цитированием
Старый 12.04.2012, 22:57   #7
Черный крыс
 
Сообщений: n/a
Ответ: Ускоренный TList

Такой вопрос: зачем писать +~0 вместо -1? Так быстрее разве?
Да вродь наскок я знаю ассемблерный код сгенерится более оптимальным ( может и ошибаюсь )

[спустя некоторое время]

Провел тест - разницы действительно никакой.
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 04:01.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com