Алгоритм блокировки для поиска перестановок фиксированной длины

Question

Чтобы найти все перестановки длиной два, можно использовать следующую простую программу:

  #include <iostream>
  using namespace std;
  int main(int argc, const char *argv[])
  {
      int l[] = {0, 1, 2, 3, 4, 5};

      const int length = sizeof(l)/sizeof(l[0]);

      for(int i = 0; i + 1 < length; i++)
          for(int j = i + 1; j < length; j++)
              cout << "(" << l[i] << ", " << l[j] << ")" << endl;

      return 0;
  }

Но в приложении, где мне это нужно, отдельные элементы являются БОЛЬШИМИ, и их необходимо создать перед использованием набора. Поэтому я пытаюсь найти алгоритм, который делает то же самое, но с блокировкой. Блокировка должна позволить мне иметь банк, который можно использовать для кэширования.

Ниже показана одна (вручную) созданная последовательность с банком, который может содержать 4 элемента:

SETS, Cache miss, bank
(0,1) * *         0, 1
(0,2) *           0, 1, 2
(0,3) *           0, 1, 2, 3
(1,2)             0, 1, 2, 3
(1,3)             0, 1, 2, 3
(2,3)             0, 1, 2, 3
(0,4) *           0, 1, 2, 4
(1,4)             0, 1, 2, 4
(2,4)             0, 1, 2, 4
(0,5) *           0, 1, 4, 5
(1,5)             0, 1, 4, 5
(4,5)             0, 1, 4, 5
(2,5)             0, 2, 4, 5
(3,4) *           3, 2, 4, 5
(3,5)             3, 2, 4, 5

Кто-нибудь из вас знает решение этой проблемы? или вы можете указать в правильном направлении.

- Allan

Answer 1

Создать класс cache с методом get(int ID), который возвращает элемент с соответствующим идентификатором:

(1) Если соответствующий элемент уже кэширован, вернуть кэшированную копию (или указательк этому)(2) Если это не так: создайте его, удалите элемент из кэша, добавьте новый элемент в кэш и перейдите к пункту (1)

Сложная задача - решить, какой элемент удалить изкеш в (2).Оптимальный выбор - убрать предмет, который больше не понадобится в течение длительного времени.Если это не практично (например, потому что вы недостаточно знаете о схеме доступа), есть много альтернатив.

Наиболее распространенные из них:

• LRU: удалить наименее использованный элемент
• MRU: удалить последний использованный элемент
• LFU: удалите наименее часто используемый элемент

См. статью Википедии об алгоритмах кэширования для дополнительных примеров.