Ooops
March 01, 2021, 10:00:29 PM

Author Topic: [bmx] StringList by Perturbatio [ 1+ years ago ]  (Read 469 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] StringList by Perturbatio [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
Title : StringList
Author : Perturbatio
Posted : 1+ years ago

Description : (BMax)
Bmax stringlist with most of the TList functionality.
It is in a lot of instances faster, and uses less memory.
Internally, it uses an array so you can simply address the elements like an array (there are some issues with doing so because of the method used to resize), but if you ensure the element isn't null beforehand, there shouldn't be a probem.


Code :
Code: BlitzMax
  1. SuperStrict
  2.  
  3. Framework BRL.Retro
  4. Import BRL.System
  5.  
  6. Rem
  7. Stringlist created by Kris Kelly (Perturbatio) Dec 2005
  8. purpose: faster access to a list of strings with less mem usage
  9. it's performance is comparable to a TList when using a small number of strings
  10. but when you are using a large amount, it is much better (and uses less memory).
  11.  
  12. When invoking the create method, you can specify the StepSize, this is the amount that
  13. the Items Array will be increased by each time it is in danger of running out of space.
  14. It is faster to do it in large blocks than in hundreds of little ones.
  15. End Rem
  16.  
  17. Type TStringList
  18.         Field Items:String[]
  19.         Field _Size:Int = 0 'DO NOT MANUALLY MODIFY THIS!!!
  20.         Field StepSize:Int
  21.        
  22.         Method AddFirst(val:String)
  23.                 Local i:Int
  24.  
  25.                 'grow Items array by 1
  26.                 'Items = Items[..Items.Length + 1]
  27.                 _Size:+1
  28.                 'resize in bulk
  29.                 If Items.Length < _Size Then Items = Items[.._Size+StepSize]
  30.                
  31.                
  32.                 'shift Items to the rightt, overwriting val
  33.                 For i = 1 To _Size-1 'Items.Length - 1
  34.                         Items[i] = Items[i - 1]
  35.                 Next
  36.                
  37.                 Items[0] = val
  38.                 'no need to return anything here since we know it was added at 0
  39.         End Method
  40.        
  41.        
  42.         Method AddLast:Int(val:String)
  43.                 'grow Items array by 1
  44.                 'Items = Items[..Items.Length + 1]
  45.                 _Size:+1
  46.                 'resize in bulk
  47.                 If Items.Length < _Size Then Items = Items[.._Size+StepSize]
  48.                
  49.                 'set the last index to val
  50.                 'Items[Items.Length - 1] = val
  51.  
  52.                 Items[_Size-1] = val
  53.                
  54.                 Return _Size 'Items.Length - 1 'return the index it was added at
  55.         End Method
  56.        
  57.        
  58.         'return the entire list as a concatenated string with optional delimiter
  59.         'because base objects have ToString, cannot override with different parameters
  60.         Method ToDelimString:String(Delim:String = "")
  61.                 Local result:String
  62.                 Local i:Int
  63.                
  64.                 For i = 0 To _Size-2
  65.                         result:+Items[i] + Delim
  66.                 Next
  67.                 result:+ Items[_Size-1]
  68.                
  69.                 Return result
  70.         End Method
  71.        
  72.        
  73.         Method ToString:String()
  74.                 Return ToDelimString() 'just call ToDelimString with no parameters
  75.         End Method
  76.        
  77.         'You could just reference the field _Size (which is what is done throughout the code),
  78.         'but that could result in an unsafe type if you
  79.         Method Count:Int()
  80.                 Return _Size
  81.         End Method
  82.        
  83.        
  84.         'return the first index where the list contains val, else return -1
  85.         Method Contains:Int(val:String, CaseSensitive:Int = False)
  86.                 Local i:Int
  87.                
  88.                 For i = 0 To _Size-1
  89.                         Select CaseSensitive
  90.                                 Case True
  91.                                         If val = Items[i] Then Return i
  92.                                 Case False
  93.                                         If val.ToUpper() = Items[i].ToUpper() Then Return i
  94.                         End Select
  95.                        
  96.                 Next
  97.                
  98.                 Return -1
  99.         End Method
  100.        
  101.        
  102.         Function FromStringArray:TStringList(val:String[])
  103.                 Local tempList:TStringList = TStringList.Create()
  104.                
  105.                 Try
  106.                         tempList.Items = val
  107.                 Catch err:String
  108.                         RuntimeError("Error when converting from String Array to TStringList, error: ~n"+err$)
  109.                         Return Null
  110.                 End Try
  111.                
  112.                 Return tempList
  113.         End Function
  114.        
  115.        
  116.         Function FromString:TStringList(val:String, Delim:String)
  117.                 Local tempList:TStringList = TStringList.Create()
  118.                 Local currentChar : String = ""
  119.                 Local count : Int = 0
  120.                 Local TokenStart : Int = 0
  121.                         If Delim.Length <0 Or Delim.Length > 1 Then Return Null
  122.        
  123.                         If Len(Delim)<>1 Then Return Null
  124.        
  125.                         val = Trim(val)
  126.        
  127.                         For count = 0 Until Len(val)
  128.                                 If val[count..count+1] = delim Then
  129.                                         tempList.AddLast(val[TokenStart..Count])
  130.                                         TokenStart = count + 1
  131.                                 End If
  132.                         Next
  133.                         tempList.AddLast(val[TokenStart..Count])       
  134.                        
  135.                 Return tempList
  136.         End Function
  137.  
  138.  
  139.         'if AutoAddToEnd is true then if the index specified is greater than size, use AddLast
  140.         Method Insert:Int(val:String, index:Int, AutoAddToEnd:Int = False)
  141.                 Local i:Int
  142.                
  143.                 'If index is out of range, Return False
  144.                 If index < 0 Then Return False
  145.                 If index > _Size Then
  146.                         If Not AutoAddToEnd Then
  147.                                 Return False
  148.                         Else
  149.                                 AddLast(val)
  150.                                 Return True
  151.                         EndIf
  152.                 EndIf
  153.                
  154.                 'if the index is equal to Size then addlast
  155.                 If index = _Size Then
  156.                         AddLast(val)
  157.                         Return True
  158.                 EndIf
  159.  
  160.                 'resize Items
  161.                 'Items = Items[..Items.Length]
  162.                 _Size:+1
  163.                 'resize in bulk
  164.                 If Items.Length < _Size Then Items = Items[.._Size + StepSize]
  165.  
  166.                
  167.                 'shift Items to the right from index
  168.                 For i = _Size-1 To index+1 Step -1
  169.                         Items[i] = Items[i - 1]
  170.                         'Print "index "+ i + " " + items[i]
  171.                 Next
  172.                
  173.                 'then insert val
  174.                 Items[index] = val
  175.                 Return True
  176.         End Method
  177.        
  178.        
  179.         Method RemoveByIndex:Int(index:Int)
  180.                 Local i:Int
  181.  
  182.                 'shift Items to the left, overwriting index
  183.                 For i = index To _Size - 2
  184.                         Items[i] = Items[i + 1]
  185.                 Next
  186.                
  187.                 'shrink Items by 1
  188.                 'Items = Items[..Items.Length]
  189.                 _Size:-1
  190.                 'if the length of items is at least (2 *StepSize) larger than Size, resize the array
  191.                 'this should help prevent the size from getting out of control but keep it reasonably fast
  192.                 If _Size < Items.Length - (StepSize * 2) Then Items = Items[.._Size]
  193.                 If _Size < 0 Then _Size = 0
  194.                 'null the end one
  195.                 Items[_Size] = Null
  196.         End Method
  197.        
  198.        
  199.         Method RemoveByString:Int(val:String, CaseSensitive:Int = False, RemoveAll:Int = False)
  200.                 Local i:Int
  201.  
  202.                 i = Contains(val, CaseSensitive)
  203.                 While i > -1
  204.                        
  205.                         RemoveByIndex(i)
  206.                         If Not RemoveAll Then Return True
  207.                         i = Contains(val, CaseSensitive)
  208.  
  209.                 Wend
  210.                
  211.                 Return True
  212.         End Method
  213.        
  214.        
  215.         Method Clear()
  216.                 Items = Items[..0]
  217.                 _Size = 0
  218.         End Method
  219.  
  220.        
  221.         Method ToArray:String[]()
  222.                 Return Items
  223.         End Method
  224.        
  225.        
  226.         Method ToList(List:TList Var)
  227.                 For Local s:String = EachIn items
  228.                         List.AddLast(s)
  229.                 Next
  230.         End Method
  231.        
  232.        
  233.         Method GetStepSize:Int()
  234.                 Return StepSize
  235.         End Method
  236.        
  237.         Method SetStepSize(val:Int)
  238.                 If val < 1 Then val = 1 'don't allow negative values
  239.                 StepSize = val
  240.         End Method
  241.        
  242.        
  243.         Method Sort()
  244.                 Items.Sort()
  245.         End Method
  246.        
  247.        
  248.         Method Free()
  249.                 TStringList.Destroy(Self)
  250.         End Method
  251.        
  252.        
  253.         Method SaveToFile(filename:String)
  254.                 Local fs:TStream = WriteFile(filename)
  255.                 Local i:Int
  256.                
  257.                 For i=0 To _Size-1
  258.                         WriteLine(fs, Items[i])
  259.                 Next
  260.                 CloseFile(fs)
  261.         End Method
  262.        
  263.        
  264.         Method LoadFromFile(filename:String)
  265.                 Local fs:TStream = OpenFile(filename)
  266.                 If Not fs Then Return
  267.                 Clear()
  268.                
  269.                 While Not Eof(fs)
  270.                         AddLast(ReadLine(fs))
  271.                 Wend
  272.                
  273.                 CloseFile(fs)
  274.         End Method
  275.        
  276.        
  277.         Function Destroy(sl:TStringList)
  278.                 sl.Clear()
  279.                 sl = Null
  280.                 GCCollect
  281.         End Function
  282.        
  283.        
  284.         Function Create:TStringList(StepSize:Int = 10)
  285.                 Local tempList:TStringList = New TStringList
  286.                 tempList.StepSize = StepSize
  287.                 Return tempList
  288.         End Function
  289. End Type
  290.  
  291. Rem test Insert
  292. Global sl:TStringList = TStringList.Create(10)
  293.  
  294. sl.AddLast("A")
  295. sl.AddLast("B")
  296. sl.AddLast("D")
  297. sl.AddLast("f")
  298. Print sl.ToString()
  299. sl.Insert("C", 2)
  300. Print sl.ToString()
  301. sl.Insert("E", 4)
  302. Print sl.ToString()
  303.  
  304. 'sl.RemoveByIndex(2)
  305.  
  306. For Local s:String = EachIn sl.Items
  307.         If s<>Null Then Print s
  308. Next
  309.  
  310. sl.AddLast("f")
  311. sl.AddLast("f")
  312. sl.AddLast("f")
  313. sl.AddLast("F")
  314. sl.RemoveByString("f", True, True)
  315. Print sl.ToDelimString("-")
  316.  
  317. End Rem
  318.  
  319.  
  320. 'Rem test speed
  321. SeedRnd MilliSecs()
  322.  
  323. Global numberOfIterations:Int = 9999 'increase this to see the performance difference
  324.  
  325.  
  326. 'Test a TStringList
  327. Print "~nTStringList:~n"
  328. Global sl:TStringList = TStringList.Create(10000) 'change this to a 1 and see the performance change
  329.  
  330.  
  331. Local starttime:Int = MilliSecs()
  332.  
  333. For Local i:Int = 0 To numberOfIterations
  334.         sl.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
  335. Next
  336.  
  337. sl.Sort()
  338.  
  339. Print MilliSecs()-Starttime + "ms"
  340. GCCollect()
  341. Print (GCMemAlloced()/1024)+"kb used"
  342.  
  343.  
  344. sl.Free()
  345. Print (GCMemAlloced()/1024)+"kb after free"
  346.  
  347.  
  348. 'test a TList
  349. Print "~nTList:~n"
  350. Global sl2:TList = New TList
  351.  
  352.  
  353. starttime:Int = MilliSecs()
  354.  
  355. For Local i:Int = 0 To numberOfIterations
  356.         sl2.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
  357. Next
  358.  
  359. sl2.Sort()
  360.  
  361.  
  362. Print MilliSecs()-Starttime + "ms"
  363. GCCollect()
  364. Print (GCMemAlloced()/1024)+"kb used"
  365. sl2 = Null
  366. GCCollect()
  367. Print (GCMemAlloced()/1024)+"kb after free"
  368.  
  369. 'EndRem


Comments :


Koriolis(Posted 1+ years ago)

 Note: given that you don't inherit from TList (which wouldn't make sense anyway) or any other "interface" class, you should make all your methods final. That will give you another little speed boost, as there will no be dynamic dispatch anymore.By the way why limiting it to strings? Strings are just objects in BlitzMax, so there's not much to gain by constraining the elements to strings (well, admitedly you free yourself from constant casts, but a more general purpose implementation would be good nonetheless).EDIT: Oh, I see you also have some methods very specific to strings. Anyway, a general purpose version would still be good :)


Perturbatio(Posted 1+ years ago)

 Do you mean something like this?
Code: [Select]
SuperStrict

Framework BRL.Retro
Import BRL.System

Rem
ObjectList created by Kris Kelly (Perturbatio) Dec 2005
purpose: faster access to a list of objects with less mem usage
it's performance is comparable to a TList when using a small number of strings
but when you are using a large amount, it is much better (and uses less memory).

When invoking the create method, you can specify the StepSize, this is the amount that
the Items Array will be increased by each time it is in danger of running out of space.
It is faster to do it in large blocks than in hundreds of little ones.
End Rem

Type TObjectList
Field Items:Object[]
Field _Size:Int = 0 'DO NOT MANUALLY MODIFY THIS!!!
Field StepSize:Int

Method AddFirst(val:Object)
Local i:Int

'grow Items array by 1
'Items = Items[..Items.Length + 1]
_Size:+1
'resize in bulk
If Items.Length < _Size Then Items = Items[.._Size+StepSize]


'shift Items to the rightt, overwriting val
For i = 1 To _Size-1 'Items.Length - 1
Items[i] = Items[i - 1]
Next

Items[0] = val
'no need to return anything here since we know it was added at 0
End Method


Method AddLast:Int(val:Object)
'grow Items array by 1
'Items = Items[..Items.Length + 1]
_Size:+1
'resize in bulk
If Items.Length < _Size Then Items = Items[.._Size+StepSize]

'set the last index to val
'Items[Items.Length - 1] = val

Items[_Size-1] = val

Return _Size 'Items.Length - 1 'return the index it was added at
End Method


'return the entire list as a concatenated string with optional delimiter
'because base objects have ToString, cannot override with different parameters
Method ToDelimString:String(Delim:String = "")
Local result:String
Local i:Int

For i = 0 To _Size-2
result:+Items[i].ToString() + Delim
Next
result:+ Items[_Size-1].ToString()

Return result
End Method


Method ToString:String()
Return ToDelimString() 'just call ToDelimString with no parameters
End Method

'You could just reference the field _Size (which is what is done throughout the code),
'but that could result in an unsafe type if you
Method Count:Int()
Return _Size
End Method


'return the first index where the list contains val, else return -1
Method Contains:Int(val:Object)
Local i:Int

For i = 0 To _Size-1
If val = Items[i] Then Return i
Next

Return -1
End Method


Function FromObjectArray:TObjectList(val:Object[])
Local tempList:TObjectList = TObjectList.Create()

Try
tempList.Items = val
Catch err:String
RuntimeError("Error when converting from Object Array to TObjectList, error: ~n"+err$)
Return Null
End Try

Return tempList
End Function

Rem
Function FromString:TObjectList(val:String, Delim:String)
Local tempList:TObjectList = TObjectList.Create()
Local currentChar : String = ""
Local count : Int = 0
Local TokenStart : Int = 0
If Delim.Length <0 Or Delim.Length > 1 Then Return Null

If Len(Delim)<>1 Then Return Null

val = Trim(val)

For count = 0 Until Len(val)
If val[count..count+1] = delim Then
tempList.AddLast(val[TokenStart..Count])
TokenStart = count + 1
End If
Next
tempList.AddLast(val[TokenStart..Count])

Return tempList
End Function
EndRem

'if AutoAddToEnd is true then if the index specified is greater than size, use AddLast
Method Insert:Int(val:Object, index:Int, AutoAddToEnd:Int = False)
Local i:Int

'If index is out of range, Return False
If index < 0 Then Return False
If index > _Size Then
If Not AutoAddToEnd Then
Return False
Else
AddLast(val)
Return True
EndIf
EndIf

'if the index is equal to Size then addlast
If index = _Size Then
AddLast(val)
Return True
EndIf

'resize Items
'Items = Items[..Items.Length]
_Size:+1
'resize in bulk
If Items.Length < _Size Then Items = Items[.._Size + StepSize]


'shift Items to the right from index
For i = _Size-1 To index+1 Step -1
Items[i] = Items[i - 1]
'Print "index "+ i + " " + items[i]
Next

'then insert val
Items[index] = val
Return True
End Method


Method RemoveByIndex:Int(index:Int)
Local i:Int

'shift Items to the left, overwriting index
For i = index To _Size - 2
Items[i] = Items[i + 1]
Next

'shrink Items by 1
'Items = Items[..Items.Length]
_Size:-1
'if the length of items is at least (2 *StepSize) larger than Size, resize the array
'this should help prevent the size from getting out of control but keep it reasonably fast
If _Size < Items.Length - (StepSize * 2) Then Items = Items[.._Size]
If _Size < 0 Then _Size = 0
'null the end one
Items[_Size] = Null
End Method


Method RemoveByObject:Int(val:Object, RemoveAll:Int = False)
Local i:Int

i = Contains(val)
While i > -1

RemoveByIndex(i)
If Not RemoveAll Then Exit
i = Contains(val)

Wend

Return True
End Method


Method Clear()
Items = Items[..0]
_Size = 0
End Method


Method ToArray:Object[]()
Return Items
End Method


Method ToList(List:TList Var)
For Local s:Object = EachIn items
List.AddLast(s)
Next
End Method


Method GetStepSize:Int()
Return StepSize
End Method

Method SetStepSize(val:Int)
If val < 1 Then val = 1 'don't allow negative values
StepSize = val
End Method


Method Sort()
Items[.._Size].Sort() 'don't sort entire array since sorting with a null object causes an unhandled memory exception
End Method


Method Free()
TObjectList.Destroy(Self)
End Method


' Method SaveToFile(filename:String) Abstract
Rem
Local fs:TStream = WriteFile(filename)
Local i:Int

For i=0 To _Size-1
WriteLine(fs, Items[i])
Next
CloseFile(fs)

End Method
EndRem

' Method LoadFromFile(filename:String) Abstract
Rem
Local fs:TStream = OpenFile(filename)
If Not fs Then Return
Clear()

While Not Eof(fs)
AddLast(ReadLine(fs))
Wend

CloseFile(fs)

End Method
EndRem

Function Destroy(sl:TObjectList)
sl.Clear()
sl = Null
GCCollect
End Function


Function Create:TObjectList(StepSize:Int = 10)
Local tempList:TObjectList = New TObjectList
tempList.StepSize = StepSize
Return tempList
End Function
End Type


'Rem test speed
SeedRnd MilliSecs()

Global numberOfIterations:Int = 9999 'increase this to see the performance difference


'Test a TObjectList
Print "~nTObjectList:~n"
Global sl:TObjectList = TObjectList.Create(1000) 'change this to a 1 and see the performance change


Local starttime:Int = MilliSecs()

For Local i:Int = 0 To numberOfIterations
sl.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
Next

sl.Sort()

Print MilliSecs()-Starttime + "ms"
GCCollect()
Print (GCMemAlloced()/1024)+"kb used"

sl.Free()
Print (GCMemAlloced()/1024)+"kb after free"


'test a TList
Print "~nTList:~n"
Global sl2:TList = New TList


starttime:Int = MilliSecs()

For Local i:Int = 0 To numberOfIterations
sl2.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
Next

sl2.Sort()


Print MilliSecs()-Starttime + "ms"
GCCollect()
Print (GCMemAlloced()/1024)+"kb used"
sl2 = Null
GCCollect()
Print (GCMemAlloced()/1024)+"kb after free"

'EndRem




Difference(Posted 1+ years ago)

 Looks good.How do I sort?


Perturbatio(Posted 1+ years ago)

 Well, with the StringList, you just use Sort()With the ObjectList, there is a sort method which relies on the compare methods of the objects.I've put a little workaround for the sort method (see <a href="../Community/posts88fd.html?topic=54852" target="_blank">http://www.blitzbasic.com/Community/posts.php?topic=54852[/url] ).


Difference(Posted 1+ years ago)

 Ok, thanks. :)


Perturbatio(Posted 1+ years ago)

 I've just realised that there's a major flaw in the sort method for the ObjectList.  It's currently sorting a slice which is a copy of the array, it probably won't sort the actual array like this.  Problem is sorting it as is causes an Unhandled Memory Exception [/i]

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal