.. _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                   |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+---------------------+-------+
| LFU_Fast     | A faster implementation of 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                   |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+---------------------+-------+
| SLRU         | segmented LRU with different number of user-specified segments                                                                                                                    |{"N_segments": N}   | 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              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+---------------------+-------+
| LinuxClock   | Approximation of linux clock algorithm                                                                                                                                            | None               | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+---------------------+-------+
| AdaptiveSLRU | Similar to ARC, but use two LRU segments instead of one LRU and one LFU                                                                                                           | None               | Python              |       |
+--------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+---------------------+-------+
| SLRU         | Segmented LRU with N segments                                                                                                                                                     | {"N":N}            | 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.