Archived

This topic is now archived and is closed to further replies.

Is this a faster way to go through a linked list?

This topic is 5793 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Lets say you have a struct like this:
      
struct Node
{

   ItemClass Item;
   Node* next;

};
  
Now lets say you have 100000 Items. I know 100000 items sounds like a lot im using this as an example. Now you have to go through it like this:
        
while(LinkedItems->next)
{

   CurrentItem = CurrentItem->next

}
  
Now to my knowledge that could get slow if you are going through the list a lot. But would this make it faster? add a long ID. Now lets say I wanted to goto item 4500. Would this be faster??
        
long ID;
int IDRemains
int i;

ID = 4500;
IDRemains = ID % 5;
ID = ID / 5;

for(i = 0; i < ID; i++)
{

   CurrentItem = CurrentItem->next->next->next->next->next;

}

if(IDRemains != 0)
{

   For(i = 0; i < IDRemains; i++)
   {

      CurrentItem = CurrentItem->next;

   }

}
  
Kinda after posting and coding I believe my second way is slower because it uses more code. But GameDev has helped me a lot so far so maybe Im right the first time. Thx. Jeff D Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton Edited by - Jeff D on January 31, 2002 8:36:00 AM Edited by - Jeff D on January 31, 2002 8:37:19 AM

Share this post


Link to post
Share on other sites
I dont think it makes much off a difference. U are trying to skip 5 items insted off 1 right? But CurrentItem->next->next->next->next->next; still has to go through all 5 items because it needs the address of the next item. I''d say it''s about the same in performance.

Share this post


Link to post
Share on other sites

If you need O(1) or O(log n) access time to arbitrary element
in a container, then std::list isn''t the container you want to use.

What you need is a container that allows O(1) or O(log n) access time. e.g. vector, deque, map or hash table (which is not in the current Standard C++ but is in many STL library ports).

You cannot make an apple out of an orange, so don''t try to "bend" std::list into giving you "faster" access. You can''t.


Premature optimizations can only slow down your project even more.

Share this post


Link to post
Share on other sites
quote:
Original post by DaJoostMan
I dont think it makes much off a difference. U are trying to skip 5 items insted off 1 right? But CurrentItem->next->next->next->next->next; still has to go through all 5 items because it needs the address of the next item. I''d say it''s about the same in performance.



It is faster skip five items at a time like that, because it is like unrolling the loop. The more you unroll it the faster it goes. There is overhead for each iteration through the loop. If you reduce this overhead in this way, this will speed things up.

---
Make it work.
Make it fast.

"Commmmpuuuuterrrr.." --Scotty Star Trek IV:The Voyage Home

Share this post


Link to post
Share on other sites
If you know how big your list will be before you start, use something like this:

class Array
{
int * root;
int length;

void set_size(int size){if (root) delete root; root = new int[size]; length = size;};
int access_element(int x) {if (0};


That''s the bare minimum of course, but it''s a good system to use, because you can resize it whenever you like and access any element with O(1) speed.

If you need the dynamic size (don''t know from the start), but you don''t mind reallocating memory very often:

void Array::append_value(int val)
{
int * temp = new int[length + 1];

for(int i = 0; i < length; i++)
temp = root[i];
temp[length = val];
root = temp;
length++;
}


but sorting and inserting become nightmares, searching is slow, and removal of select is also slow.

Share this post


Link to post
Share on other sites
Well you see if I had all the items with an ID It should never exceed the Linked List. Ill just have a variable that holds the number of items if it exceeds the number than something went wrong in my code. The way its working right now The player class has an inventory. Now the weapon equiped is actually a pointer to the weapon LinkedList. When you load the character from a file it gives the weapon''s ID num. When the program searches the linked List for the ID num and finds it, it then sets the Player''s Weapon pointer to that weapon. So if somehow the ID num is higher than the amount of items in the game then there is something wrong with my code. But all I have to do is this:

if(CurrentItem->next->next->next->next->next != NULL)
CurrentItem = CurrentItem->next->next->next->next->next;

But I''m still somewhat a newbie in this stuff.

Symphonic hmm interesting perhaps I will try to play around with that. Thx man.

Jeff D

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Jeff D
Well you see if I had all the items with an ID It should never exceed the Linked List. Ill just have a variable that holds the number of items if it exceeds the number than something went wrong in my code. The way its working right now The player class has an inventory. Now the weapon equiped is actually a pointer to the weapon LinkedList. When you load the character from a file it gives the weapon''s ID num. When the program searches the linked List for the ID num and finds it, it then sets the Player''s Weapon pointer to that weapon. So if somehow the ID num is higher than the amount of items in the game then there is something wrong with my code. But all I have to do is this:

if(CurrentItem->next->next->next->next->next != NULL)
CurrentItem = CurrentItem->next->next->next->next->next;

But I''m still somewhat a newbie in this stuff.

Symphonic hmm interesting perhaps I will try to play around with that. Thx man.

Jeff D



Man, this problem is positively screaming to be a hash table.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I have an even better suggestion. Never iterate through 100000 objects at once. If you need them to all be updated, update them in segments over time.

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
What if, say CurrentItem->next->next == NULL ?
CurrentItem = CurrentItem->next->next->next->next->next will send you on a one-way trip to Segfaultland.


Haha, Segfaultland. Very original .

I would suggest using a hash table.

Share this post


Link to post
Share on other sites
I looked up things about hash tables they seem quite advanced for me. heheh Im still quite new to C++. Well I was sitting down and thought. Im gonna make the weapons, armor, items, spells. I know the amount so why not just create them with arrays. Is this like a bad habit to get into with programming

Hash tables seemed confusing, maybe I''m just tired right now.

Jeff D




Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Share this post


Link to post
Share on other sites
It''s not a bad idea, but take the time to look up the basics on making a template class. Then use the code I gave you, because it will save you some trouble.

If you REALLY don''t know up from down yet, I can give you a complete Array template class that I have written.

George D. Filiotis
Are you in support of the ban of Dihydrogen Monoxide? You should be!

Share this post


Link to post
Share on other sites
Hey I take all the code I can get if its to big to put on here send to domon_m@hotmail.com. Thx

About template classes I got Teach yourself c++ in 24 hours ill take a look at it.

Jeff D




Suffered seven plagues, but refused to let the slaves go free. ~ Ross Atherton

Share this post


Link to post
Share on other sites
You could also use the builting vector class. Of course there is no hashing, but it can be treated just like an array. That way you have 2 options: you could make a vector for each category, ie weapons, armour, etc... or you could make a root object like CharacterStuff, derive the character items and spells from that and save them all in one vector.

---
Make it work.
Make it fast.

"Commmmpuuuuterrrr.." --Scotty Star Trek IV:The Voyage Home

Share this post


Link to post
Share on other sites