On Thu, Dec 31, 2020 at 8:43 AM James Oldfield <[email protected]> wrote: > > 1. My first suggestion is to replace the odd cache logic with a > straightforward classic LRU cache. I'm hoping this is uncontroversial, > but I can imagine there might be programs that somehow depend on the > current behaviour. But my suspicion is that many more suffer and just no > one looked hard enough to notice. >
LRU has worst scenario too. And implementing LRU requires some memory. For example, functools.lru_cache() uses doubly-linked list internally. There are some LRU-like algorithms, like clock or double chance. But all algorithms have worst scenario anyway. Another option is a random eviction algorithm. It chose random entry to evict. * Frequently used keys have a high chance for cache hit, like LFU (least frequently used). * When frequently used keys are changed in time, old frequently used keys are eventually evicted. (behaves like least recently frequently used?) * Minimum overhead for managing keys. So I think a random eviction algorithm is better than LRU. Off topic: Can we add random_cache to functools, like lru_cache? Regards, -- Inada Naoki <[email protected]> _______________________________________________ Python-ideas mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/[email protected]/message/PM64J2I77AIOMN7XXZSY2F6O4SFXEEHX/ Code of Conduct: http://python.org/psf/codeofconduct/
