Постоянное время для инициализации с использованием большего количества жемчужин программирования - Столбец 1
Я читал "Программирование жемчужин", и я действительно запутался в одном из объяснений решения - проблема 9 в столбце 1.
Вопрос заключался в следующем: при использовании растровых данных для представления набора целых чисел первая фаза инициализирует набор пустым. Но инициализация пространства сама по себе может занять много времени. Покажите, как обойти эту проблему, разработав метод инициализации записи вектора в ноль при первом обращении к нему.
Ответ был таким: Эффект инициализации векторных данных[0...n-1] может быть достигнут с помощью сигнатуры, содержащейся в двух дополнительных n-элементных векторах, от и до, и целой вершине. Если элементdata[i] был инициализирован, то из[i] < top и в[* из *[i]] = i. Таким образом, from является простой сигнатурой, а вместе с top и top убедитесь, что from не случайно подписана случайным содержимым памяти.
Я прочитал этот ответ несколько раз. Я не понимаю это
Может кто-нибудь объяснить это?
Спасибо,
2 ответа
Эта страница помогла мне: http://comments.gmane.org/gmane.comp.programming.algogeeks/30667
Но дай мне посмотреть, смогу ли я это объяснить.
По сути, проблема в том, что инициализация вектора для всех нулей занимает нетривиальное время, если вектор достаточно велик. Итак, как мы можем избежать инициализации в 0, используя больше места? т.е. как мы можем отличить случайные данные в этом векторе от данных, которые мы намеренно поместили туда?
Решение Bentley заключается в использовании векторов "from" (карта) и "to" (сигнатура [на самом деле просто обратная карта к индексу from]) того же размера, что и вектор данных, и "top" - число элементов в массиве данных до сих пор. Это важно что 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[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) В массив данных еще не вставлено никаких элементов (т. Е. Top = 0), что подразумевает from[i] < 0 который не является допустимым индексом массива. Так что это невозможно.
B) Вставлен элемент (то есть top > 0, допустим, это 1), так как from[i] < top => from[i] = 0, Тем не менее, мы вставили один элемент в массив данных, поэтому мы явно установили to[from[i]] = i,
Остальное следует для top = 2...n
НТН
Я обнаружил, что сообщение в следующей ссылке очень полезно для понимания идеи, стоящей за уловкой инициализации с постоянным временем.
Ссылка: http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
Надеюсь, поможет-