自组织列表

2024 年 8 月 28 日 | 阅读 13 分钟

自组织列表使用自组织算法对元素进行序列化以优化平均访问时间。自组织列表旨在通过将经常访问的项推到列表的前面来提高线性搜索的效率。在最佳情况下，自组织列表可以实现近乎恒定的元素访问时间。

自组织列表使用重组方法在运行时调整以适应不同的查询分布。虽然键值排序是最常见的列表排序方法，但它不是唯一的方法。另一种组织列表以加快搜索速度的方法是按预期访问频率排序。虽然这样做的好处可能不如按键值排序那么显著，但按访问频率（至少大致）组织列表的成本要低得多，并且在某些情况下可以加快顺序搜索。

排序链表的在最坏情况下的搜索时间为 O(n)。与根节点进行一次比较后，我们可以跳过平衡二叉搜索树中大约一半的节点。我们对排序数组有随机访问权限，并且可以在数组上使用二分查找。

自组织列表根据记录的实际访问模式重新排列列表中的记录。自组织列表采用启发式方法来确定如何排列列表。这些启发式方法与缓冲区池管理指南相似。实际上，缓冲区池是一种自组织列表。因为我们通常必须检查缓冲区的内容以确定所需信息是否已在主内存中，所以按预期访问频率对缓冲区池进行排序是一种合适的方法。

当按访问频率排序时，当需要读取新页面信息时，列表末尾的缓冲区最适合重用。有三种传统的启发式方法用于管理自组织列表。这三种启发式方法如下所述：

1. 频率计数

保持列表按频率排序的最明显技术之一是跟踪每个记录被访问的次数，并始终将记录按该顺序保存。这种过程将被称为频率计数，或简称为“计数”。计数是一种不经常使用的缓冲区替换方法。如果对某个记录的访问次数超过了对它之前的记录的访问次数，则该记录将提前到列表的头部。因此，计数将按记录到目前为止发生的顺序跟踪记录。

计数对访问频率随时间的增加响应不佳，并且需要空间来存储访问计数。一个记录一旦被访问过一次，就会有很多人访问它。除了需要空间来存储访问计数之外，计数对访问频率随时间的增加响应不佳。无论随后的访问历史如何，在频率计数系统下，一旦一个记录被访问了大量次数，它就会停留在列表的顶部附近。

2. 换位

任何找到的记录都应与其在列表中排在它前面的记录进行交换。这种策略称为换位。对于使用链表或数组实现的列表，换位是一个可行的选择。经常使用的记录会随着时间的推移而移到列表的顶部。以前经常访问但不再需要的记录将逐渐被推到文件柜的后面。因此，它似乎在改变访问频率方面具有有利的特性。不幸的是，有些访问序列是病态的，可能会导致换位失败。

考虑列表中的最后一个记录（称为 XX）被访问的情况。然后，将倒数第二个记录（称为 YY）与它交换。然后，将倒数第二个记录（称为 YY）与它交换，使 YY 成为最后一个记录。如果现在访问 YY，它将与 XX 交换。由于这两个记录都不会向前移动，因此 XX 和 YY 之间交替的重复访问序列将始终搜索到列表的末尾。然而，在实践中，这种病态情况很少见。将访问的记录在列表中向前移动固定步数是换位的一种变体。

3. 移到前面

当找到一个记录时，它会被移到列表的顶部，将所有其他记录推回一个位置。移到前面策略等同于最近使用的缓冲区替换策略。如果记录存储在链表中，这种启发式方法很容易实现。当记录存储在数组中时，将一个靠近末尾的记录向前移动会导致许多记录（轻微地）改变位置。

当执行至少 n 次搜索时，移到前面的成本是有限的，因为它最多需要最优静态排序对 n 个记录所需访问次数的两倍。换句话说，如果我们提前知道（至少 n 次）搜索序列，并按频率顺序存储数据以减少这些访问的总成本，那么成本至少是移到前面启发式方法所需成本的一半。（摊销分析可以验证这一点）。

最后，移到前面适应访问频率的局部变化，因此如果一个记录在短时间内经常被访问，它将在那段时间内出现在列表的顶部附近。当记录按顺序处理时，移到前面的性能很差，尤其是当顺序重复多次时。

Java 代码

现在让我们编写 Java 代码来对自组织列表数据结构执行所有基本操作。

// A Sample Java Program to Implement Self-organizing List Data Structure
 
 
import java.util.Scanner;
 

// A class named SelfOrganizingList is created that will have all the functions of the Self Organizing List Data Structure
class SelfOrganizingList
{

    // A private int array named list is created that will hold the actual data in the Self Organizing List
    private int[] list;
    // A private int array named count is created that will store the count for each of the values that are stored in the list array
    private int[] count;
    // A private int variable named size is declared that will represent the size of the Self Organizing List
    private int size;
 
    // A parameterized constructor is written that will be used to initialize both the Integer arrays named list and count with the size of the list that is passed as a parameter to the constructor
    public SelfOrganizingList(int listSize)
    {
        list = new int[listSize];
        count = new int[listSize];
        size = 0;        
    }
    

    // A function named isEmpty is written that will be used to check whether the Self Organizing List is Empty or not 
    // The return type of the isEmpty function is boolean
    public boolean isEmpty()
    {
        return size == 0;
    }
    

    // A function named isFull is written that will be used to check whether the Self Organizing List is Full or not 
    // The return type of the isFull function is boolean
    public boolean isFull()
    {
        return size == list.length;
    }

    
    // A function named makeEmpty is written that will be used to empty the Self Organizing List
    // The makeEmpty function will return all the data that was stored in the list and count arrays
    public void makeEmpty()
    {
        int l = list.length;
        
        // Both List and count arrays are made empty
        list = new int[l];
        count = new int[l];
        size = 0;        
    }

    // A function named getSize is written that will be used to return the size of the Self Organizing List
    public int getSize()
    {
        return size;
    }


    // A function named insert is written that will be used to add a new value to the Self Organizing List 
    public void insert(int val)
    {
        // Before adding a new value to the Self Organizing List, first it is checked is there space available for the accommodation of new data to be inserted
        // That check is made with the help of isFull() function
        if (isFull() )
        {
            // If there is no space available to accommodate the new data to be added, an error message is thrown, and execution is stopped 
            System.out.println("Error : List full!");
            return;
        }
        // If space is present, then data is added to the List
        list[size] = val;
        count[size] = 0;
        size++;
    }

    // A function named remove is written that will be used to remove an already existing value from the Self Organizing List 
    // The position of the value to be removed is passed as a parameter to the remove() function
    public void remove(int pos)
    {
        pos-- ;
        if (pos < 0 || pos >= size )
        {
            System.out.println("Invalid position ");
            return;
        }
        for (int i = pos; i < size - 1; i++)
        {
            list[i] = list[i + 1];
            count[i] = count[i + 1];
        }
        size--;        
    }


    // A function named search is written that will be used to search or find and already existing value from the Self Organizing List 
    public boolean search(int x)
    {
        boolean searchResult = false;
        int pos = -1;
        for (int i = 0; i < size; i++)
        {
            if (list[i] == x)
            {
                searchResult = true;
                pos = i;
                break;
            }
        }
        if (searchResult)
        {
            count[pos]++;
            int c = count[pos];
            for (int i = 0; i < pos; i++)
            {
                if (count[pos] > count[i])
                {
                    for (int j = pos; j > i; j--)
                    {
                        list[j] = list[j - 1];
                        count[j] = count[j - 1];
                    }
                    list[i] = x;
                    count[i] = c;
                    break;
                }
            }
        }
        return searchResult;        
    }
    

    // A function named printList is written that will be used to print all the data present in the Self Organizing List 
    public void printList()
    {
        System.out.print("\nList = ");
        for (int i = 0; i < size; i++)
            System.out.print(list[i] +" ");
        System.out.print("\nCount = ");
        for (int i = 0; i < size; i++)
            System.out.print(count[i] +" ");
    }
}// end of SelfOrganizingList Class

public class Main
{    
    // main function is written to call all the functionalities functions of the Self Organizing List Data structure written above
    public static void main(String[] args)
    {             
        Scanner scan = new Scanner(System.in);
 
        // An object of the SelfOrganizingList Class is created
        System.out.println("Enter size of Self Organizing List::");
        SelfOrganizingList list = new SelfOrganizingList(scan.nextInt()); 
 
        char ch;
         // Do-while loop
        // Do part for performing actions
        do
        // Menu is displayed
        // Users enter 'y' to continue 'n' if
        // entered by user , the program terminates
        {
            System.out.println("Please Choose one of the Operations::");
            System.out.println("1. To insert Data in the Self Organizing List.");
            System.out.println("2. To delete Data from the Self Organizing List.");
            System.out.println("3. To search/find Data in the Self Organizing List.");
            System.out.println("4. To Check List is empty or not.");
            System.out.println("5. To Check List is full or not.");
            System.out.println("6. To Get the size of the Self Organizing List.");            
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                list.insert( scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("Enter position to delete");
                list.remove(scan.nextInt() );                     
                break;                         
            case 3 : 
                System.out.println("Enter integer element to search");
                System.out.println("Search Result : "+ list.search(scan.nextInt() ));
                break;                                          
            case 4 : 
                System.out.println("Empty status = "+ list.isEmpty());
                break;     
            case 5 : 
                System.out.println("Full status = "+ list.isFull());
                break;                     
            case 6 :  
                System.out.println("Size = "+ list.getSize() +" \n");
                break;                         
            default : 
                System.out.println("Please enter a valid option from the menu to proceed further.\n \n");
                break;    
            }
            /*  Display List  */  
            list.printList();
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }//end of main function
}// end of main class

输出

上述代码给出以下输出。

Enter the size of Self Organizing List::
10
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
1
Enter integer element to insert
101

List = 101 
Count = 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
1
Enter integer element to insert
102

List = 101 102 
Count = 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
1
Enter integer element to insert
103

List = 101 102 103 
Count = 0 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
1
Enter integer element to insert
104

List = 101 102 103 104 
Count = 0 0 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
3
Enter integer element to search
102
Search Result : true

List = 102 101 103 104 
Count = 1 0 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
3
Enter integer element to search
104
Search Result : true

List = 102 104 101 103 
Count = 1 1 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
2
Enter position to delete
104
Invalid position 

List = 102 104 101 103 
Count = 1 1 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
2
Enter position to delete
2

List = 102 101 103 
Count = 1 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
4
Empty status = false

List = 102 101 103 
Count = 1 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
5
Full status = false

List = 102 101 103 
Count = 1 0 0 
Do you want to continue (Type y or n) 

y
Please Choose one of the Operations::
1. To insert Data in the Self Organizing List.
2. To delete Data from the Self Organizing List.
3. To search/find Data in the Self Organizing List.
4. To Check List is empty or not.
5. To Check List is full or not.
6. To Get the size of the Self Organizing List.
6
Size = 3 


List = 102 101 103 
Count = 1 0 0 
Do you want to continue (Type y or n) 

n