webentwicklung-frage-antwort-db.com.de

Temporale vs. räumliche Lokalität mit Arrays

Ich bin etwas verwirrt über die Bedeutung der räumlichen und zeitlichen Lage. Ich hoffe, wenn ich es mit einem Array-Beispiel anschaue, wird es mir helfen, es besser zu verstehen.

In einem Beispiel wie diesem: A [0] [1], A [0] [2], A [0] [3] .... etc

Zeigt dies zeitliche Lokalität? Ich sehe, dass auf dieselbe Zeile oft zugegriffen wird, aber bei unterschiedlichen Offsets ... bedeutet das, dass auf eine andere Adresse zugegriffen wird?

Ich kann auch sagen, dass ein Beispiel wie dieses lautet: A [1], A [2], A [3] ... etc

Demonstriert räumliche Lokalität

Ich hoffe, dass einige Klarstellungen, wie zeitliche und räumliche Lokalität in realem Code funktioniert, mir helfen werden, sie besser zu verstehen.

32
Eric Smith

Die räumliche und zeitliche Lokalität beschreibt zwei unterschiedliche Merkmale, wie Programme auf Daten (oder Anweisungen) zugreifen. Wikipedia hat einen guten Artikel über Fundstelle .

Es wird gesagt, dass eine Sequenz von Referenzen spatial locality hat, wenn Dinge, auf die zeitlich nahe verwiesen wird, ebenfalls räumlich nah sind (nahegelegene Speicheradressen, nahegelegene Sektoren auf einer Platte usw.). Es wird gesagt, dass eine Sequenz temporal locality hat, wenn Zugriffe auf dasselbe Objekt zeitlich gruppiert sind.

Wenn ein Programm auf jedes Element in einem großen Array zugreift und es einmal liest, dann zum nächsten Element weitergeht und keinen Zugriff auf einen bestimmten Ort wiederholt, bis es jeden anderen Ort berührt hat, ist dies ein eindeutiger Fall von räumlich locality, aber nicht temporal locality. Auf der anderen Seite, wenn ein Programm wiederholt auf eine zufällige Teilmenge der Orte auf dem Array zugreift, bevor es zu einer anderen Teilmenge weitergeht, wird gesagt, dass es temporal locality, aber nicht räumlich locality hat. Ein gut geschriebenes Programm wird Datenstrukturen haben, die zusammengruppierte Objekte zusammenfassen, wodurch räumliche Lokalität sichergestellt wird. Wenn Ihr Programm wahrscheinlich auf B zugreift, nachdem es auf A zugreift, sollten sowohl A als auch B nahe beieinander liegen.

Dein erstes Beispiel

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

zeigt räumliche -Lokalität, Dinge, auf die zeitnah zugegriffen wird, sind räumlich nahe. Temporal locality wird nicht angezeigt, weil Sie nicht mehrmals auf dasselbe Objekt zugegriffen haben.

Dein zweites Beispiel

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

zeigt auch räumliche Lokalität, aber nicht zeitliche Lokalität.

Hier ist ein Beispiel, das temporal zeigt

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]
66
amdn

In einfachen Worten

Zeitliche Lokalität: Das Konzept, dass eine Ressource, die zu einem bestimmten Zeitpunkt zeitlich ___ referenziert wird, irgendwann in naher Zukunft erneut referenziert wird.

Räumliche Lokalität: Das Konzept, dass die Wahrscheinlichkeit besteht, dass eine Ressource referenziert wird, ist __. Höher, wenn auf eine Ressource in der Nähe nur referenziert wurde.

Quelle (n): Wikipedia

14

Hier ist ein Beispiel für Code mit locality:

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;
  • Es gibt temporale Lokalität , weil in der Schleife häufig auf die Summe zugegriffen wird. Die zeitliche Lokalität wird ausgenutzt, indem kürzlich verwendete Befehls- und Datenwerte im Cache-Speicher verbleiben und eine Cache-Hierarchie ausgenutzt wird. Oder sogar in einem Register, überhaupt nicht in Erinnerung.

  • Es gibt räumliche Lokalität , weil wir ein Array 'a' haben und wir Auf jedes Element des Arrays in der Reihenfolge zugreifen. Die räumliche Lokalität wird im Allgemeinen ausgenutzt, indem größere Cache-Blöcke verwendet werden und indem Vorabrufmechanismen (Abrufen von Elementen mit erwarteter Verwendung) in die Cache-Steuerlogik integriert werden.

8
superrcoop

Zeitliche Lokalität ist der Spezialfall der räumlichen Lokalität.

0
laura

Zeitliche Lokalität: Die zeitliche Lokalität basiert auf wiederholt referenzierten Ressourcen.

Räumliche Lokalität: Die räumliche Lokalität gibt an, dass die Daten neben den zuletzt referenzierten Daten in naher Zukunft angefordert werden.

0
Raushan

Ich habe immer wieder Schwierigkeiten, mich an den Unterschied zwischen ihnen zu erinnern, obwohl ich mich an beide Arten von Lokalitäten erinnere. 

Spatical Locality Denken Sie daran, dass sich das Adverb "sequenziell" im Kopf befindet.

Temporal Locality Wenn Sie daran denken, dass Sie zu Beginn des Sortierens von Algos "eine temporäre Variable" zum Wechseln sehen. z.B. Blase sortieren. Es hat zwei Schleifen und dort zu tauschen ist wie int temp = ......

Sie können anhand des Weges erkennen, welche Definition zu was gehört.

0
snr