Linked List Vs Array
BlitzMax Forums/BlitzMax Programming/Linked List Vs Array
| ||
| Hi, Can anybody explain why I would use a linked list over an array to store my game data? Before I discovered blitz3d I used arras for everything. Its seems b3d didn't have very good arrays so i switched to links lists, they were nice, but i'm wondering if i should be switching back to arrays now in blitx max. Are arrays really slow to resize? Is it easier to delete things out of the middle or a linked list? What are your opinions? |
| ||
| For linked lists, it would most likely be faster if you're constantly adding and removing stuff from the list. Like particles. |
| ||
| Are arrays really slow to resize? Is it easier to delete things out of the middle or a linked list? Yes and Yes. Resizing or compressing an Array (removing "empty" elements) takes linear time, Link lists are compressed and resized automatically, in constant time. Deleting would be the same speed, if you can live with "Null" elements in your array. If you have to compress the array afterwards, a list is your best bet.Arrays are good for random access and good for sequential access (both are in constant time). Linked lists on the other hand are constant for sequential, but linear for random access. The choice of which datastructure to use, depends entirely on the problem you're trying to solve. |
| ||
| perhaps you should create a program to test. linked list vs array (round 1)
Local food:String[] = ["Milk","Raisins","Hamburger","Spam"]
Local foodlist:TList = CreateList()
foodlist.addlast("Milk")
foodlist.addlast("Raisins")
foodlist.addlast("Hamburger")
foodlist.addlast("Spam")
now# = MilliSecs()
For loop = 10 To 100000
For x = 0 To Len(food)-1
'Print food[x]
Next
Next
elapsed# = MilliSecs()-now
Print "Array Elapsed:"+elapsed
now# = MilliSecs()
For loop = 10 To 100000
For n:String = EachIn foodlist
'Print n
Next
Next
elapsed# = MilliSecs()-now
Print "List Elapsed:"+elapsed
|
| ||
| To be fair, you should use foreach in both examples. Not that it's a very scientific benchmark or anything. :o> |
| ||
| Linked lists and arrays are not the only methods of storing data that are useful (although they are easy because they are already implemented). If you want to index by something like a string, you could use a hash table. Lets say you have a list of players, and you want to pull an object up from each player's name. You take the string, run a hash function to convert that into a number that falls within the range of an array, and store it in that element. Or, you can have a linked list faster by breaking it into subelements. For example, if you were storing words in a dictionary, you could have an array of linked lists with 26 entries for a-z. That way when you manipulate a list, you are manipulating a much smaller subset. |
| ||
| I use lists only for storing the highscores (essentially because they provide the "sort" method which I didn't bother to code), but in general I strongly prefer arrays (because of my background) |
| ||
| You can sort arrays, just like lists. |
| ||
| enhanced (yet still un-scientific) test program: From my calculations, Arrays are much faster to iterate over. avg: Array = 1ms Lists = 25ms
Local food:String[] = ["Milk","Raisins","Hamburger","Spam"]
Local now:Double , elapsed:Double
Local foodlist:TList = CreateList()
foodlist.addlast("Milk")
foodlist.addlast("Raisins")
foodlist.addlast("Hamburger")
foodlist.addlast("Spam")
For tests = 1 To 10
' ARRAY TEST
now = MilliSecs()
For loop = 10 To 100000
For n:String = EachIn food
'Print n
Next
Next
elapsed = MilliSecs()-now
Print "Array Elapsed:"+elapsed
' LIST TEST
now = MilliSecs()
For loop = 10 To 100000
For n:String = EachIn foodlist
'Print n
Next
Next
elapsed = MilliSecs()-now
Print "List Elapsed:"+elapsed
FlushMem
Next
|
| ||
| We should expand this test to include adding and removing items to the list/array. Also sorting the elements is probably a common task. What are the cleanest ways to do this? I was reading yesterday about adding a compare method to a type to allow you to define how your list can be sorted. Can this be done with an Array as well. |
| ||
| > You can sort arrays, just like lists. oh... also with array of objects? Does it still use the compare method? Then lists suck totally lol |
| ||
| Why shouldn't it use the compare method? This way you define what makes one of your own types larger / smaller than another. and it only sorts if you say it to do so. Hakea: Yes you can sort arrays, if you implement a function to do so. This way it would be faster than the list would normally be in sorting at all (quicksort or any other n log n sort algorithm) as the list can't use "indexed" sort algorithms otherwise no as array is no type in BM and so can't have the same functionality as a list. but you can't slice a list on the other side, so ... perhaps this is why TList has the "fromarray" and "toarray" methodes? ;) |
| ||
| perhaps Mark could clarify where Lists make sense and where Arrays would better suit the needs of the programmer |
| ||
| Thats more of personal opinion or object structure used so a clarification would be useless. You will see what you need when you actually program something and do some ressearch on the possible approaches of solving the problems efficient, if you haven't studied computer science and were taught whole stuff. Normally you wouldn't even have a TList structure in a language btw but could it create on your own. The main reason BM has it is that it is used for internal stuff as well (I assume procedural programming and keep track of OO references for example). One of the main uses of the TList is the object handling (-> global list:TList in own types to keep track of existing objects) or things like message queues in network programming / gui programming. If you need to capability to access a specific object with only 1 call then array is the way to go, as it works with indices. |
| ||
| Can anybody explain why I would use a linked list over an array to store my game data? An array has a certain length or size. If you read or write outside of this size you get an error unless you first increase the size of the array. A List on the other hand links each object to the next and previous object. When adding an object to a list we have to add it first,last,before or after some object in that list. Let's say you are creating ememies. To add each enemy to a list and then draw each enemy in that list is easier than to first create an array and increase it everytime we need another enemy. Lists makes it easier (for the programmer) to work with adding and removing objects over time. Arrays are easier and faster when you need specific objects. |
| ||
| hmm.. ok, so it sounds like Lists are best used when I have a dynamic number of objects. They may not be faster, but seem to be a cleaner way to add, remove and sort dynamic data. Arrays are better (cleaner) when I know how much data i need and it has some implicit order. A grid map for example. |
| ||
| they are normally faster with a dynamic number of objects if you don't want to waste memory with overallicating its size as resizing an array can be a quite cpu time intense thing (create a the array of the new size, copying the old content, deallocating the old array). And yep, your examples are quite good for some "standard uses" of this 2 "structures" |
| ||
| Yes, to kind of build on what Dreamora is saying: Even if iterating through a list is slower than an array, it can be faster - because in the list, you are only iterating through entries that exist, were in the array, you iterate through the entire potential set. |
| ||
| Also, manually iterating over the list seemed to be faster on my test run. I'm thinking that some of the speed loss may be due to the downcasting required. The array is just iterating over elements known as a strings, whereas the list has to see if the object is a string or not. |
| ||
Local food:String[] = ["Milk","Raisins","Hamburger","Spam"]
Local now:Double , elapsed:Double
Local foodlist:TList = CreateList()
foodlist.addlast("Milk")
foodlist.addlast("Raisins")
foodlist.addlast("Hamburger")
foodlist.addlast("Spam")
For tests = 1 To 10
' ARRAY TEST
now = MilliSecs()
For loop = 10 To 1000000
For n:String = EachIn food
'Print n
Next
Next
elapsed = MilliSecs()-now
Print "Array Elapsed:"+elapsed
' LIST TEST
now = MilliSecs()
For loop = 10 To 1000000
For n:String = EachIn foodlist
'Print n
Next
FlushMem() ' <-------- do not forget, and array is a little faster
Next
elapsed = MilliSecs()-now
Print "List Elapsed:"+elapsed
FlushMem
Next |
| ||
I'm not sure there's a significant difference, unless you have a huge number of objects.objects=1000 Type TThing Field a EndType Local array:TThing[objects] Local list:TList=New TList For n=1 To objects thing:TThing=New TThing array[n-1]=thing list.addlast thing Next now = MilliSecs() For thing=EachIn array Next elapsed = MilliSecs()-now Print "Array Elapsed:"+elapsed now = MilliSecs() For thing=EachIn list Next elapsed = MilliSecs()-now Print "List Elapsed:"+elapsed |
| ||
| Has it *really* been a year already? |
| ||
| ha ha. yeah. It's a little surreal reading your own post from a year ago. I don't even remember writing it. |
| ||
| The array is just iterating over elements known as a strings, whereas the list has to see if the object is a string or not. Good point. We need generics. |
| ||
| I recently figured out that I was getting major slowdowns because of my use of TLists. This was not an insignificant delay, it was something like a 2 msecs loss for each shadow I rendered, just because I had to go through a long list of objects. You must avoid TLists! |
| ||
| You must avoid TLists! hahahahaha Or only put in the Tlist the things you are going to want. Then you wouldnt have to search the whole list for the thing you wanted, you would know it was the next one ;) You could for example have another list for just shadows which contains the tlink to your big list. (PS, I know Im not telling you anything you dont already know and do, I just didnt want ppl to never use Tlists simply because you have just said so) (There are some very easyerly influenced ppl out there ;) |
| ||
| I still maintain that hash-tables are almost always a better choice than a list. The only time this isn't true is if you are tight on memory and can't afford the overhead of having a properly sized table(i.e. larger than you initially need, to avoid re-sizing slowdowns). |
| ||
| I already have a list for each type. It's just the raw speed of going through the lists is too slow. Actually, I see a few people have pointed out that lists are slow to find things in. I don't ever use Remove or Find with a list. My engine is smart enough to do without those. However, the speed of lists is still hurting performance. |
| ||
| The difference will depend upon how much processing is performed 'per item'. Arrays will be mmarginally faster - and more cache friendly - but if you're doing a decent amount of work the difference will be minimal. |
| ||
| I still maintain that hash-tables are almost always a better choice than a list. That depends entirely on the efficiency of the hashing algorithm. |
| ||
| @Leadwerks If you want to speed up you TList access dont use foreach manually walk the list. Foreach is nice but MAX implmentation of enumerators is not real fast, way too much overhead in function calls. So if you have to walk a list many times best optimization you can do is inline it using the raw links. Granted if the underlying implmentation changes your code will break, so you might consider implmenting your own version. SuperStrict Type TItem Field Name : String Function Create:TItem(I:Int) Local r : TItem = New TItem r.Name = "Item "+I Return r End Function End Type Const ITEMCOUNT:Int = 1000 Global ItemList : TList = New TList For Local i:Int = 0 Until ITEMCOUNT ItemList.Addlast(TItem.Create(i)) Next Local starttime:Int= MilliSecs() Local c:Int = 0 For Local t:Int = 0 Until 1000 For Local item :TItem= EachIn ItemList c:+1 Next Next Print (MilliSecs()-starttime)+"ms" starttime:Int= MilliSecs() c:Int = 0 For Local t:Int = 0 Until 1000 Local link:TLink= ItemList.FirstLink() While link Local item:TItem=TItem(link._value) If link._succ._value<>link._succ link=link._succ Else link=Null End If C:+1 Wend Next Print (MilliSecs()-starttime)+"ms" 35ms 12ms [/code] Results from my machine for this simple little list thats close to 300% faster naviagation of the list. Hope this helps Doug Stastny |
| ||
| I've found similar results as Budman with manually iterating through the loop. 'Twas quite surprised. |
| ||
| Thanks Budman, bookmarking. |
| ||
| Thank you for the tips. Can't you replace this: If link._succ._value<>link._succ link=link._succ Else link=Null End If with this?: link=link.NextLink() |
| ||
| @Leadwerks You can but... try the timing, by expanding the code inline you save the time for setting the function call for that simple piece of code. In C/C++ you can mark little functions/methods like NextLink as Inline and compiler auto exapnds them. For Max you need to hand code those optimizations... old school :) Doug Stastny |
| ||
| I wish we had Inline and Macros in BMax. |
| ||
| . |
| ||
| would be nice to have inline Assembler in BlitzMax :-) |
   |