What is a reference location?

Question

What is a reference location?

Asked 5 years, 6 months ago

Viewed 641 times

8

There are several answers here that talk about locality of reference, but do not explain what is.

Where it is applied?

And why it’s so important for data structures and algorithms?

In the sense of temporal/spatial location? How in that reply?

– Jefferson Quesado

2019/01/04 at 12:58
@Jeffersonquesado left open, can talk about it, I almost asked about the guys, but I thought I could make it wide

– Maniero

2019/01/04 at 13:16
This answer also cites reference location.

– Piovezan

2019/01/04 at 14:26

1 answer

Browser other questions tagged algorithm terminology performance computer-science

You are not signed in. Login or sign up in order to post.

by Ramires Nascimento • **311** points · Answer 1 · 2019-01-04T12:59:25+00:00

Reference locality is a concept coming from computer architecture, as computer memory is finite there are some algorithms that aim to make access to memory faster. The main idea is that there are memories that are faster than others, for example, it is much faster to access content in RAM than on disk.

This concept extends also to other commercial software, imagine that you have a part of your data that is very accessed, and others that are not so much, and that they are all in the database, every time you read or write this data, you will need to read and write in the database, this will involve I/O operations and are time consuming. The ideal would be that the data that are most accessed would be in the software’s RAM, hence the concept of cache.

You can have multiple levels of cache, either the RAM cache that will be the fastest, or a cache in a suitable database for this, as is the case with REDIS.

When we talk about algorithms or data structures the same concept is applied, for example, imagine that you need to calculate the Fibronacci sequence of a certain number, and use a recursive algorithm to do this, you can use two approaches, the first is that you will always calculate the number and the second is that you will cache the last 200 numbers calculated.

In the first option you spend less memory but, spend more processing, in the second you spend more memory, in contrast with the course of time your software will be able to calculate the number faster.