Implementing a Self Organizing List in Go

Hello guys, I have recently written a library implementing self-organizing list in Go language. This was a part of my experiments with Go. Go indeed is a very awesome language to learn. Some of the good things about Go is that it's very fast as this is a compiled language. And it has some inbuild strict checking so this will basically force you to write good quality code with no unused variables and all. Go also has standard libraries for unit test and benchmarking which is very simple to implement. So basically you won't need to look for compatible libraries for creating benchmarks and writing test cases for your projects.


So now coming to our topic self-organizing list. The self-organizing list is a kind of self-learning list which will rearrange its elements based on their usage to improve their average access time. The aim of the self-organizing list is to improve the efficiency of linear search by moving more frequently accessed items towards the head of the list. 

There are several techniques for rearranging the nodes. Some of the basic techniques are:- 

1. Move to Front Method (MTF):-

This technique moves the element which is accessed to the head of the list. This has the advantage of being easily implemented and requiring no extra memory. This heuristic also adapts quickly to rapid changes in the query distribution. On the other hand, this method may prioritize infrequently accessed nodes-for example, if an uncommon node is accessed even once, it is moved to the head of the list and given maximum priority even if it is not going to be accessed frequently in the future. These 'over-rewarded' nodes destroy the optimal ordering of the list and lead to slower access times for commonly accessed elements. Another disadvantage is that this method may become too flexible leading to access patterns that change too rapidly. This means that due to the very short memories of access patterns even an optimal arrangement of the list can be disturbed immediately by accessing an infrequent node in the list.



Here is the pseudo code for this implementation.

And this is my implementation of this method in Go


2. Count:-

In this technique, the number of times each node was searched for is counted i.e. every node keeps a separate counter variable which is incremented every time it is called. The nodes are then rearranged according to decreasing count. Thus, the nodes of highest count i.e. most frequently accessed are kept at the head of the list. The primary advantage of this technique is that it generally is more realistic in representing the actual access pattern. However, there is an added memory requirement, that of maintaining a counter variable for each node in the list. Also, this technique does not adapt quickly to rapid changes in the access patterns. For example: if the count of the head element say A is 100 and for any node after it say B is 40, then even if B becomes the new most commonly accessed element, it must still be accessed at least (100 - 40 = 60) times before it can become the head element and thus make the list ordering optimal.



Here is the pseudo code for this implementation.
And this is my implementation of this method in Go


3. Transpose Method:-

This technique involves swapping an accessed node with its predecessor. Therefore, if any node is accessed, it is swapped with the node in front unless it is the head node, thereby increasing its priority. This algorithm is again easy to implement and space efficient and is more likely to keep frequently accessed nodes at the front of the list. However, the transpose method is more cautious. i.e. it will take many accesses to move the element to the head of the list. This method also does not allow for rapid response to changes in the query distributions on the nodes in the list.


Here is the pseudo code for this implementation.

And this is my implementation of this method in Go

You can find the full source code of this library with the instructions to implement this in your project here on my Github repo. Library also includes the test files for each method. If you find something missing in the library and want to contribute feel free to open an issue in the Github repo.

Reference: wikipedia

Comments

Popular posts from this blog

All about NIT Agartala

How to integrate a payment gateway into your WordPress website for donations without using woocommerce