Временная и пространственная локальность с массивами

Я немного запутался в значениях пространственной и временной локальности. Я надеюсь, посмотрев на это с помощью массива, это поможет мне понять это лучше.

В следующем примере: A [0] [1], A [0] [2], A [0] [3].... и т.д.

Означает ли это временную локальность? Я вижу, что к одной и той же строке обращаются много раз, но при разных смещениях... означает ли это, что обращается к другому адресу?

Кроме того, могу ли я сказать, что пример такой: A [1], A [2], A [3]... и т.д.

Демонстрирует пространственную локальность?

Надеюсь, некоторые разъяснения о том, как временная и пространственная локальность работают в реальном коде, помогут мне лучше понять их.

Ответ 1

Пространственная и временная локальность описывают две разные характеристики того, как программы получают доступ к данным (или инструкциям). В Wikipedia есть хорошая статья о локальности ссылки.

Говорят, что последовательность ссылок имеет spatial локальность, если близкие по времени объекты, близкие по времени, также находятся в пространстве (соседние адреса памяти, соседние сектора на диске и т.д.). Говорят, что последовательность имеет temporal локальность, если доступ к одной и той же вещи кластеризуется во времени.

Если программа обращается к каждому элементу в большом массиве и читает его один раз, а затем переходит к следующему элементу и не повторяет доступ к какой-либо определенной точке до тех пор, пока она не коснется любого другого местоположения, тогда это явный случай пространственного локальность, но не временная локальность. С другой стороны, если программа тратит время на повторный доступ к случайному подмножеству местоположений в массиве, прежде чем переходить к другому случайному подмножеству, говорят, что он имеет временную локальность, но не пространственную локальность. Хорошо написанная программа будет иметь структуры данных, которые объединяют вещи, к которым обращаются вместе, обеспечивая тем самым пространственную локальность. Если вы, вероятно, будете иметь доступ к B вскоре после обращения к A, то следует выделить как A, так и B. друг друга.

Ваш первый пример

A[0][1], A[0][2], A[0][3]

показывает пространственную локальность, близкие по времени объекты, близкие по времени, близки в пространстве. Он не показывает временную локальность, потому что вы не обращались к одной и той же вещи более одного раза.

Ваш второй пример

A[1], A[2], A[3]

также показывает пространственную локальность, но не временную локальность.

Вот пример, показывающий временную локальность

A[1], A[2000], A[1], A[1], A[2000], A[30], A[30], A[2000], A[30], A[2000], A[30], A[4], A[4]

Ответ 2

Простыми словами,

Временная локальность: понятие о том, что ресурс, на который ссылается в какой-то момент вовремя будет ссылаться снова в ближайшем будущем.

Пространственная локальность: понятие о вероятности ссылки на ресурс выше, если ресурс, находящийся рядом с ним, просто ссылается.

Источник (ы): Википедия

Ответ 3

Вот пример кода с местностью:

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;

Существует временная локализация, потому что к сумме часто обращаются в цикле. Временная локальность эксплуатируется путем сохранения недавно использованных инструкций и значений данных в кэш-памяти и путем использования иерархии кеша. Или даже в регистре, а не в памяти вообще.
Существует пространственная локальность, потому что у нас есть массив "а", и мы получаем доступ к каждому элементу массива по порядку. Пространственная локальность обычно используется за счет использования более крупных блоков кеша и включения механизмов предварительной выборки (выборки элементов ожидаемого использования) в логику управления кешем.

Ответ 4

Временная локализация является частным случаем пространственной локализации.

Ответ 5

Мне время от времени трудно вспомнить разницу между ними, хотя я помню оба типа местности.

Помните о Spatical Locality, помните "последовательно" наречие.

Помните, что в начале изучения алгоритмов сортировки вы видите "временную переменную", которую нужно поменять местами. например, пузырьковая сортировка. У него есть два цикла, и обмен там происходит как int temp =.....

С помощью способа вы можете узнать, какое определение кому принадлежит.

Ответ 6

Временная локализация: временная локализация основана на многократно ссылающихся ресурсах.

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