Salvando na inicialização do array

19

Li recentemente que é possível ter matrizes que não precisam ser inicializadas, ou seja, é possível usá-las sem ter que gastar algum tempo tentando definir cada membro com o valor padrão. ou seja, você pode começar a usar a matriz como se ela tivesse sido inicializada pelo valor padrão sem precisar inicializá-la. (Desculpe, não me lembro onde li isso).

Por exemplo, por que isso pode ser surpreendente:

Digamos que você está tentando modelar um pior caso hashtable (para cada um insert / pesquisa de exclusão /) de inteiros no intervalo .[ 1 , n 2 ]O(1)[1,n2]

Você pode alocar uma matriz de tamanho bits e usar bits individuais para representar a existência de um número inteiro na hashtable. Nota: alocar memória é considerado tempo O ( 1 ) .n2O(1)

Agora, se você não precisou inicializar essa matriz, qualquer sequência das operações say nesta hashtable é agora o pior caso O ( n ) .nO(n)

Portanto, você tem uma implementação de hash "perfeita", que para uma sequência de operações usa Θ ( n 2 ) de espaço, mas é executada em O ( n ) tempo!nΘ(n2)O(n)

Normalmente, espera-se que seu tempo de execução seja pelo menos tão ruim quanto o uso de espaço!

Nota: O exemplo acima pode ser usado para uma implementação de um conjunto esparso ou matriz esparsa, portanto, não é apenas de interesse teórico, suponho.

Então a questão é:

Como é possível ter uma matriz como estrutura de dados que nos permita pular a etapa de inicialização?

Aryabhata
fonte
@Aryabhata Qual é a referência que você mencionou?
191 uli
1
"usar memória" não é o mesmo que "ter alocado, mas nunca acessado a memória", portanto, acho que o "paradoxo" motivador não existe.
Raphael
1
Eu acho que o primeiro parágrafo é bem claro: tenha um valor padrão, sem levar tempo para preencher a matriz com o valor padrão. A resposta, caso outra pessoa tenha tempo de escrevê-la antes de mim, está aqui scholar.google.co.uk/… Há também uma breve explicação no meu blog rgrig.blogspot.co.uk/2008/12/array -puzzle-solution.html
rgrig
@uli: Esta é uma pergunta de propagação, na verdade eu li isso há muito tempo.
Aryabhata
@Raphael: Ainda é surpreendente quando você ouve algo sobre isso pela primeira vez. A maioria dos paradoxos não são :-)
Aryabhata

Respostas:

15

Esse é um truque muito geral, que pode ser usado para outros fins que não o hash. Abaixo, dou uma implementação (em pseudo-código).

Deixe três vetores não inicializados , P e V de tamanho n cada. Nós os usaremos para realizar as operações solicitadas por nossa estrutura de dados. Também mantemos uma variávelAPVn . As operações são implementadas da seguinte forma:pos

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i) 
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 

A matriz simplesmente armazena os valores que são passados ​​pelo procedimento s e t . As matrizes V eAsetV funcionam como certificados que podem dizer se uma determinada posição em A foi inicializada.PA

Observe que a cada momento os elementos em variando de 0 a p o s - 1, são inicializados. Estamos, portanto, pode usar com segurança esses valores como um certificado para os valores inicializados em A . Para cada posição i em A que é inicializada, há um elemento correspondente no vetor P cujo valor é igual a i . Isso é apontado por V [ i ] . Portanto, se olharmos para o elemento correspondente, P [ V [ i ] ] e seu valor é iP0pos1AiAPiV[i]P[V[i]]i, sabemos que foi inicializado (já que P nunca mente, porque todos os elementos que estamos considerando são inicializados). Da mesma forma, se A [ i ] não for inicializado, V [ i ] poderá apontar para uma posição em P fora do intervalo 0 .. p o s - 1 , quando tivermos certeza de que não foi inicializado ou apontar para uma posição dentro desse intervalo. Mas este P [ j ] em particular corresponde a uma posição diferente em A e, portanto,A[i]PA[i]V[i]P0..pos1P[j]A , então sabemos que A [ i ] não foi inicializado.P[j]iA[i]

É fácil ver que todas essas operações são feitas em tempo constante. Além disso, o espaço utilizado é para cada um dos vetores e O ( 1 ) para a variável p o s , portanto O ( n ) no total.O(n)O(1)posO(n)

zotachidil
fonte
Mas não é possível que, por acaso, seja igual a i sem A [ i ] ter sido definido? P[V[i]]iA[i]
Robert S. Barnes
É mas então pos será menor que V [i] agora não seria? Porque caso contrário, não seria por acaso. Como tendo pos mais alto que V [i], significa que definimos especificamente o valor de P no índice V [i] para um valor específico que escolhemos, ou seja, i.
Lobo
Note-se que este é um exemplo clássico de algo que é impossível de se fazer no (portátil) C.
TLW