Open In App

Self Organizing List | Set 1 (Introduction)

Last Updated : 19 May, 2017
Improve
Improve
Like Article
Like
Save
Share
Report

The worst case search time for a sorted linked list is O(n). With a Balanced Binary Search Tree, we can skip almost half of the nodes after one comparison with root. For a sorted array, we have random access and we can apply Binary Search on arrays.

One idea to make search faster for Linked Lists is Skip List. Another idea (which is discussed in this post) is to place more frequently accessed items closer to head.. There can be two possibilities. offline (we know the complete search sequence in advance) and online (we don’t know the search sequence).
In case of offline, we can put the nodes according to decreasing frequencies of search (The element having maximum search count is put first). For many practical applications, it may be difficult to obtain search sequence in advance. A Self Organizing list reorders its nodes based on searches which are done. The idea is to use locality of reference (In a typical database, 80% of the access are to 20% of the items). Following are different strategies used by Self Organizing Lists.

1) Move-to-Front Method: Any node searched is moved to the front. This strategy is easy to implement, but it may over-reward infrequently accessed items as it always move the item to front.

2) Count Method: Each node stores count of the number of times it was searched. Nodes are ordered by decreasing count. This strategy requires extra space for storing count.

3) Transpose Method: Any node searched is swapped with the preceding node. Unlike Move-to-front, this method does not adapt quickly to changing access patterns.

Competitive Analysis:
The worst case time complexity of all methods is O(n). In worst case, the searched element is always the last element in list. For average case analysis, we need probability distribution of search sequences which is not available many times.
For online strategies and algorithms like above, we have a totally different way of analyzing them called competitive analysis where performance of an online algorithm is compared to the performance of an optimal offline algorithm (that can view the sequence of requests in advance). Competitive analysis is used in many practical algorithms like caching, disk paging, high performance computers. The best thing about competitive analysis is, we don’t need to assume anything about probability distribution of input. The Move-to-front method is 4-competitive, means it never does more than a factor of 4 operations than offline algorithm (See the MIT video lecture for proof).

We will soon be discussing implementation and proof of the analysis given in the video lecture.

References:
http://en.wikipedia.org/wiki/Self-organizing_list
MIT Video Lecture
http://www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf
http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)

This article is compiled by Abhay Rathi.


https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Skip List | Set 1 (Introduction)
Next Article
Unrolled Linked List | Set 1 (Introduction)

Similar Reads

Self Organizing List : Move to Front Method
Self Organizing list is a list that re-organizes or re-arranges itself for better performance. In a simple list, an item to be searched is looked for in a sequential manner which gives the time complexity of O(n). But in real scenario not all the items are searched frequently and most of the time only few items are searched multiple times.  So, a s
10 min read
Self Organizing List : Count Method
Self Organizing list is a list that re-organizes or re-arranges itself for better performance. In a simple list, an item to be searched is looked for in a sequential manner which gives the time complexity of O(n). But in real scenario not all the items are searched frequently and most of the time only few items are searched multiple times.  So, a s
11 min read
Organizing Tournament Problem
Given a positive integer N representing the count of players playing the game. The game is played between two teams such that each team consists of at least one player but the total count of players in the game must be N. The game lasts in exactly 30 minutes, the task is to check if all players will play the game against each other or not If the ga
8 min read
Inversion count in Array Using Self-Balancing BST
Inversion Count for an array indicates – how far (or close) the array is from being sorted. If an array is already sorted then the inversion count is 0. If an array is sorted in the reverse order that inversion count is the maximum. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. For simplicity, we may assume that all e
15+ min read
Self Descriptive Number
Given an integer N, the task is to find all the self-descriptive numbers from 1 to N A self-descriptive number is an integer n in given base b is b digits long in which each digit at position p (the most significant digit being at position 0 and the least significant at position b - 1) counts how many times a digit p is in n. For example in base 10
11 min read
Self-Balancing Binary Search Trees
Self-Balancing Binary Search Trees are height-balanced binary search trees that automatically keep the height as small as possible when insertion and deletion operations are performed on the tree. The height is typically maintained in order of logN so that all operations take O(logN) time on average. Examples: The most common examples of self-balan
4 min read
Find the centroid of a non-self-intersecting closed Polygon
Given N vertices of the polygon, the task is to find the centroid of the polygonExamples: Input: ar = {{0, 0}, {0, 8}, {8, 8}, {8, 0}} Output: {Cx, Cy} = {4, 4} Input: ar = {{1, 2}, {3, -4}, {6, -7}} Output: {Cx, Cy} = {3.33, -3} Approach: The centroid of a non-self-intersecting closed polygon defined by n vertices (x0, y0), (x1, y1), ..., (xn-1, y
5 min read
Why You Should Become a Self-Taught Programmer?
You may have heard about Jack Dorsey (Twitter), Mark Zuckerberg (Facebook), Kevin Systrom (Instagram) and many others. Right, these are one of the top programmers and tech enthusiasts who are currently ruling the world. But, have you ever thought that what made them so accomplished and proficient in the world of programming? No, it is not any colle
8 min read
Self Numbers
A Number N is said to be Self Number if it can not be written as M + sum of digits of M for any M.The first few Self numbers are: 1, 3, 5, 7, 9, 20, 31, 42................ Check if N is a Self number Given an integer N, the task is to find if this number is Self number or not. Examples: Input: N = 3 Output: Yes Explanation: 1 + sumofDigits(1) = 2 2
5 min read
Self Balancing BST in JavaScript
A self-balancing binary search tree (BST) is a type of binary search tree that automatically keeps its height balanced in order to guarantee that operations such as searching, inserting, and deleting elements in the tree take less time on average. How do self-balancing BSTs maintain height balance? Self-balancing binary search trees (BSTs) maintain
11 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox