Jump to content
  • Advertisement

Archived

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

Jeff D

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

This topic is 6010 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
Advertisement
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
What if, say CurrentItem->next->next == NULL ?
CurrentItem = CurrentItem->next->next->next->next->next will send you on a one-way trip to Segfaultland.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!