Una lista autoorganizada es una lista que modifica el orden en que se almacenan los elementos según el patrón de acceso real o esperado. El objetivo es conseguir una ordenación que mantenga más próximos los elementos más buscados para mejorar el tiempo medio de acceso. Esta propiedad también se conoce como la localidad de referencia que trae los elementos más utilizados al principio de la lista. Esto aumenta la probabilidad de encontrar el elemento al principio de la lista y los elementos que rara vez se usan se empujan al final de la lista.
Técnicas para reorganizar Nodes
Al ordenar los elementos en la lista, las probabilidades de acceso de los elementos generalmente no se conocen de antemano. Esto ha llevado al desarrollo de varias heurísticas para aproximar el comportamiento óptimo. Las heurísticas básicas utilizadas para reordenar los elementos en la lista son,
1. Método Mover al Frente
Esta técnica mueve el elemento que se evalúa a la cabeza de la lista.
En la t-ésima selección de elementos:
si se selecciona el elemento i:
mover el elemento i al encabezado de la lista
2. Método de conteo
En esta técnica, se cuenta el número de veces que se buscó cada Node, es decir, cada Node mantiene una variable de contador separada que se incrementa cada vez que se llama.
init: count(i) = 0 para cada elemento i
En t-ésima selección de artículo:
si se busca el elemento i:
cuenta(i) = cuenta(i) + 1
3. Método de transposición
Esta técnica implica intercambiar un Node accedido con su predecesor.
En la t-ésima selección de elementos:
si se selecciona el elemento i:
si no soy el cabeza de lista:
intercambiar el artículo i con el artículo (i – 1)
Java
// Java Program to Implement Self organizing List
import java.util.Scanner;
class SelfOrganizingList {
private int[] list;
private int[] count;
private int size;
// Constructor
public SelfOrganizingList(int listSize)
{
list = new int[listSize];
count = new int[listSize];
size = 0;
}
// checks if list is empty
public boolean isEmpty() { return size == 0; }
// checks if list is full
public boolean isFull() { return size == list.length; }
// Makes list empty
public void makeEmpty()
{
int l = list.length;
list = new int[l];
count = new int[l];
size = 0;
}
// returns the size of list
public int getSize() { return size; }
// Function to insert element
public void insert(int val)
{
if (isFull()) {
System.out.println("Error : List full!");
return;
}
list[size] = val;
count[size] = 0;
size++;
}
// Function to remove element
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--;
}
// Function to search for an element
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;
}
// prints 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] + " ");
}
}
public class SelfOrganizingListTest {
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("SelfOrganizingList Test\n");
// Creating object of class SelfOrganizingList
System.out.println("Enter size of list ");
SelfOrganizingList list
= new SelfOrganizingList(scan.nextInt());
char ch;
// Perform list operations
do {
System.out.println(
"\nSelfOrganizingList Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete at position");
System.out.println("3. search");
System.out.println("4. check empty");
System.out.println("5. check full");
System.out.println("6. get size");
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("Wrong Entry \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');
}
}
Producción
1.1 elemento de inserción
Insertar elemento en la lista: 12
1.2 elemento de inserción
Insertar elemento en la lista: 13
Elemento de búsqueda
Elemento de búsqueda = 13
Publicación traducida automáticamente
Artículo escrito por amnindersingh1414 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA