Skip to content

Latest commit

 

History

History
189 lines (151 loc) · 9.07 KB

README.md

File metadata and controls

189 lines (151 loc) · 9.07 KB
Raw

The library provides a powerful and flexible implementation of the self-organizing list data structure written in TypeScript. It offers support for multiple heuristic algorithms such as Frequency Count, Move to Front and Transpose. In addition to custom methods, the data structure also includes a selection of methods with behavior equivalent to that of JavaScript's built-in Array data structure.

Introduction

A self-organizing list (aka SoList) is a list that reorders its elements based on some self-organizing heuristic to improve average access time. The aim of a self-organizing list is to improve efficiency of linear search by moving more frequently accessed items towards the head of the list. A self-organizing list achieves near constant time for element access in the best case. A self-organizing list uses a reorganizing algorithm to adapt to various query distributions at runtime.

Self-organizing techniques

Frequency Count

This technique involves counting the number of times each node is searched for, by keeping a separate counter variable for each node that is incremented every time the node is accessed.

Pseudocode:

init: count(i) = 0 for each item i
At t-th item selection:
    if item i is searched:
        count(i) = count(i) + 1
        rearrange items based on count

Move to Front

This technique moves the node which is accessed to the head of the list.

Pseudocode:

At the t-th item selection:
    if item i is selected:
        move item i to head of the list

Transpose

This technique involves swapping an accessed node with its predecessor.

Pseudocode:

At the t-th item selection:
   if item i is selected:
        if i is not the head of list:
            swap item i with item (i - 1)

Rearrange upon creation

In literature, some self-organizing list implementations activate a heuristic after every creation operation (like insert(), push(), unshift(), etc.). This means that immediately after a new node is added to the list, the relevant heuristic is triggered and the list is rearranged.

This library supports both of these approaches. By default, the list is only rearranged when searched. To activate the option for rearranging the list upon creation, use rearrangeOnCreation=true when creating a new SoList instance. See the example below for more details.

Methods which perform rearrange of the list:

  • Rearrange upon search: at(), find(), findIndex(), findLast(), findLastIndex(), includes(), indexOf() and lastIndexOf().
  • Rearrange upon creation: constructor (initialization from an iterable), insert(), push() and unshift().

Installation

npm install solists

Example

const { FrequencyCountSoList, MoveToFrontSoList, TransposeSoList } = require("solists");

/** Examples of SoList without rearrange upon creation **/

// Example of SoList with Frequency Count heuristic
const fcList1 = new FrequencyCountSoList(false,[1,2,3,4,5]);
console.log(fcList1.toString()); // 1,2,3,4,5
fcList1.includes(2);
fcList1.includes(4);
console.log(fcList1.toString()); // 2,4,1,3,5

// Example of SoList with Move to Front heuristic
const mtfList1 = new MoveToFrontSoList(false,[1,2,3,4,5]);
console.log(mtfList1.toString()); // 1,2,3,4,5
mtfList1.includes(2);
mtfList1.includes(4);
console.log(mtfList1.toString()); // 4,2,1,3,5

// Example of SoList with Transpose heuristic
const tList1 = new TransposeSoList(false,[1,2,3,4,5]);
console.log(tList1.toString()); // 1,2,3,4,5
tList1.includes(2);
tList1.includes(4);
console.log(tList1.toString()); // 2,1,4,3,5

/** Examples of SoList with rearrange upon creation **/

// Example of SoList with Frequency Count heuristic
const fcList2 = new FrequencyCountSoList(true,[1,2,3,4,5]);
console.log(fcList2.toString()); // 1,2,3,4,5
fcList2.includes(2);
fcList2.includes(4);
console.log(fcList2.toString()); // 2,4,1,3,5

// Example of SoList with Move to Front heuristic
const mtfList2 = new MoveToFrontSoList(true,[1,2,3,4,5]);
console.log(mtfList2.toString()); // 5,4,3,2,1
mtfList2.includes(2);
mtfList2.includes(4);
console.log(mtfList2.toString()); // 4,2,5,3,1

// Example of SoList with Transpose heuristic
const tList2 = new TransposeSoList(true,[1,2,3,4,5]);
console.log(tList2.toString()); // 2,3,4,5,1
tList2.includes(2);
tList2.includes(4);
console.log(tList2.toString()); // 2,4,3,5,1

Methods and properties

List of properties of SoList:

Name Description
length Represents the number of elements in that SoList

List of methods of SoList:

Name Description
solist[Symbol.iterator]() Returns an iterator that yields the value of each index in the SoList
at() Returns the value at a given index
concat() Returns a new SoList consisting of merging the existing SoList with given iterable inputs
constructor Creates a new empty SoList instance or from a given iterable
copyWithin() Shallow copies part of a SoList to another location in the same SoList and returns it
entries() Returns a SoList iterator object of key/value pairs
every() Checks if every element in a SoList satisfies a predicate function
fill() Changes all elements in a SoList to a static value
filter() Creates a new SoList with every element in a SoList that satisfies a predicate function
find() Returns the value of the first element in a SoList that satisfies a predicate function
findIndex() Returns the index of the first element in a SoList that satisfies a predicate function
findLast() Returns the value of the last element in a SoList that satisfies a predicate function
findLastIndex() Returns the index of the last element in a SoList that satisfies a predicate function
flat() Creates a new SoList with all sub-SoList elements concatenated into it recursively up to the specified depth
forEach() Executes a provided function once for each SoList element
includes() Determines whether a SoList includes a certain value among its entries
indexOf() Returns the first index at which a given element can be found in a SoList
insert() Adds an element into a specific index of a SoList
isEmpty() Checks if the SoList does not contain any elements
isEqual() Checks if the SoList is equal to a given iterable
join() Joins all elements of SoList into a string separated by commas or a specified separator string
keys() Returns a SoList iterator object of keys
lastIndexOf() Returns the last index at which a given element can be found in a SoList
map() Creates a new SoList populated with the results of calling a provided function on every element of a SoList
pop() Removes the last element from a SoList and returns that element
push() Adds one or more elements to the end of a SoList and returns the new length of the SoList
reduce() Reduces the values of a SoList to a single value (going left-to-right)
reduceRight() Reduces the values of a SoList to a single value (going right-to-left)
remove() Removes an element by a specific index from a SoList
reverse() Reverses the order of the elements in a SoList
shift() removes the first element from a SoList and returns that removed element
slice() Returns a shallow copy of a portion of a SoList into a new SoList selected by positions
some() Checks if any of the elements in a SoList satisfy a predicate function
sort() Sorts the elements of a SoList and returns the reference to the same SoList, now sorted
splice() Changes the contents of a SoList by removing or replacing existing elements and/or adding new elements
toLocaleString() Returns a string representing the elements of the SoList using their toLocaleString methods
toString() Returns a string representing the specified SoList and its elements
unshift() Adds one or more elements to the beginning of a SoList and returns the new length of the SoList
values() Returns a SoList iterator object of values

SoList vs JS-Array

Although SoList implements most of the methods of JS-Array (with identical behavior), there are several differences and limitations:

  • Unlike JS-Array, SoList does not support empty items (for example [1,,3]).
  • Currently, the every(), filter(), find(), findIndex(), findLast(), findLastIndex(), flatMap() and some() don't support the thisArg argument.
  • Unsupported JS-Array methods: group() and groupToMap().
  • Additional custom methods of SoList: insert(), isEmpty(), isEqual() and remove().

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

Please make sure to update tests as appropriate and run existing ones using:

npm run test

License

The library is freely distributable under the terms of the MIT license.