FIFO кеш аномалии

Это Followup вызов из этого одного , если вы путать , пожалуйста , убедитесь , что один из первых.

Во-первых, пусть будет числом пропущенных кешей, которое будет иметь последовательность обращений к ресурсам, если предположить, что наш кеш имеет емкость и использует схему извлечения «первым пришел-первым обслужен» (FIFO), когда она заполнена. $m(s, k)$ $s$ $k$

Тогда при заданном соотношении вернуть непустую последовательность обращений к ресурсам , что существует с $r > 1$ $s$ $k > j$ $m(s, k) \geq r \cdot m(s, j)$ .

$s$ $r$ $s$

$r = 1.1$ $(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)$ $9$ $3$ $10$ $4$ .

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

Самый короткий код в байтах побеждает.

code-golf array-manipulation orlp
источник

Фоновое чтение: аномалия

Белади

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

Лохматый

@Shaggy Пойдите, проверьте другую проблему, и второстепенное чтение от другого комментария. Суть в том, что кеш FIFO может ухудшиться, поскольку он становится больше для некоторых серий запросов.

orlp

Ответы:

Wolfram Language (Mathematica) , 124 113 101 байт

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

Попробуйте онлайн!

ПРИМЕЧАНИЕ. Вывод TIO не является действительным списком, поскольку он будет очень длинным. Функция обертки в TIO сообщает вам о количестве сбоев страниц для двух объемов кеша.

Для актуального списка: попробуйте онлайн!

Похожие: arXiv: 1003.1336

Как?

Давайте предположим ситуацию, когда у нас есть две емкости кеша, 3и4 .

Кроме того, допустим, что 3-cache {4, 2, 5}выгружен, а 4-cache {5, 4, 3, 2}выгружен. Тогда, давайте попробуем пейджинг {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 было 5 ошибок страницы, в то время как у 4-cache было 10. Мы также вернулись в исходное состояние.

Здесь, если мы повторим пейджинг {1, 2, 3, 4, 5}, мы асимптотически достигнем отношения 2.

Мы можем распространить это явление на более высокие объемы кэша, чтобы мы могли просматривать страницы {1, 2, 3, ... , 2n + 1}и получать любое соотношение.

Юнг Хван Мин
источник