LRU Paging Competitive Ratio

Problem

Return the ratio of LRU page faults to offline-optimal page faults on a request sequence.

Simulate LRU with a cache of cache_size pages, then simulate Belady's optimal policy that evicts the page used farthest in the future, and divide the two fault counts. Return 0.0 for a non-positive cache or an empty request sequence.

Hint

Belady evicts the resident page whose next request is farthest away, which lower-bounds any online policy.

Test cases

case 1

in: [[1,2,3,4,1,2,5,1,2,3,4,5],3]

expected: 1.4285714285714286

case 2

in: [[1,1,1],2]

expected: 1

case 3

in: [[1,2,1,2],1]

expected: 1

case 4

in: [[],3]

expected: 0

case 5

in: [[1,2,3],3]

expected: 1

Starter codePython

def lru_competitive_ratio(pages, cache_size):
    # Your code here
    pass

5 test cases · run your code against them in the editor