Постоянное время для инициализации, используя больше пространства-программирование жемчуга - Колонок 1

Я читал «Программирование Pearls» и я действительно запутался в одном из объяснений решения - задач 9 в колонке 1.Постоянное время для инициализации, используя больше пространства-программирование жемчуга - Колонок 1

Вопрос был : При использовании растровых данных для представления набора целых чисел первая фаза инициализирует набор для пустого. Но инициализация пространства может занять много времени. Показать, как обойти эту проблему, разработав метод инициализации записи вектора в ноль при первом доступе.

Ответ: Эффект инициализации вектора данные [0 ... N-1], может быть достигнуто с подписью , содержащейся в двух дополнительных векторов п-элементов, от и к , и целое число top. Если элемент данных [я] был инициализирован, то из [I] < верхней и к [* от * [я]] = я. Таким образом из простой подпись и к и топ вместе убедитесь, что из не случайно подписан случайным содержимым памяти.

Я прочитал этот ответ несколько раз. Я этого не понимаю.

Может кто-нибудь объяснить это?

Спасибо,

источник

2012-04-22 Fihop

Эта страница помогла мне: http://comments.gmane.org/gmane.comp.programming.algogeeks/30667

Но позвольте мне увидеть, если я могу это объяснить.

В основном проблема заключается в следующем: инициализация вектора для всех 0s занимает нетривиальное количество времени, если вектор достаточно велик. Итак, как мы можем избежать инициализации до 0s, используя больше пространства? Как мы можем отличить случайные данные в этом векторе от данных, которые мы намеренно помещаем там?

Решение Bentley должно использовать «от» (карту) и «к» (подпись (действительно только обратная карта к индексу из)) векторов того же размера, что и вектор данных и «верхний», который представляет собой количество элементов в массиве данных до сих пор. Важно, чтобы from[i] < top, как описано ниже.

Используя пример из раствора: Мы объявляем массив данных и установить число элементов равным нулю:

top = 0 
data = int array of integers of size 1,000,000 
     (all random values since we did not initialize it)

Вставьте элемент с индексом 1 (I = 1, в этом случае). Но откуда мы знаем, что это не случайная величина? Мы используем карту и подпись. Индекс «from» равен индексу данных.

from[i] = top 
to[top] = i 
data[i] = 0 (I don't think it matters whether you set it to 0 or your intended value of 3) 
top++ (top is now 1)

Таким образом, вы можете сказать, что если to[from[i]] == i случайно. Ну, так как мы заявляем from[i] < top, это невозможно.

Проверьте следующие два случая:

A) Там нет элементов, вставленных еще в массив данных (то есть сверху = 0) что предполагает from[i] < 0, который не является допустимым индекс массива. Так что это невозможно.

B) Элемент вставлен (то есть верхний> 0, скажем, 1) С from[i] < top =>from[i] = 0. Однако мы ввели один элемент в массив данных, поэтому мы явно установили to[from[i]] = i.

Остальные следует за верхние = 2 ... п

НТНА

источник

2012-07-07 01:10:38 encore2097