Экономия на инициализации массива

Недавно я читал, что возможно иметь массивы, которые не нужно инициализировать, то есть их можно использовать, не тратя время на попытки установить для каждого элемента значение по умолчанию. то есть вы можете начать использовать массив, как если бы он был инициализирован значением по умолчанию без необходимости его инициализации. (Извините, я не помню, где я это читал).

Например, почему это может быть удивительно:

Скажем, вы пытаетесь смоделировать в худшем случае хеш-таблицу (для каждого из вставки / удаления / поиска) целых чисел в диапазоне [ 1 , n 2 ] .$\mathcal{O}(1)$$[1, n^2]$

Вы можете выделить массив размером бита и использовать отдельные биты для представления существования целого числа в хеш-таблице. Примечание: выделение памяти считается O ( 1 ) времени.$n^2$$\mathcal{O}(1)$

Теперь, если вам вообще не нужно было инициализировать этот массив, любая последовательность, скажем, операций на этой хеш-таблице теперь является наихудшим случаем O ( n ) .$n$$\mathcal{O}(n)$

Таким образом , в сущности, у вас есть «идеальный» реализацию хеш - функции, которая для последовательности операций использует thetas ; ( п 2 ) пространство, но работает в O ( N ) времени!$n$$\Theta(n^2)$$\mathcal{O}(n)$

Обычно можно ожидать, что ваше время выполнения будет как минимум таким же плохим, как и использование вами пространства!

Примечание: приведенный выше пример может быть использован для реализации разреженного набора или разреженной матрицы, так что, я полагаю, он представляет не только теоретический интерес.

Итак, вопрос:

Как можно иметь массив, подобный структуре данных, который позволяет нам пропустить этап инициализации?

Это очень общий прием, который можно использовать для других целей, кроме хеширования. Ниже я приведу реализацию (в псевдокоде).

$A$$P$$V$$n$$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$$set$$V$$P$$A$

$P$$0$$pos-1$$A$$i$$A$$P$$i$$V[i]$$P[V[i]]$$i$$A[i]$$P$$A[i]$$V[i]$$P$$0..pos-1$$P[j]$$A$$P[j] \neq i$$A[i]$

$O(n)$$O(1)$$pos$$O(n)$