Dies ist die Folgeherausforderung von dieser , wenn Sie verwirrt sind, überprüfen Sie diese bitte zuerst.

Zunächst sei die Anzahl der Cache-Fehlschläge einer Sequenz von Ressourcenzugriffen, vorausgesetzt, unser Cache hat die Kapazität und verwendet ein FIFO-Auswurfschema (First-In-First-Out), wenn es voll ist.$m(s, k)$$s$$k$

Geben Sie dann bei einem Verhältnis eine nicht leere Folge von Ressourcenzugriffen so dass mit .$r > 1$$s$$k > j$$m(s, k) \geq r \cdot m(s, j)$

Im Klartext, Konstrukt , das eine Sequenz der Ressource zugreift , so dass es zwei Cache - Größen , wo die größeren Cache (mindestens) hat - mal mehr Cache - Misses , wenn zur Lösung verwendet .$s$$r$$s$

Ein Beispiel für , eine gültige Ausgabe ist die Folge , da sie bei einer Cache-Größe von Cache-Fehlschläge verursacht , aber Fehler bei einer Cache-Größe von .$r = 1.1$$(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)$$9$$3$$10$$4$

Es spielt keine Rolle, welche Sequenz Sie zurückgeben, solange sie den Anforderungen entspricht.

Kürzester Code in Bytes gewinnt.

Wolfram Language (Mathematica) , 124 113 101 Bytes

Flatten@{s=⌈2#⌉;q=Range[r=2s+1];g=Mod[q s-s,r];{Sort@g[[#+1;;]],g[[;;#]]}&~Array~r,Table[q,s^3]}&

Probieren Sie es online!

HINWEIS: Die TIO-Ausgabe ist nicht die tatsächliche Liste, da sie sehr lang wäre. Die Wrapper-Funktion von TIO gibt die Anzahl der Seitenfehler für zwei Cache-Kapazitäten an.

Für die aktuelle Liste: Probieren Sie es online!

Siehe auch: arXiv: 1003.1336

Wie?

Nehmen wir an, wir haben zwei Cache-Kapazitäten 3und 4.

3Nehmen wir auch an, der Cache hat sich {4, 2, 5}ausgelagert, und der 4Cache hat sich {5, 4, 3, 2}ausgelagert. Dann versuchen wir es mit Paging {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}:

page  3-cache   4-cache
      {4,2,5}  {5,4,3,2}
  1   {1,4,2}  {1,5,4,3}
  2   {1,4,2}  {2,1,5,4}
  3   {3,1,4}  {3,2,1,5}
  4   {3,1,4}  {4,3,2,1}
  5   {5,3,1}  {5,4,3,2}
  1   {5,3,1}  {1,5,4,3}
  2   {2,5,3}  {2,1,5,4}
  3   {2,5,3}  {3,2,1,5}
  4   {4,2,5}  {4,3,2,1}
  5   {4,2,5}  {5,4,3,2}

Der 3-cache hatte 5 Seitenfehler, während der 4-cache 10 hatte. Wir sind auch in unseren ursprünglichen Zustand zurückgekehrt.

Wenn wir hier das Blättern wiederholen {1, 2, 3, 4, 5}, erreichen wir asymptotisch das Verhältnis von 2.

Wir können dieses Phänomen auf höhere Cache-Kapazitäten ausweiten, so dass wir {1, 2, 3, ... , 2n + 1}mit jedem Verhältnis paginieren und enden können.