note: this is still the faster version

[earonesty]

was curious, even with the new builtin ordered dict, the simple python impl is still slower, but barely! should probably update the readme. no need to compare to old and extremely slow impls.

A = TypeVar("A")
T = TypeVar("T")

class LRU(Generic[A, T]):
    """Simple LRU cache using a dictionary."""
    def __init__(self, maxsize: int):
        self.cache = dict[Any]()
        self.maxsize = maxsize

    def get(self, key: A, default: T | None = None) -> T | None:
        if key not in self.cache:
            return default
        else:
            self.cache[key] = self.cache.pop(key)
            return self.cache[key]

    def put(self, key: A, value: int) -> None:
        self.cache[key] = value
        if len(self.cache) > self.maxsize:
            self.cache.pop(next(iter(self.cache)))

timeit

    simple = LRU(10)
    ll = lib.LRU(10)

    import timeit

    print("simple:", timeit.timeit(lambda: [simple.put(i, 1) for i in range(100)], number=10000))
    print("lru-dict:", timeit.timeit(lambda: [ll.__setitem__(i, 1) for i in range(100)], number=10000))

simple timeit results:

simple: 0.1914528000052087
lru-dict: 0.1341520000132732

[MarkReedZ]

With python 3.12.3 using the dict is faster for me

simple: 0.13609749102033675
lru-dict: 0.16980825795326382

[miili]

Tradeoff is with large dicts.

Here, the size is 4096 with Python 3.13.1.

simple: 27.91239029799999
lru-dict: 2.6699569709999196

Ran with

simple = LRU(4096)
ll = LLRU(4096)

print(
    "simple:",
    timeit.timeit(lambda: [simple.put(i, 1) for i in range(10000)], number=1000),
)
print(
    "lru-dict:",
    timeit.timeit(lambda: [ll.__setitem__(i, 1) for i in range(10000)], number=1000),
)

[miili]

Put and subsequent access leads to:

simple: 3.064283808000255
lru-dict: 1.0523998819999179

Here is the optimized example:

import random
import timeit
from typing import Generic, TypeVar

from lru import LRU as LLRU

_A = TypeVar("A")
_T = TypeVar("T")


class LRU(Generic[_A, _T]):
    """Simple LRU cache using a dictionary."""

    def __init__(self, maxsize: int):
        self.cache = dict()
        self.maxsize = maxsize

    def get(self, key: _A, default: _T | None = None) -> _T | None:
        try:
            val = self.cache.pop(key)
            self.cache[key] = val
            return val
        except KeyError:
            return default

    def put(self, key: _A, value: int) -> None:
        self.cache[key] = value
        if len(self.cache) > self.maxsize:
            self.cache.pop(next(iter(self.cache)))

    __setitem__ = put
    __getitem__ = get


simple = LRU(1024)
ll = LLRU(1024)

data = random.randbytes(4096)


def test(lru, access: int = 1000):
    def foo():
        for i in range(access):
            lru[i] = data
        for i in range(access):
            _ = lru[i]

    return foo


print(
    "simple:",
    timeit.timeit(test(simple, access=1000), number=10000),
)
print(
    "lru-dict:",
    timeit.timeit(test(ll, access=1000), number=10000),
)