Há várias respostas aqui que fala sobre localidade de referência, mas não explicam o que é.
Onde ela é aplicada?
E por que ela é tão importante para estruturas de dados e algoritmos?
Há várias respostas aqui que fala sobre localidade de referência, mas não explicam o que é.
Onde ela é aplicada?
E por que ela é tão importante para estruturas de dados e algoritmos?
Localidade de referência é um conceito vindo de arquitetura de computadores, como a memória do computador é finita existe alguns algoritmos que visam deixar o acesso a memória mais rápidos.A ideia principal é que existe memórias que são mais rápidas que outras, por exemplo, é muito mais rápido acessar um conteúdo na memória RAM do que no disco.
Esse conceito se estende também para outros softwares comercias, imagine que você tem uma parte do seus dados que é muito acessada, e outras que não são tanto, e que todos eles estão no banco de dados, toda vez que você ler ou escreve esse dado, você precisará ler e escrever no banco de dados, isso envolverá operações de I/O e são demoradas. O ideal seria que os dados que são mais acessados estivessem na memória RAM do software, dai nasce o conceito de cache.
Você pode ter vários níveis de cache, seja o cache em RAM que será o mais rápido, ou um cache em um banco de dados apropriado para isso, como é o caso do REDIS.
Quando falamos em algoritmos ou estrutura de dados o mesmo conceito é aplicado, por exemplo, imagine que você precisa calcular a sequencia de Fibronacci de um certo número, e usa um algoritmo recursivo para fazer isso, você pode usar duas abordagens, a primeira é que você sempre irá calcular o número e a segunda é que você guardará em cache os 200 últimos números calculados.
Na primeira opção você gasta menos memória porém, gasta mais processamento, já na segunda você gasta mais memória, em contrapartida com o decorrer do tempo o seu software conseguirá calcular o número mais rápido.