Skip to main content
gamedev.net
🔒 Locked

Are pointers more efficient?

Started by dmatter Apr 15, 2004 at 2:59 PM 8 replies 700+ views
Original Post
dmatter
dmatter
I''m writing some code that needs to be as fast as possible for its environment in C. I''ve been trying to compromise between speed and memory. At the moment I''m using several dynamic arrays of pointers to structures which store all sorts of information. I have several requirements that I''ve guidelined myself, the system must be dynamic (resizable), fast, and comparitively memory unintensive. The whole reason I chose the current method was because the table of pointers itself is smaller than an array of structures and it doesn''t require a huge contiguous chunk of memory i.e. it can be split up in smaller sized chuncks pointed to by each pointer in the table. However, I was also considering using linked lists with two pointers, one to the next element and one to the previous, its main disadvantage (in my mind) is its spead because I cannot simply call up and index, I have to loop through the list until I find the entry I want. Basically I need to know which is more efficient (following the criteria above), or is there a better option all together? Any help would be greatly appreciated.
SpaceDude
SpaceDude
If you are using dynamic arrays... Then you need to know in advance how many items of data you will have in them... Which in most cases you don''t.

So the main advantage of linked lists is that you can add new items, delete items, etc... very quickly and effeciently without having to shift data around in memory...

In most of my applications, i never need to access a particular index directly. So the fact that i can''t do that is not a problem at all. And i do tend to use linked lists a lot, it is rare for me to use dynamic arrays.

I would suggest you use arrays only when you know exactly how much data you need to store in advance otherwise use linked lists.
krez
krez
std::vector is a dynamic array; you can get items by index, and it resizes by itself when necessary. if you know ahead of time the number of elements you want, you can have it reserve that much memory so it doesn''t have to resize (which copies all the elements already in there).

you can use a vector of pointers, so it only has to copy 4 bytes per element instead of the entire structs.
--- krez ([email="krez_AT_optonline_DOT_net"]krez_AT_optonline_DOT_net[/email])
bytecoder
bytecoder
quote:

If you are using dynamic arrays... Then you need to know in advance how many items of data you will have in them... Which in most cases you don''t.

So the main advantage of linked lists is that you can add new items, delete items, etc... very quickly and effeciently without having to shift data around in memory...

In most of my applications, i never need to access a particular index directly. So the fact that i can''t do that is not a problem at all. And i do tend to use linked lists a lot, it is rare for me to use dynamic arrays.

I would suggest you use arrays only when you know exactly how much data you need to store in advance otherwise use linked lists.

You''re half right. Dynamic arrays should be used if you need to access a random position in the structure very often. On the other hand, if you add elements to it often you should use a linked list.
Colin Jeanne
Colin Jeanne
quote:
Original post by krez
[C++ stuff]

Except that dmatter is using C.

Depending on what properties your data has you might be able to store it, sorted, in a tree. That way the structure can grow and, under good conditions, you should be able to find an element fast than you would with a linked list.

Thanks Salsa!Colin Jeanne | Invader''s Realm
"I forgot I had the Scroll Lock key until a few weeks ago when some asshole program used it. It even used it right" - Conner McCloud
bobstevens
bobstevens
quote:
Original post by krez
std::vector is a dynamic array; you can get items by index, and it resizes by itself when necessary. if you know ahead of time the number of elements you want, you can have it reserve that much memory so it doesn''t have to resize (which copies all the elements already in there).


Another neat trick is that if you know ahead of time the number of elements you want, you can use a normal array!

Zahlman
Zahlman
You could always go and implement something like std::vector in C.

Maybe you don''t need all the extra functions, and maybe you don''t require completely contiguous use of memory. But you can gain plenty from just using the idea of exponential growth of the container size. Going from a structure like

N nodes -> N nodes -> N nodes -> N nodes

to

N nodes -> N*k nodes -> N*k^2 nodes -> N*k^3 nodes

still provides O(n) space overhead (and the advantage that you can tune that amount as you like, to trade off against speed), and gives you an O(lg n) subscript operator, and probably faster iteration overall. Of course, random insertion will still be O(n). You could ameliorate that by implementing some "balancing" scheme so that each "buffer" is not completely filled, I think. There will be occasional O(n) cases that way, but I think the whole thing will amortize out to O(lg n).
flangazor
flangazor
Sounds like a job for a tree of sorts. This book will be of interest for you.
dmatter
dmatter
Thanks, I''ve now adapted my code for linked lists and I''ve changed some other bits around so there''s no requirement to call up a value by index - Now I''m sure there is an increase in speed

I was wondering whats the best way to free a linked list, given the first element?
Currently I think this works:

for (pointer *ptr = data->first, *nextptr; ptr; ptr = nextptr)
{
nextptr = ptr->next
free (ptr);
}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.