Anomalie pamięci podręcznej FIFO

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

Po pierwsze, niech jest liczbą cache strzela sekwencja dostępów zasobów miałoby zakładając naszą pamięć ma pojemność 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 tak, że istnieje o . $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) razy więcej tęskni cache, gdy stosowane do rozwiązywania . $s$ $r$ $s$

Przykładem dla , poprawnym wyjściem jest sekwencja , ponieważ powoduje braków pamięci podręcznej dla wielkości pamięci podręcznej , ale chybień dla rozmiaru pamięci podręcznej . $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.

code-golf array-manipulation orlp
źródło

Dodatkowe informacje: Anomalia

Bélády'ego

Może to być tylko wyczerpanie, ale to wyzwanie nie jest dla mnie do końca jasne; czy możesz podać działający przykład i kilka innych przypadków testowych?

Kudłaty

@Shaggy Go sprawdź inne wyzwanie i czytanie w tle z drugiego komentarza. Najważniejsze jest to, że pamięć podręczna FIFO może się pogorszyć, ponieważ staje się większa dla niektórych serii żądań.

orlp

Odpowiedzi:

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.

JungHwan Min
źródło