Tabela de pesquisa - Lookup table

Na ciência da computação , uma tabela de pesquisa é uma matriz que substitui a computação em tempo de execução por uma operação de indexação de matriz mais simples. A economia no tempo de processamento pode ser significativa, porque recuperar um valor da memória geralmente é mais rápido do que realizar um cálculo "caro" ou uma operação de entrada / saída . As tabelas podem ser pré - calculadas e armazenadas em armazenamento estático de programa, calculadas (ou "pré-buscadas" ) como parte da fase de inicialização de um programa ( memoização ) ou mesmo armazenadas em hardware em plataformas específicas de aplicativos. As tabelas de pesquisa também são amplamente utilizadas para validar os valores de entrada comparando-os com uma lista de itens válidos (ou inválidos) em uma matriz e, em algumas linguagens de programação, podem incluir funções de ponteiro (ou deslocamentos para rótulos) para processar a entrada correspondente. FPGAs também fazem uso extensivo de tabelas de pesquisa reconfiguráveis ​​e implementadas por hardware para fornecer funcionalidade de hardware programável.

História

Parte de uma tabela do século 20 de logaritmos comuns no livro de referência Abramowitz e Stegun .

Antes do advento dos computadores, as tabelas de consulta de valores eram usadas para acelerar cálculos manuais de funções complexas, como trigonometria , logaritmos e funções estatísticas de densidade.

Na Índia antiga (499 DC), Aryabhata criou uma das primeiras tabelas de seno , que ele codificou em um sistema numérico baseado em letras sânscritas. Em 493 DC, Victorius de Aquitaine escreveu uma tabuada de 98 colunas que deu (em algarismos romanos ) o produto de cada número de 2 a 50 vezes e as linhas eram "uma lista de números começando com mil, descendo de centenas para um cem, depois diminuindo de dezenas para dez, depois de um para um e, em seguida, as frações para 1/144 "As crianças da escola moderna são frequentemente ensinadas a memorizar" tabuadas "para evitar cálculos dos números mais comumente usados ​​(até 9 x 9 ou 12 x 12).

No início da história dos computadores, as operações de entrada / saída eram particularmente lentas - mesmo em comparação com as velocidades do processador da época. Fazia sentido reduzir as caras operações de leitura por uma forma de cache manual , criando tabelas de pesquisa estáticas (incorporadas no programa) ou matrizes pré-buscadas dinâmicas para conter apenas os itens de dados de ocorrência mais comum. Apesar da introdução do armazenamento em cache em todo o sistema que agora automatiza esse processo, as tabelas de pesquisa no nível do aplicativo ainda podem melhorar o desempenho de itens de dados que raramente, ou nunca, mudam.

As tabelas de consulta foram uma das primeiras funcionalidades implementadas em planilhas de computador , com a versão inicial do VisiCalc (1979) incluindo uma LOOKUP função entre suas 20 funções originais. Isso foi seguido por planilhas subsequentes, como o Microsoft Excel , e complementadas por funções especializadas VLOOKUP e HLOOKUP para simplificar a pesquisa em uma tabela vertical ou horizontal. No Microsoft Excel, a XLOOKUP função foi implementada a partir de 28 de agosto de 2019.

Exemplos

Pesquisa simples em uma matriz, uma matriz associativa ou uma lista vinculada (lista não classificada)

Isso é conhecido como pesquisa linear ou pesquisa de força bruta , em que cada elemento é verificado quanto à igualdade, por sua vez, e o valor associado, se houver, usado como resultado da pesquisa. Geralmente, esse é o método de pesquisa mais lento, a menos que valores de ocorrência frequente ocorram no início da lista. Para uma matriz unidimensional ou lista vinculada , a pesquisa geralmente é para determinar se há ou não uma correspondência com um valor de dados de 'entrada'.

Pesquisa binária em uma matriz ou uma matriz associativa (lista classificada)

Um exemplo de um " algoritmo de divisão e conquista ", a pesquisa binária envolve cada elemento sendo encontrado determinando em qual metade da tabela uma correspondência pode ser encontrada e repetindo até o sucesso ou o fracasso. Isso só é possível se a lista estiver classificada, mas oferece um bom desempenho mesmo com listas longas.

Função hash trivial

Para uma pesquisa de função hash trivial , o valor de dados brutos não assinados é usado diretamente como um índice para uma tabela unidimensional para extrair um resultado. Para intervalos pequenos, esta pode ser uma das pesquisas mais rápidas, mesmo excedendo a velocidade de pesquisa binária com ramificações zero e executando em tempo constante .

Contando bits em uma série de bytes

Um problema discreto que é caro de resolver em muitos computadores é o de contar o número de bits que são definidos como 1 em um número (binário), às vezes chamado de função de população . Por exemplo, o número decimal "37" é "00100101" em binário, portanto, contém três bits definidos como "1" binário.

Um exemplo simples de código C , projetado para contar os 1 bits em um int , pode ter a seguinte aparência: 

int count_ones(unsigned int x)
{
    int result = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        result++;
    }
    return result;
}

Esse algoritmo aparentemente simples pode levar potencialmente centenas de ciclos, mesmo em uma arquitetura moderna, porque faz muitas ramificações no loop - e a ramificação é lenta. Isso pode ser melhorado usando o desenrolamento de loop e algumas outras otimizações do compilador. No entanto, existe uma solução algorítmica simples e muito mais rápida - usando uma pesquisa de tabela de função hash trivial .

Simplesmente construa uma tabela estática, bits_set , com 256 entradas, dando o número de um bits definido em cada valor de byte possível (por exemplo, 0x00 = 0, 0x01 = 1, 0x02 = 1 e assim por diante). Em seguida, use esta tabela para encontrar o número de unidades em cada byte do inteiro usando uma pesquisa de função hash trivial em cada byte por vez e some-os. Isso não requer ramificações e apenas quatro acessos à memória indexada, consideravelmente mais rápidos do que o código anterior. 

/* Pseudocode of the lookup table 'uint32_t bits_set[256]' */
/*                    0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... */
int bits_set[256] = {    0,    1,    1,    2,     1,     2, // 200+ more entries

/* (this code assumes that 'int' is an unsigned 32-bits wide integer) */
int count_ones(unsigned int x)
{
    return bits_set[ x       & 255]
        + bits_set[(x >>  8) & 255]
        + bits_set[(x >> 16) & 255]
        + bits_set[(x >> 24) & 255];
}

A fonte acima pode ser melhorada facilmente, (evitando AND e deslocando) por 'reformulação' 'x' como uma matriz de char de 4 bytes sem sinal e, de preferência, codificado em linha como uma única instrução em vez de ser uma função. Observe que mesmo este algoritmo simples pode ser muito lento agora, porque o código original pode ser executado mais rápido do cache de processadores modernos, e as tabelas de pesquisa (grandes) não se encaixam bem nos caches e podem causar um acesso mais lento à memória (além disso, no exemplo acima, requer endereços de computação dentro de uma tabela, para realizar as quatro pesquisas necessárias).

Tabelas de pesquisa em processamento de imagem

Exemplo de arquivo de tabela de consulta de 16 bits vermelho (A), verde (B), azul (C). (Linhas 14 a 65524 não mostradas)

Em aplicativos de análise de dados, como processamento de imagem , uma tabela de pesquisa (LUT) é usada para transformar os dados de entrada em um formato de saída mais desejável. Por exemplo, uma imagem em tons de cinza do planeta Saturno será transformada em uma imagem colorida para enfatizar as diferenças em seus anéis.

Um exemplo clássico de redução de cálculos de tempo de execução usando tabelas de pesquisa é obter o resultado de um cálculo de trigonometria , como o seno de um valor. O cálculo de funções trigonométricas pode retardar substancialmente uma aplicação de computação. O mesmo aplicativo pode terminar muito mais cedo quando primeiro pré-calcula o seno de um número de valores, por exemplo, para cada número inteiro de graus (a tabela pode ser definida como variáveis ​​estáticas em tempo de compilação, reduzindo os custos de tempo de execução repetida). Quando o programa requer o seno de um valor, ele pode usar a tabela de pesquisa para recuperar o valor do seno mais próximo de um endereço de memória e também pode interpolar para o seno do valor desejado, em vez de calcular por fórmula matemática. As tabelas de pesquisa são, portanto, usadas por coprocessadores matemáticos em sistemas de computador. Um erro em uma tabela de pesquisa foi responsável pelo infame bug de divisão de ponto flutuante da Intel .

As funções de uma única variável (como seno e cosseno) podem ser implementadas por uma matriz simples. As funções que envolvem duas ou mais variáveis ​​requerem técnicas de indexação de matriz multidimensional. O último caso pode, portanto, empregar uma matriz bidimensional de potência [x] [y] para substituir uma função para calcular x y para um intervalo limitado de valores de x e y. Funções que têm mais de um resultado podem ser implementadas com tabelas de pesquisa que são matrizes de estruturas.

Conforme mencionado, existem soluções intermediárias que usam tabelas em combinação com uma pequena quantidade de computação, geralmente usando interpolação . O pré-cálculo combinado com a interpolação pode produzir maior precisão para valores que caem entre dois valores pré-calculados. Esta técnica requer um pouco mais de tempo para ser executada, mas pode aumentar muito a precisão em aplicações que exigem maior precisão. Dependendo dos valores que estão sendo pré-computados, a pré - computação com interpolação também pode ser usada para reduzir o tamanho da tabela de pesquisa enquanto mantém a precisão.

No processamento de imagem , as tabelas de pesquisa são frequentemente chamadas de LUT s (ou 3DLUT) e fornecem um valor de saída para cada um de um intervalo de valores de índice. Um LUT comum, chamado mapa de cores ou paleta , é usado para determinar as cores e os valores de intensidade com os quais uma determinada imagem será exibida. Na tomografia computadorizada , "janelamento" se refere a um conceito relacionado para determinar como exibir a intensidade da radiação medida.

Embora frequentemente eficaz, o emprego de uma tabela de pesquisa pode resultar em uma penalidade severa se o cálculo que o LUT substitui for relativamente simples. O tempo de recuperação da memória e a complexidade dos requisitos de memória podem aumentar o tempo de operação do aplicativo e a complexidade do sistema em relação ao que seria exigido pelo cálculo de fórmula simples. A possibilidade de poluir o cache também pode se tornar um problema. Acessos de tabela para tabelas grandes quase certamente causarão perda de cache . Esse fenômeno está se tornando cada vez mais um problema à medida que os processadores ultrapassam a memória. Um problema semelhante aparece na rematerialização , uma otimização do compilador . Em alguns ambientes, como a linguagem de programação Java , as pesquisas de tabela podem ser ainda mais caras devido à verificação de limites obrigatória que envolve uma comparação adicional e ramificação para cada pesquisa.

Existem duas limitações fundamentais sobre quando é possível construir uma tabela de pesquisa para uma operação necessária. Um é a quantidade de memória disponível: não se pode construir uma tabela de pesquisa maior do que o espaço disponível para a tabela, embora seja possível construir tabelas de pesquisa baseadas em disco às custas do tempo de pesquisa. O outro é o tempo necessário para calcular os valores da tabela na primeira instância; embora isso geralmente precise ser feito apenas uma vez, se levar um tempo proibitivamente longo, pode tornar o uso de uma tabela de consulta uma solução inadequada. No entanto, conforme afirmado anteriormente, as tabelas podem ser definidas estaticamente em muitos casos.

Senos de computação

A maioria dos computadores realiza apenas operações aritméticas básicas e não pode calcular diretamente o seno de um determinado valor. Em vez disso, eles usam o algoritmo CORDIC ou uma fórmula complexa, como a seguinte série de Taylor para calcular o valor do seno com um alto grau de precisão:

(para x próximo de 0)

No entanto, pode ser caro para calcular, especialmente em processadores lentos, e há muitos aplicativos, especialmente em computação gráfica tradicional , que precisam calcular muitos milhares de valores de seno a cada segundo. Uma solução comum é calcular inicialmente o seno de muitos valores uniformemente distribuídos e, em seguida, para encontrar o seno de x , escolhemos o seno do valor mais próximo de x . Isso estará próximo do valor correto porque o seno é uma função contínua com uma taxa de mudança limitada. Por exemplo: 

real array sine_table[-1000..1000]
for x from -1000 to 1000
    sine_table[x] = sine(pi * x / 1000)

function lookup_sine(x)
    return sine_table[round(1000 * x / pi)]
Interpolação linear em uma parte da função seno

Infelizmente, a tabela requer um pouco de espaço: se números de ponto flutuante de precisão dupla IEEE forem usados, serão necessários mais de 16.000 bytes. Podemos usar menos amostras, mas nossa precisão piorará significativamente. Uma boa solução é a interpolação linear , que desenha uma linha entre os dois pontos da tabela em cada lado do valor e localiza a resposta nessa linha. Isso ainda é rápido de calcular e muito mais preciso para funções suaves , como a função seno. Aqui está um exemplo de interpolação linear: 

function lookup_sine(x)
    x1 = floor(x*1000/pi)
    y1 = sine_table[x1]
    y2 = sine_table[x1+1]
    return y1 + (y2-y1)*(x*1000/pi-x1)

A interpolação linear fornece uma função interpolada que é contínua, mas não terá, em geral, derivadas contínuas . Para uma interpolação mais suave de consulta de tabela que é contínua e tem primeira derivada contínua , deve-se usar o spline cúbico de Hermite .

Outra solução que usa um quarto do espaço, mas leva um pouco mais de tempo para ser computada, seria levar em consideração as relações entre seno e cosseno junto com suas regras de simetria. Nesse caso, a tabela de pesquisa é calculada usando a função seno para o primeiro quadrante (ou seja, sin (0..pi / 2)). Quando precisamos de um valor, atribuímos uma variável para ser o ângulo envolvido no primeiro quadrante. Em seguida, envolvemos o ângulo nos quatro quadrantes (não é necessário se os valores estiverem sempre entre 0 e 2 * pi) e retornamos o valor correto (ou seja, o primeiro quadrante é um retorno direto, o segundo quadrante é lido de pi / 2-x, terceiro e quarto são negativos do primeiro e do segundo, respectivamente). Para o cosseno, só precisamos retornar o ângulo deslocado por pi / 2 (ou seja, x + pi / 2). Para tangente, dividimos o seno pelo cosseno (o tratamento da divisão por zero pode ser necessário dependendo da implementação): 

function init_sine()
    for x from 0 to (360/4)+1
        sine_table[x] = sin(2*pi * x / 360)

function lookup_sine(x)
    x = wrap x from 0 to 360
    y = mod (x, 90)
    if (x <  90) return  sine_table[   y]
    if (x < 180) return  sine_table[90-y]
    if (x < 270) return -sine_table[   y]
    return -sine_table[90-y]

function lookup_cosine(x)
    return lookup_sine(x + 90)

function lookup_tan(x)
    return lookup_sine(x) / lookup_cosine(x)

Ao usar interpolação, o tamanho da tabela de pesquisa pode ser reduzido usando amostragem não uniforme , o que significa que onde a função é quase reta, usamos poucos pontos de amostra, enquanto onde ela muda o valor rapidamente usamos mais pontos de amostra para manter a aproximação perto da curva real. Para obter mais informações, consulte interpolação .

Outros usos de tabelas de pesquisa

Caches

Artigo principal: Cache (computação)

Caches de armazenamento (incluindo caches de disco para arquivos ou caches de processador para código ou dados) também funcionam como uma tabela de pesquisa. A mesa é construída com memória muito rápida em vez de ser armazenada em uma memória externa mais lenta e mantém duas partes de dados para um sub-intervalo de bits que compõem um endereço de memória externa (ou disco) (notavelmente os bits mais baixos de qualquer endereço externo possível) :

  • uma peça (a tag) contém o valor dos bits restantes do endereço; se esses bits corresponderem aos do endereço de memória para leitura ou gravação, a outra parte conterá o valor em cache para este endereço.
  • a outra parte mantém os dados associados a esse endereço.

Uma única pesquisa (rápida) é executada para ler a tag na tabela de pesquisa no índice especificado pelos bits mais baixos do endereço de armazenamento externo desejado e para determinar se o endereço de memória é atingido pelo cache. Quando um hit é encontrado, nenhum acesso à memória externa é necessário (exceto para operações de gravação, onde o valor em cache pode precisar ser atualizado de forma assíncrona para a memória mais lenta após algum tempo, ou se a posição no cache deve ser substituída por outro Morada).

LUTs de hardware

Na lógica digital , uma tabela de pesquisa pode ser implementada com um multiplexador cujas linhas de seleção são conduzidas pelo sinal de endereço e cujas entradas são os valores dos elementos contidos na matriz. Esses valores podem ser conectados fisicamente, como em um ASIC cuja finalidade é específica para uma função, ou fornecidos por travas D que permitem valores configuráveis. ( ROM , EPROM , EEPROM ou RAM .)

Um LUT de n bits pode codificar qualquer função booleana de entrada de n , armazenando a tabela verdade da função no LUT. Esta é uma maneira eficiente de codificar funções de lógica booleana , e LUTs com 4-6 bits de entrada são, na verdade, o principal componente dos FPGAs ( matrizes de portas programáveis ​​em campo) modernas que fornecem recursos lógicos de hardware reconfiguráveis.

Sistemas de aquisição e controle de dados

Em sistemas de aquisição e controle de dados , as tabelas de pesquisa são comumente usadas para realizar as seguintes operações em:

  • A aplicação de dados de calibração , de modo a aplicar correções para medições não calibradas ou valores de setpoint ; e
  • Execução da conversão da unidade de medida ; e
  • Execução de cálculos genéricos definidos pelo usuário.

Em alguns sistemas, os polinômios também podem ser definidos no lugar das tabelas de pesquisa para esses cálculos.

Veja também

Referências

links externos