Jump to content
  • Advertisement
Sign in to follow this  
Algorithmic_Dream();

Why do we need to iterate data structures as they are already in RAM

This topic is 1553 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

First off, I hope I placed this in the appropriate section.  If so...

 

 

I've been programming for a while, but this may be a simple question to some (or many).

 

My Question: If a data structure already exist directly in RAM, then why do we need to spend the processing power to iterate in order to find the right data? (Side Note: pointers still exist in managed languages. They're just handled for you)

 

My theory is that in order to save memory, the pointer is the only actual data in RAM, so iterating expands the content within the memory address.

 

Basically if I have a list:

 

list(list name,value)

 

Index 0: list(mylist, 10);

Index 1: list(mylist, 15);

Index 2: list(mylist, 5);

 

All that would actually be in RAM is:

 

index 0, index1, index 2

 

Under my theory, in order to find and access any of it's contents, it has to do some form of parent to child linear search to expand all the data to find '5'? (The parent being the index's pointer to its physical address, and the data structure's value being the child pointer loaded into RAM as it searches):

 

Index 0: --> GET VALUE '10'; FALSE; Next Address!

Index 1: --> GET VALUE '15'; FALSE; Next Address!

Index 2: --> GET VALUE '5'; TRUE; RETURN Value!

 

This is all just my theory on it, so that's why I'm asking why iteration exists with data and data structures that are already in RAM, and why I can't just pull a value or any data attribute out of the data structure directly?

 

It would save so much processing power and development time if I never needed to (or rarely needed to) iterate within RAM.

 

Thanks for your time, and responses smile.png

Edited by Algorithmic_Dream();

Share this post


Link to post
Share on other sites
Advertisement

In data structures that don't offer random access, is it because the pointers that are public only point to the physical addresses of the index? And in order to find anything else like a value, it could only be accessed as a private pointer within that physical address by performing it as a second step?

 

If I displayed on screen an inventory system that didn't use a random access data structure, by clicking directly on a value to manipulate it, would the spatial information expedite the iteration process (or maybe even skip the need for iterating)?

Share this post


Link to post
Share on other sites

All data and code is located in RAM. To access the data and code you need an address. At some point all data and code is iterated through. In case of the code to execute the processor iterates with the program counter through the instructions.

Even data is accessed by an address. Using a pointer mostly means that you stored somewhere the address where the data resides. But even this pointer is stored in an address.

If you organize your data in an array you even iterate through memory but because you know that the data structures are layed out in an successive manner you can calculate the address of any structure in this array from the startaddress, the index and the size a single structure occupy.

Using linked lists or hash tables or whatever management structure is used only means to move the iteration process somewhere else.

Share this post


Link to post
Share on other sites

Thanks everybody who posted so far.

 

I guess I'm a little caught up on the idea that because I can click on an index/value directly in the UI, it shouldn't need to iterate 100 addresses to find it in memory. With that being said, hopefully I can use spatial data structures to access such data in a less iterative way.

 

@Chris_F: The topic wasn't about how linked lists worked in the typical implementation sense. I'm curious about why data structures need to iterate if everything is in RAM, and how to reduce their iteration cycle to (hopefully) a single point A - Point B iteration. I had the thought that if it's in RAM, all the data could be accessed in one simple want it-grab it function. An example of that is, if the mouse can click it, the data structure already knows where to go. If the player can see it on screen, the data structure should already know how it's organized and therefore, it shouldn't need to reiterate to reorganize.  I'm sure I'm on the right track to something there, but as different data structures will iterate differently, I guess I just have to find the right one for the job. That is in contrast to my thought that RAM could work like how someone would view an image or a movie. It would have a wide scope, and hold the data's big picture, while having no problem picking up on the smaller nuances and details.

 

Hopefully what I said made enough sense to you. I feel that what I said might need a bit more premeditated thought and analysis in order to be clear and concise for everybody. If it made sense to you, what are your thoughts. If it didn't, let me know.  I feel that I should take some time to truly learn how the RAM works, and then learn some algorithms for reducing the iteration/search time. Who knows, maybe i'll eventually get it to a 1 step iteration cycle.

Share this post


Link to post
Share on other sites

RAM has nothing to do with iteration, or vice-versa.

Iteration is simply one of the many algorithms which may or may not be required for a specific task in a program. For your tree-item example, the program would most likely use a map, which is a data structure optimised for quick searches: each tree item gets a unique identifier, and that identifier can be directly translated to the item's memory address, without any iteration involved (the algorithm is called "mapping"). Iteration is usually only required with data structures and algorithms for which no such direct relationship between the items of the data and their location in memory can be established...

 

The best example would be sorting a list of random numbers. Since they are random, the computer does not know at what position in the list each number is located before sorting, and while sorting, it has to put each item at a specific position in the output list. To do that, you first tell it to "iterate" over the whole list, and set aside the smallest number it finds during iteration, then move it into the lowest position of the output list. Then you tell it to iterate again over the list, to find the second-smallest item, and put it in the second-lowest position in the output list.. And so on until all of the items are sorted.

 

Computers cannot simply look at the list of random numbers as a whole, and arrange them in order from smallest to biggest like us humans can.

 

As for RAM vs. file-storage, the data can be stored anywhere... Files have file offsets, which are similar to memory addresses (file offsets are also called pointers sometimes). Iterating over data from a file is no different than iterating over memory, so you cannot say that iteration is specific to RAM data...

Edited by tonemgub

Share this post


Link to post
Share on other sites

RAM has nothing to do with iteration, or vice-versa.

Iteration is simply one of the many algorithms which may or may not be required for a specific task in a program. For your tree-item example, the program would most likely use a map, which is a data structure optimised for quick searches: each tree item gets a unique identifier, and that identifier can be directly translated to the item's memory address, without any iteration involved.

Even a map iterates through a tree. As I said before. Iteration is done somewhere but mostly hidden behind some function or encapsulated in a class/template or however you name it.

 

For my understanding iteration is the step by step walkthrough an organizational unit, map list queue whatever.

Share this post


Link to post
Share on other sites

 

RAM has nothing to do with iteration, or vice-versa.

Iteration is simply one of the many algorithms which may or may not be required for a specific task in a program. For your tree-item example, the program would most likely use a map, which is a data structure optimised for quick searches: each tree item gets a unique identifier, and that identifier can be directly translated to the item's memory address, without any iteration involved.

Even a map iterates through a tree. As I said before. Iteration is done somewhere but mostly hidden behind some function or encapsulated in a class/template or however you name it.

 

For my understanding iteration is the step by step walkthrough an organizational unit, map list queue whatever.

 

 

Iteration means repeating something, usually refers to executing the body of a loop repeatedly (because it is a loop). It doesn't mean executing an algorithm. And a map data structure doesn't need to be implemented as a tree.

Share this post


Link to post
Share on other sites


Iteration means repeating something, usually refers to executing the body of a loop repeatedly (because it is a loop). It doesn't mean executing an algorithm. And a map data structure doesn't need to be implemented as a tree.

A loop is an algorithm too. Not very complex but it describes how something has to be done.

 

I dont said that the map is implemented in a tree. But even the traversal of a tree is done in steps that are done the same way in each step, so it is an iteration anyways you use a loop inside or recursive call to the traversal function.

Maps maybe implemented as hashtables. But even there you only get a good guess where to start the search, that afterwards is iterated through a collection of data to find the right one.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!