To jest kolejne wyzwanie z tego , jeśli jesteś zdezorientowany, sprawdź to najpierw.

Po pierwsze, niech jest liczbą cache strzela sekwencja s dostępów zasobów miałoby zakładając naszą pamięć ma pojemność k i wykorzystuje pierwszy-w-pierwsze wyszło (FIFO) program wyrzutową gdy jest pełny.$m(s, k)$$s$$k$

Następnie dana stosunkiem , powrót niepusty sekwencję zasobów dostępy s tak, że istnieje k > j o m ( s , k ) ≥ R ⋅ m ( s , j ) .$r > 1$$s$$k > j$$m(s, k) \geq r \cdot m(s, j)$

W prostym języku angielskim, skonstruować ciąg zasobu dostępu tak, że nie ma gdzie dwa rozmiary większy cache cache ma (przynajmniej) R razy więcej tęskni cache, gdy stosowane do rozwiązywania s .$s$$r$$s$

Przykładem dla , poprawnym wyjściem jest sekwencja ( 3 , 2 , 1 , 0 , 3 , 2 , 4 , 3 , 2 , 1 , 0 , 4 ) , ponieważ powoduje 9 braków pamięci podręcznej dla wielkości pamięci podręcznej 3 , ale 10 chybień dla rozmiaru pamięci podręcznej 4 .$r = 1.1$$(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)$$9$$3$$10$$4$

Nie ma znaczenia, jaką sekwencję zwracasz, o ile spełnia ona wymagania.

Najkrótszy kod w bajtach wygrywa.

Wolfram Language (Mathematica) , 124 113 101 bajtów

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

Wypróbuj online!

UWAGA: Wyjście TIO nie jest faktyczną listą, ponieważ byłoby bardzo długie. Funkcja owijania w TIO informuje o liczbie błędów strony dla dwóch pojemności pamięci podręcznej.

Rzeczywista lista: Wypróbuj online!

Powiązane: arXiv: 1003.1336

W jaki sposób?

Załóżmy, że mamy dwie pojemności pamięci podręcznej 3i 4.

Powiedzmy też, że 3-cache {4, 2, 5}stronicował, a 4-cache {5, 4, 3, 2}stronicował. Następnie spróbujmy stronicować {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}

3-Cache miał 5 stron błędów, natomiast 4-cache miał 10. Mamy również wróciliśmy do naszego pierwotnego stanu.

Gdybyśmy powtarzali stronicowanie {1, 2, 3, 4, 5}, asymptotycznie osiągnęlibyśmy stosunek 2.

Możemy rozszerzyć to zjawisko na wyższe pojemności pamięci podręcznej, abyśmy mogli wyświetlać strony {1, 2, 3, ... , 2n + 1}i uzyskiwać dowolne proporcje.