<commit_before>A Go data structure benchmark
=============================

This is an experiment to determine the best way to store elements indexed by an integer in Go.

The "best way" is of course relative to the scenario in which the storage will be used. My focus will mostly be on the following scenario:

- The storage system may be static
- Accessing elements is done a lot more frequently than adding elements
- The lookup should be able to happen by multiple parallel go routines, so it should not be blocking

This repository contains some general benchmarks that allows to compare the storage costs and lookup time of a few different data structures in relation to the amount of elements stored in the structure.

If you want to add other data structures to the test, or if you spot a mistake, feel free to send me a pull request.

Following data structures are currently tested:

## [The simple Binary Search Tree (BST)](http://en.wikipedia.org/wiki/Binary_search_tree)

A Binary search tree is a simple way to store data indexed by an integer, with a focus on fast retrieval (compared to e.g a linked list).

In theory, it has an average lookup time complexity of O(log n), and a worst case lookup time of O(n). This worst case occurs when elements are added in-order (based on their index). This makes it a pretty bad in a lot of common scenario's.

A good way to prevent a worst case scenario would be to sort the elements before inserting them in the tree. The downside of this is that then the tree is not entirely dynamic, meaning we need to rebuild the tree every time when we want to add new elements after the initial build. In some use-cases (like in my case), this is not a problem.

I did not implement this sorting mechanism, but I did add an algorithm to the benchmark that inserts elements in an ideal order. This allows to measure only the characteristics of the "tree part" of the data structure in a best case scenario.

## [The Left-Leaning Red-Black (LLRB) tree](http://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree)

The LLRB tree is a type of tree similar to the binary search tree, but it is self-balancing. This means it has a O(log n) lookup time complexity regardless of the order the elements where added.
<commit_msg>Added link to skip directly to the results<commit_after>A Go data structure benchmark
=============================

This is an experiment to determine the best way to store elements indexed by an integer in Go.

TL;DR, skip to [the results](#user-content-test-results)

The "best way" is of course relative to the scenario in which the storage will be used. My focus will mostly be on the following scenario:

- The storage system may be static
- Accessing elements is done a lot more frequently than adding elements
- The lookup should be able to happen by multiple parallel go routines, so it should not be blocking

This repository contains some general benchmarks that allows to compare the storage costs and lookup time of a few different data structures in relation to the amount of elements stored in the structure.

If you want to add other data structures to the test, or if you spot a mistake, feel free to send me a pull request.

Following data structures are currently tested:

## [The simple Binary Search Tree (BST)](http://en.wikipedia.org/wiki/Binary_search_tree)

A Binary search tree is a simple way to store data indexed by an integer, with a focus on fast retrieval (compared to e.g a linked list).

In theory, it has an average lookup time complexity of O(log n), and a worst case lookup time of O(n). This worst case occurs when elements are added in-order (based on their index). This makes it a pretty bad in a lot of common scenario's.

A good way to prevent a worst case scenario would be to sort the elements before inserting them in the tree. The downside of this is that then the tree is not entirely dynamic, meaning we need to rebuild the tree every time when we want to add new elements after the initial build. In some use-cases (like in my case), this is not a problem.

I did not implement this sorting mechanism, but I did add an algorithm to the benchmark that inserts elements in an ideal order. This allows to measure only the characteristics of the "tree part" of the data structure in a best case scenario.

## [The Left-Leaning Red-Black (LLRB) tree](http://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree)

The LLRB tree is a type of tree similar to the binary search tree, but it is self-balancing. This means it has a O(log n) lookup time complexity regardless of the order the elements where added.

{'fraction_non_alphanumeric': 0.05359844391614437, 'fraction_numerical': 0.002161227577263886, 'mean_word_length': 4.2531214528944385, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2573288', 'n_tokens_mistral': 1133, 'n_tokens_neox': 1093, 'n_words': 764}