cody said:
You know that inserting or removing items it an ArrayList causes all
succeeding items to shift in memory?
Yes, I know, do you know that lookup time for an linked list is considerably
higher than an ArrayList? However, how often do you really insert or remove?
And how often is the whole thing big enough that it matters. When you
combine the issue with the memory problems below...its not nessecerily as
big a problem as you seem to think. In an array list, the cost of inserting,
adding, and removing incurs that lookup cost as well(by storing the tail or
adding to the head you can mitigate the cost of adding).
Let us consider(there may be off by one errors here, I don't have time to
verify the exactness right now):
assuming the arraylist is big enough to hold the items(by default it should
be at 64 at this point, I think)
an ArrayListof 40 objects and a linked list of the same forty.
If I want to insert an object at index 20 I would:
for ArrayList:
base + 20*refSize = index;
copy 20*refSize bytes to index+refSize;
copy refSize bytes to index;
for LinkedList
compare the link address to to null
if not null, then load node at link address and
repeat 19 times
copy thisNode next address to lastNode next address
copy lastNode next address to thisNode address
Neither one is really that much more efficent than the other. Some tricks
could be performed to *try* to speed up node lookups, but not without the
cost of complexity. Most of the really good tricks need to understand the
usage, which a general class can't match. Inserting in linked lists is much
more valuable when you are directly acessing the list than it is when you
try to use IList to work with the list. For small amounts of data, there
should be virtually no difference in insertion speed, for large amounts the
memory issues with LinkedLists I illustrate below is potentially a problem.
Also in a critical real time it cannot be that your ArrayList if it
resizes
due to an addition of an item grows and copies itself in memory,
This point is moot, as you really shouldn't be using .NET in critical
realtime situations anyway, atleast in its current form. The garbage
collector is unpredictable and may freeze threads for unpredictable amounts
of time while it moves an unpredictable amount of memory around...how
exactly does that make an array resize something to worry about?
also if you have a total of 100 mb ram and your ArrayList is 30mb in size,
resizing will cause the ArrayList to grow to the double size and now you
have an
30mb ArrayList plus a 60mb ArrayList in ram simultanously.
If you are using a large ArrayList, you should pre-define the size instead
of letting it grow. Anyway, lets do some math here, a linked list of
integers, consider it LinkedList<int>, using 30 meg of integer data as the
store amount:
integers: 7864320 integers * 4bytes an integer = 31,457,280 bytes or 30 megs
node references: 7864320 node references * 4bytes a reference = 31,457,280
bytes or 30 megs
size of the combined nodes: 62,914,560 bytes or 60 megs
node object headers(the .NET runtime headers, pretty sure this is 8 bytes):
7864320 * 8 = 62,914,560 bytes or 60 megs
grand total: 125,829,120 bytes or 120 meg for 30meg of data storage. this
would be larger still on 64 bit hardware and\or you use a doubly linked
list.
This is higher than the combined 90 meg of array data in an
List<int>(ArrayList would exhibit worse problems because it would box the
ints, forming references to them and extra object headers, a non-generics
enabled, object based linked list would exhibit the same issue. In effect
you end up with an extra 12 bytes per integer, even ontop of the costs of
LinkedList as it stands). 30 of that 90 will be collected in fairly short
order, but the 120 of the linked list will stay until the list is done with.
The end result is that storing an object in a LinkedList will always take up
atleast an extra 12 bytes ontop of the memory cost of the object vs storing
the same object in an array or an ArrayList. Trading off that extra space
for trees or skiplists...something that will reduce lookup time or add
hiearchy is one thing, but to achieve the singular effect of speading up
insertions in some cases is not generally something I'm interested in. I
know that linked lists are sometimes valuable...but I really don't believe
that they are so important that a generic implementation needs to exist in
the BCL. I have the serious concern that by adding LinkedLists to .NET,
people are going to start using them on this concept of "inserts are so much
faster" without considering the, IMHO substantial, downfalls of a
LinkedList.
--
cody
[Freeware, Games and Humor]
www.deutronium.de.vu ||
www.deutronium.tk
)...but I think a