.. _algorithms:

Algorithms
================
.. _cache_replacement_algorithms:

+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| algorithm    | description                                                                                                                                                                       | cache_params    | implemented version | Other |
+==============+===================================================================================================================================================================================+=================+=====================+=======+
| LRU          | Least recent used                                                                                                                                                                 | None            | C and Python        |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| Optimal      | Optimal                                                                                                                                                                           | None            | C and Python        |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| FIFO         | First in first out                                                                                                                                                                | None            | C and Python        |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| LFU          | Least frequently used                                                                                                                                                             | None            | C                   |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| LRU_2        | LRU on the second to the most recent timestamp                                                                                                                                    | None            | C                   |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| LRU_K        | LRU on the Kth to the most recent timestamp                                                                                                                                       | {"K": K}        | C                   |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| MRU          | Most recent used                                                                                                                                                                  | None            | C and Python        |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| Random       | Random evict element                                                                                                                                                              | None            | C and Python        |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| clock        | Second chance algorithm, when evicting, if the element that current clock hand points to has value 1, set to 0, giving it a second chance, otherwise, evict it.                   | None            | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| AdaptiveSLRU | Similar to ARC, but use two LRU segments instead of one LRU and one LFU                                                                                                           | None            | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| SLRU         | Segmented LRU with two segments                                                                                                                                                   | {"ratio":ratio} | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| S4LRU        | Segmented LRU with four segments                                                                                                                                                  | None            | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| LFU_RR       | Least frequent used, when there are more than one with same least frequency, random select one                                                                                    | None            | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
| LFU_MRU      | Least frequent used, when there are more than one with same least frequency, select most recent one                                                                               | None            | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+
|              |                                                                                                                                                                                   |                 |                     |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+---------------------+-------+



Please notice that when passing cache_params, all parameters are stored in a dictionary.
