Bonus1

LRU-K

王子轩

Date: 2024-6-8

Chapter 1: Introduction

Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn’t been used for the longest amount of time) when the cache is full and a new page is referenced which is not there in cache.

LRU-K is a variant of the LRU algorithm, where K represents the number of recent uses. LRU can be considered as LRU-1. Unlike LRU, the LRU-K requires the maintenance of two different queues (for historical access and cache). The data in the historical access queue is not moved to the cache queue until the data is hit K times.

Chapter 2: Algorithm Specification

Pseudo code：

function processIntegers(k, n, m, integerList):
    cacQueue = initializeQueue() // Queue for 'cac' 
    hisQueue = initializeQueue() // Queue for 'his' (user's queue)
    hashTable = initializeHashTable() // Hash table to track occurrences
    for each integer in integerList:
        if integer in cacQueue:
            remove(integer from cacQueue)
            enqueue(integer to cacQueue) // Re-add to the tail
        else if integer in hisQueue:
            remove(integer from hisQueue)
            enqueue(integer to hisQueue) // Re-add to the tail
        else:
            if hisQueue is full:
                remove(head of hisQueue)
                enqueue(integer to hisQueue)
            else:
                enqueue(integer to hisQueue)
        updateHashTable(integer, hashTable)
        if hashTable[integer] == k:
            move(integer from hisQueue to cacQueue)
            reset(hashTable[integer])
    results = []
    while hisQueue is not empty:
        if hisQueue is empty:
            results.append("-")
        else:
            results.append(dequeue from hisQueue)
    while cacQueue is not empty:
        if cacQueue is empty:
            results.append("-")
        else:
            results.append(dequeue from cacQueue)
    return results
// Main execution
k = readInteger() // The threshold for moving integers to 'cac' queue
n = readInteger() // The size of 'his' queue
m = readInteger() // The number of integers to process
integerList = readIntegerList(m) // The list of integers to process

results = processIntegers(k, n, m, integerList)
output(results)

Chapter 3: Testing Results

input	expect	aim	actual output
2 5 17 9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6 9	4 9 8 3 7 5 6	Experimenting with two lines of output	4 9 8 3 7 5 6
3 5 10 9 5 6 7 8 3 8 9 5 9	7 3 8 5 9 -	Experimenting with one line of output	7 3 8 5 9 -

Chapter 4: Analysis and Comments

Time Complexity Derivation:

1. Initialization operations.

   • The time complexity of initializing the queues cacQueue and hisQueue is O(1). - The time complexity of initializing the hash table hashTable depends on how the hash table is implemented and is usually O(m), where m is the length of the list of integers.

2. Processing integer lists.

   • For each integer in the integer list integerList, do the following:

     • Check if the integer is in cacQueue or hisQueue: O(1) (assuming O(1) for hash table operations). - If in queue, remove and rejoin tail of queue: O(1). - If not in queue, check if hisQueue is full, if so, remove head element and add new element: O(1). - Update the hash table: O(1). - Thus, for each integer, the total time complexity of the above operations is O(1).

3. Output results after processing is complete.

   • Remove elements from hisQueue and cacQueue in turn and add them to the result list: O(n + k), where n is the maximum capacity of hisQueue and k is the number of elements in cacQueue.

In summary, the time complexity of the whole algorithm is O(m + n + k), where m is the length of the list of integers, n is the capacity of hisQueue, and k is the number of elements in cacQueue.

Derivation of space complexity:

1. Queues and hash tables.

   • The space complexity of cacQueue and hisQueue is O(k) and O(n) respectively. - The space complexity of the hash table hashTable is O(m) because it stores the number of occurrences of each integer.

2. ResultList.

   • The space complexity of the result list is O(n + k) because it contains at most all the elements in hisQueue and cacQueue.

Therefore, the space complexity of the whole algorithm is O(m + n + k), where m is the length of the integer list, n is the capacity of hisQueue, and k is the number of elements in cacQueue.

Directions for improvement：

Time complexity optimization

1. Optimizing the use of hash tables.

   • If the hash table implementation is not optimal, consider using more efficient data structures such as balanced binary search trees (e.g., red-black trees) or jump tables, which provide more stable query and update time complexity when there are more hash conflicts.

2. Reducing unnecessary operations.

   • If there are duplicate or unnecessary computations in the algorithm, try to reduce these operations by caching the results or simplifying the logic.

3. Batch processing.

   • If the algorithm allows it, consider batch processing some operations to reduce the number of accesses to the data structure, thus reducing the time complexity.

Space complexity optimization

1. Space reuse.

   • If the data stored in hisQueue and cacQueue are duplicated or can be shared in some way, you can try to reuse the space to reduce the memory usage.

2. Data structure selection.

   • Choose an appropriate data structure to store the data. For example, if the range of elements is limited, you can use a bit array or Bloom filter to reduce the space usage.

Algorithm logic optimization

1. Reduce queue operations.

   • If queue operations are frequent and have an impact on performance, consider whether they can be reduced through algorithm logic tuning.

2. Avoid duplicate calculations.

   • If there are repeated calculations in the algorithm, consider avoiding repeated calculations by caching or preprocessing.

Code level optimization

1. Loop Expansion.

   • For loop structure, if the number of loops is fixed and small, loop unrolling can be used to reduce the loop overhead.

2. Inline function calls.

   • For short functions that are called frequently, consider inlining them to reduce the function call overhead.

3. Algorithm parallelization.

   • If algorithms can be executed in parallel, consider using multi-threading or multi-processing to speed up the computation process.

Appendix: Source Code (in C)

#include <stdio.h>

int main()

{

    int k, n, m;

    // k: number of types of cookies

    // n: number of types of crackers

    // m: number of crackers to be distributed

    scanf("%d%d%d", &k, &n, &m);

    static int his[200000];

    static int cac[200000];

    static int hash_his[200000];

    static int hash_cac[200000];

    // hash_his: a hash table to store the index of each cookie in the history array

    // hash_cac: a hash table to store the index of each cookie in the current array

   // Initialize all the hash_his and hash_cac to -1

 for (int i = 0; i < 200000; i++)

    {

        hash_his[i] = hash_cac[i] = -1;

    }

    // Initialize the pointers

    int his_tail = 0;

    int cac_tail = 0;

    int his_head = 0;

    int cac_head = 0;

    int his_blank = 0;

    int cac_blank = 0;

    // Initialize the count array

    int cnt[200000] = {0};

    // Iterate through the array

    for (int i = 0; i < m; i++)

    {

        int x;

        scanf("%d", &x);

        // x: the type of the current cracker

        if (hash_cac[x] != -1)

        {

            cac[hash_cac[x]] = -1;

            if (hash_cac[x] == cac_head)

            {

                cac_head++;

                // move the head of the current array to the right

                for (; cac[cac_head] == -1 && cac_head < cac_tail; cac_head++)

                    ;

            }

            // cac_blank is incremented by 1

            cac_blank++;

            // cac_tail is incremented by 1

            cac_tail++;

            // The value x is stored at the position cac_tail - 1

            cac[cac_tail - 1] = x;

            // The value x is stored at the position hash_cac[x] in the hash_cac array

            hash_cac[x] = cac_tail - 1;

        }

        else

        {

            // If the value x is in the history array

            if (hash_his[x] != -1)

            {

                // The value hash_his[x] is set to -1 in the history array

                his[hash_his[x]] = -1;

                // If the value hash_his[x] is equal to his_head

                if (hash_his[x] == his_head)

                {

                    // his_head is incremented by 1

                    his_head++;

                    // move the head of the history array to the right

                    for (; his[his_head] == -1 && his_head < his_tail; his_head++)

                        ;

                }

                //his_blank++;

                //his_tail++;

                //his[his_tail - 1] = x;

                //hash_his[x] = his_tail - 1;

            }

            else

            {

                if (his_tail - his_blank == n)

                {

                    cnt[his[his_head]]--;

                    hash_his[his[his_head]] = -1;

                    his[his_head] = -1;

                    his_head++;

                    for (; his[his_head] == -1 && his_head < his_tail; his_head++)

                        ;

                    //his_blank++;

                    //his_tail++;

                    //his[his_tail - 1] = x;

                    //hash_his[x] = his_tail - 1;

                }

                else

                {

                    //his[his_tail++] = x;

                    //hash_his[x] = his_tail - 1;

                }

            }

            cnt[x]++;

            // If the count of the current element is equal to k

            if (cnt[x] == k)

            {

                // If the number of elements in the current array is equal to the number of elements in the original array

                if (cac_tail - cac_blank == n)

                {

                    // If the element is in the array, set its value to -1

                    hash_cac[cac[cac_head]] = -1;

                    // Set the element to -1

                    cac[cac_head] = -1;

                    // Increment the head

                    cac_head++;

                    // Find the next non-negative element

                    for (; cac[cac_head] == -1 && cac_head < cac_tail; cac_head++)

                        ;

                    // Increment the blank

                    cac_blank++;

                    // Increment the tail

                    cac_tail++;

                    // Set the element to the current value

                    cac[cac_tail - 1] = x;

                    // Set the element's value to the current tail

                    hash_cac[x] = cac_tail - 1;

                }

                // Otherwise, add the element to the array

                else

                {

                    cac[cac_tail++] = x;

                    hash_cac[x] = cac_tail - 1;

                }

                // Decrement the tail

                his_tail--;

                // Set the element's value to -1

                hash_his[his[his_tail]] = -1;

                // Set the element's count to 0

                cnt[x] = 0;

            }

        }

    }

    // If the number of elements in the history array is equal to the number of elements in the original array

    if (his_blank == his_tail)

    {

        // Print -

        printf("-\n");

    }

    // Otherwise, print the elements in the history array

    else

    {

        // Print the first element

        printf("%d", his[his_head]);

        // Print the remaining elements

        for (int i = his_head + 1; i < his_tail; i++)

        {

            if (his[i] != -1)

            {

                printf(" %d", his[i]);

            }

        }

        // Print a new line

        printf("\n");

    }

  

    // If the number of elements in the array is equal to the number of elements in the original array

    if (cac_tail == cac_blank)

    {

        // Print -

        printf("-\n");

    }

    // Otherwise, print the elements in the array

    else

    {

        // Print the first element

        printf("%d", cac[cac_head]);

        // Print the remaining elements

        for (int i = cac_head + 1; i < cac_tail; i++)

        {

            if (cac[i] != -1)

            {

                printf(" %d", cac[i]);

            }

        }

        // Print a new line

        printf("\n");

    }

    return 0;

}

Declaration

I hereby declare that all the work done in this project titled “LRU-K” is of my independent effort.